“EMBER: exact mesh booleans via efficient & robust local arrangements” by Trettner, Nehring-Wirxel and Kobbelt

Boolean operators are an essential tool in a wide range of geometry processing and CAD/CAM tasks. We present a novel method, EMBER, to compute Boolean operations on polygon meshes which is exact, reliable, and highly performant at the same time. Exactness is guaranteed by using a plane-based representation for the input meshes along with recently introduced homogeneous integer coordinates. Reliability and robustness emerge from a formulation of the algorithm via generalized winding numbers and mesh arrangements. High performance is achieved by avoiding the (pre-)construction of a global acceleration structure. Instead, our algorithm performs an adaptive recursive subdivision of the scene’s bounding box while generating and tracking all required data on the fly. By leveraging a number of early-out termination criteria, we can avoid the generation and inspection of regions that do not contribute to the output. With a careful implementation and a work-stealing multi-threading architecture, we are able to compute Boolean operations between meshes with millions of triangles at interactive rates. We run an extensive evaluation on the Thingi10K dataset to demonstrate that our method outperforms state-of-the-art algorithms, even inexact ones like QuickCSG, by orders of magnitude.

1. Marco Attene. 2020. Indirect Predicates for Geometric Constructions. Computer-Aided Design 126 (Sep 2020), 102856. Google ScholarCross Ref
2. Hichem Barki, Gael Guennebaud, and Sebti Foufou. 2015. Exact, robust, and efficient regularized Booleans on general 3D meshes. Computers & Mathematics with Applications 70, 6 (2015), 1235–1254.Google ScholarDigital Library
3. Gilbert Bernstein. 2013. Cork Boolean Library. https://github.com/gilbo/cork Accessed January 19, 2022.Google Scholar
4. Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. In Proceedings of the Symposium on Geometry Processing (Berlin, Germany) (SGP ’09). Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 1269–1278.Google Scholar
5. Marcel Campen and Leif Kobbelt. 2010. Exact and robust (self-) intersections for polygonal meshes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 397–406.Google Scholar
6. Gianmarco Cherchi, Marco Livesu, Riccardo Scateni, and Marco Attene. 2020. Fast and Robust Mesh Arrangements Using Floating-Point Arithmetic. ACM Trans. Graph. 39, 6, Article 250 (Nov. 2020), 16 pages.Google ScholarDigital Library
7. Salles Viana Gomes de Magalhães, W Randolph Franklin, and Marcus Vinícius Alvim Andrade. 2020. An Efficient and Exact Parallel Algorithm for Intersecting Large 3-D Triangular Meshes Using Arithmetic Filters. Computer-Aided Design 120 (2020), 102801.Google ScholarDigital Library
8. 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
9. Torbjörn Granlund and the GMP development team. 2020. GNU MP: The GNU Multiple Precision Arithmetic Library. https://gmplib.org/.Google Scholar
10. Peter Hachenberger, Lutz Kettner, and Kurt Mehlhorn. 2007. Boolean operations on 3D selective Nef complexes: Data structure, algorithms, optimized implementation and experiments. Computational Geometry 38, 1–2 (2007), 64–99.Google ScholarDigital Library
11. Alec Jacobson, Ladislav Kavan, and Olga Sorkine. 2013. Robust Inside-Outside Segmentation using Generalized Winding Numbers. ACM Trans. Graph. 32, 4 (2013).Google ScholarDigital Library
12. Bruce Naylor, John Amanatides, and William Thibault. 1990. Merging BSP trees yields polyhedral set operations. ACM Siggraph Computer Graphics 24, 4 (1990), 115–124.Google ScholarDigital Library
13. Walter Nef. 1978. Beiträge zur Theorie der Polyeder: Mit Anwendungen in der Computergraphik. (1978).Google Scholar
14. Julius Nehring-Wirxel, Philip Trettner, and Leif Kobbelt. 2021. Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs. Computer-Aided Design 135 (2021), 103015.Google ScholarCross Ref
15. Dairon Sanchez. 2021. Bar Chair Round 01. https://polyhaven.com/a/bar_chair_round_01 Accessed January 19, 2022.Google Scholar
16. Jonathan Richard Shewchuk. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (1997), 305–363.Google ScholarCross Ref
17. Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. 2016. Mesh Arrangements for Solid Geometry. ACM Trans. Graph. 35, 4, Article 39 (July 2016), 15 pages.Google ScholarDigital Library
18. Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).Google Scholar