“Boundary-sampled halfspaces: a new representation for constructive solid modeling” by Du, Zhou, Carr and Ju

We present a novel representation of solid models for shape design. Like Constructive Solid Geometry (CSG), the solid shape is constructed from a set of halfspaces without the need for an explicit boundary structure. Instead of using Boolean expressions as in CSG, the shape is defined by sparsely placed samples on the boundary of each halfspace. This representation, called Boundary-Sampled Halfspaces (BSH), affords greater agility and expressiveness than CSG while simplifying the reverse engineering process. We discuss theoretical properties of the representation and present practical algorithms for boundary extraction and conversion from other representations. Our algorithms are demonstrated on both 2D and 3D examples.

1. Pankaj K Agarwal and Micha Sharir. 2000. Arrangements and their applications. In Handbook of computational geometry. Elsevier, 49–119.Google Scholar
2. Lionel Alberti, Bernard Mourrain, and Julien Wintz. 2008. Topology and arrangement computation of semi-algebraic planar curves. Computer Aided Geometric Design 25, 8 (2008), 631–651.Google ScholarDigital Library
3. Jean-Philippe Bauchet and Florent Lafarge. 2020. Kinetic shape reconstruction. ACM Transactions on Graphics (TOG) 39, 5 (2020), 1–14.Google ScholarDigital Library
4. Eric Berberich, Pavel Emeliyanenko, Alexander Kobel, and Michael Sagraloff. 2012. Arrangement computation for planar algebraic curves. In Proceedings of the 2011 International Workshop on Symbolic-Numeric Computation. 88–98.Google ScholarDigital Library
5. Matthew Berger, Andrea Tagliasacchi, Lee M Seversky, Pierre Alliez, Gael Guennebaud, Joshua A Levine, Andrei Sharf, and Claudio T Silva. 2017. A survey of surface reconstruction from point clouds. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 301–329.Google Scholar
6. Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269–1278.Google Scholar
7. Alexandre Boulch, Martin de La Gorce, and Renaud Marlet. 2014. Piecewise-planar 3D reconstruction with edge and corner regularization. In Computer Graphics Forum, Vol. 33. Wiley Online Library, 55–64.Google Scholar
8. Suzanne F Buchele and Richard H Crawford. 2003. Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. In Proceedings of the eighth ACM symposium on Solid modeling and applications. 135–144.Google ScholarDigital Library
9. J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. 2001. Reconstruction and Representation of 3D Objects with Radial Basis Functions. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 2001). 67–76.Google ScholarDigital Library
10. Malcolm S Casale and James E Bobrow. 1989. A set operation algorithm for sculptured solids modeled with trimmed patches. Computer Aided Geometric Design 6, 3 (1989), 235–247.Google ScholarDigital Library
11. Anne-Laure Chauve, Patrick Labatut, and Jean-Philippe Pons. 2010. Robust piecewise-planar 3D reconstruction and completion from large-scale unstructured point data. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, 1261–1268.Google ScholarCross Ref
12. Zhiqin Chen, Andrea Tagliasacchi, and Hao Zhang. 2020. Bsp-net: Generating compact meshes via binary space partitioning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 45–54.Google ScholarCross Ref
13. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and robust mesh arrangements using floating-point arithmetic. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.Google ScholarDigital Library
14. Matthijs Douze, Jean-Sébastien Franco, and Bruno Raffin. 2017. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558 (2017).Google Scholar
15. Tao Du, Jeevana Priya Inala, Yewen Pu, Andrew Spielberg, Adriana Schulz, Daniela Rus, Armando Solar-Lezama, and Wojciech Matusik. 2018. Inversecsg: Automatic conversion of 3d models to csg trees. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1–16.Google ScholarDigital Library
16. Laurent Dupont, Michael Hemmer, Sylvain Petitjean, and Elmar Schömer. 2007. Complete, exact and efficient implementation for computing the adjacency graph of an arrangement of quadrics. In European Symposium on Algorithms. Springer, 633–644.Google ScholarCross Ref
17. Jack Edmonds and Richard M Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (JACM) 19, 2 (1972), 248–264.Google ScholarDigital Library
18. Pierre-Alain Fayolle and Alexander Pasko. 2016. An evolutionary approach to the extraction of object construction trees from 3D point clouds. Computer-Aided Design 74 (2016), 1–17.Google ScholarDigital Library
19. Pierre-Alain Fayolle, Alexander Pasko, Elena Kartasheva, Christophe Rosenberger, and Christian Toinard. 2008. Automation of the volumetric models construction. In Heterogeneous objects modelling and applications. Springer, 214–238.Google Scholar
20. Francisco R Feito, Carlos J Ogáyar, Rafael Jesús Segura, and ML Rivero. 2013. Fast and accurate evaluation of regularized Boolean operations on triangulated solids. Computer-Aided Design 45, 3 (2013), 705–716.Google ScholarDigital Library
21. Karim Hamza and Kazuhiro Saitou. 2004. Optimization of constructive solid geometry via a tree-based multi-objective genetic algorithm. In Genetic and Evolutionary Computation Conference. Springer, 981–992.Google ScholarCross Ref
22. Christoph Martin Hoffmann. 1989. Geometric and solid modeling. (1989).Google Scholar
23. Zhiyang Huang, Nathan Carr, and Tao Ju. 2019. Variational implicit point set surfaces. ACM Transactions on Graphics (TOG) 38, 4 (2019), 1–13.Google ScholarDigital Library
24. Adrien Kaiser, Jose Alonso Ybanez Zepeda, and Tamy Boubekeur. 2019. A survey of simple geometric primitives detection methods for captured 3D data. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 167–196.Google Scholar
25. John Keyser, Tim Culver, Mark Foskey, Shankar Krishnan, and Dinesh Manocha. 2004. ESOLID – a system for exact boundary evaluation. Computer-Aided Design 36, 2 (2004), 175–193.Google ScholarCross Ref
26. Pierre-Alain Langlois, Alexandre Boulch, and Renaud Marlet. 2019. Surface reconstruction from 3d line segments. In 2019 International Conference on 3D Vision (3DV). IEEE, 553–563.Google ScholarCross Ref
27. Jyh-Ming Lien, Vikram Sharma, Gert Vegter, and Chee Yap. 2014. Isotopic arrangement of simple curves: An exact numerical approach based on subdivision. In International Congress on Mathematical Software. Springer, 277–282.Google ScholarCross Ref
28. Gabor Lukács, Ralph Martin, and Dave Marshall. 1998. Faithful least-squares fitting of spheres, cylinders, cones and tori for reliable segmentation. In European conference on computer vision. Springer, 671–686.Google ScholarCross Ref
29. Bernard Mourrain, Jean-Pierre Técourt, and Monique Teillaud. 2005. On the computation of an arrangement of quadrics in 3d. Computational Geometry 30, 2 (2005), 145–164.Google ScholarDigital Library
30. Gregory M Nielson. 2004. Radial hermite operators for scattered point cloud data with normal vectors and applications to implicitizing polygon mesh surfaces for generalized CSG operations and smoothing. In IEEE Visualization 2004. IEEE, 203–210.Google ScholarDigital Library
31. Sven Oesau, Florent Lafarge, and Pierre Alliez. 2014. Indoor scene reconstruction using feature sensitive primitive extraction and graph-cut. ISPRS journal of photogrammetry and remote sensing 90 (2014), 68–82.Google Scholar
32. Alexander Pasko, Valery Adzhiev, Alexei Sourin, and Vladimir Savchenko. 1995. Function representation in geometric modeling: concepts, implementation and applications. The visual computer 11, 8 (1995), 429–446.Google Scholar
33. Darko Pavić, Marcel Campen, and Leif Kobbelt. 2010. Hybrid booleans. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 75–87.Google Scholar
34. Aristides AG Requicha and Herbert B Voelcker. 1977. Constructive solid geometry. (1977).Google Scholar
35. Aristides G Requicha. 1980. Representations for rigid solids: Theory, methods, and systems. ACM Computing Surveys (CSUR) 12, 4 (1980), 437–464.Google ScholarDigital Library
36. Jaroslaw Rossignac and Aristides Requicha. 1984. Constant-radius blending in solid modelling. (1984).Google Scholar
37. Jaroslaw R Rossignac and Aristides AG Requicha. 1986. Offsetting operations in solid modelling. Computer Aided Geometric Design 3, 2 (1986), 129–148.Google ScholarDigital Library
38. Jaroslaw R Rossignac and Aristides AG Requicha. 1999. Solid modeling. Technical Report. Georgia Institute of Technology.Google Scholar
39. Ruwen Schnabel, Roland Wahl, and Reinhard Klein. 2007. Efficient RANSAC for point-cloud shape detection. In Computer graphics forum, Vol. 26. Wiley Online Library, 214–226.Google Scholar
40. Elmar Schömer and Nicola Wolpert. 2006. An exact and efficient approach for computing a cell in an arrangement of quadrics. Computational Geometry 33, 1–2 (2006), 65–97.Google ScholarCross Ref
41. Ariel Shamir. 2008. A survey on mesh segmentation techniques. In Computer graphics forum, Vol. 27. Wiley Online Library, 1539–1556.Google Scholar
42. Vadim Shapiro. 2002. Solid Modeling. Handbook of computer aided geometric design 20 (2002), 473–518.Google Scholar
43. Vadim Shapiro and Donald L Vossler. 1991. Construction and optimization of CSG representations. Computer-Aided Design 23, 11 (1991), 4–20.Google ScholarDigital Library
44. Vadim Shapiro and Donald L Vossler. 1993. Separation for boundary to CSG conversion. ACM Transactions on Graphics (TOG) 12, 1 (1993), 35–55.Google ScholarDigital Library
45. Sara Silva, Pierre-Alain Fayolle, Johann Vincent, Guillaume Pauron, Christophe Rosenberger, and Christian Toinard. 2005. Evolutionary computation approaches for shape modelling and fitting. In Portuguese Conference on Artificial Intelligence. Springer, 144–155.Google ScholarDigital Library
46. JM Smith and Neil A Dodgson. 2007. A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic. Computer-Aided Design 39, 2 (2007), 149–163.Google ScholarDigital Library
47. Yannick Verdie, Florent Lafarge, and Pierre Alliez. 2015. LOD generation for urban scenes. ACM Transactions on Graphics 34, ARTICLE (2015), 30.Google Scholar
48. Charlie CL Wang. 2010. Approximate boolean operations on large polyhedral solids with partial mesh reconstruction. IEEE transactions on visualization and computer graphics 17, 6 (2010), 836–849.Google Scholar
49. Qiaoyun Wu, Kai Xu, and Jun Wang. 2018. Constructing 3D CSG models from 3D raw point clouds. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 221–232.Google Scholar
50. Brian Wyvill, Andrew Guy, and Eric Galin. 1999. Extending the csg tree. warping, blending and boolean operations in an implicit surface modeling system. In Computer Graphics Forum, Vol. 18. Wiley Online Library, 149–158.Google Scholar
51. Songgang Xu and John Keyser. 2013. Fast and robust Booleans on polyhedra. Computer-Aided Design 45, 2 (2013), 529–534.Google ScholarDigital Library
52. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh arrangements for solid geometry. ACM Transactions on Graphics (TOG) 35, 4 (2016), 1–15.Google ScholarDigital Library
53. Yixin Zhuang, Hang Dou, Nathan Carr, and Tao Ju. 2017. Feature-aligned segmentation using correlation clustering. In Computational Visual Media, Vol. 2, 147–160.Google ScholarCross Ref