{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T13:31:46Z","timestamp":1780493506988,"version":"3.54.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T00:00:00Z","timestamp":1669766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>Boolean operations are among the most used paradigms to create and edit digital shapes. Despite being conceptually simple, the computation of mesh Booleans is notoriously challenging. Main issues come from numerical approximations that make the detection and processing of intersection points inconsistent and unreliable, exposing implementations based on floating point arithmetic to many kinds of degeneracy and failure. Numerical methods based on rational numbers or exact geometric predicates have the needed robustness guarantees, that are achieved at the cost of increased computation times that, as of today, has always restricted the use of robust mesh Booleans to offline applications. We introduce an algorithm for Boolean operations with robustness guarantees that is capable of operating at interactive frame rates on meshes with up to 200K triangles. We evaluate our tool thoroughly, considering not only interactive applications but also batch processing of large collections of meshes, processing of huge meshes containing millions of elements and variadic Booleans of hundreds of shapes altogether. In all these experiments, we consistently outperform prior robust floating point methods by at least one order of magnitude.<\/jats:p>","DOI":"10.1145\/3550454.3555460","type":"journal-article","created":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T21:19:07Z","timestamp":1669843147000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Interactive and Robust Mesh Booleans"],"prefix":"10.1145","volume":"41","author":[{"given":"Gianmarco","family":"Cherchi","sequence":"first","affiliation":[{"name":"University of Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabio","family":"Pellacini","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"CNR IMATI, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Livesu","sequence":"additional","affiliation":[{"name":"CNR IMATI, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,30]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Volume-aware design of composite molds. ACM Transactions on Graphics","author":"Alderighi Thomas","year":"2019","unstructured":"Thomas Alderighi, Luigi Malomo, Daniela Giorgi, Bernd Bickel, Paolo Cignoni, and Nico Pietroni. 2019. Volume-aware design of composite molds. ACM Transactions on Graphics (2019)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201381"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2014.09.002"},{"key":"e_1_2_2_4_1","volume-title":"As-exact-as-possible repair of unprintable STL files. Rapid Prototyping Journal","author":"Attene Marco","year":"2018","unstructured":"Marco Attene. 2018. As-exact-as-possible repair of unprintable STL files. Rapid Prototyping Journal (2018)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201337"},{"key":"e_1_2_2_7_1","unstructured":"Audrey Baxter and Lorelei Wrigh. 2019. Ray-Traced Constructive Solid Geometry. (2019)."},{"key":"e_1_2_2_8_1","unstructured":"Gilbert Bernstein. 2013. Cork Boolean Library. https:\/\/github.com\/gilbo\/cork."},{"key":"e_1_2_2_9_1","volume-title":"Computer Graphics Forum","author":"Bernstein Gilbert","unstructured":"Gilbert Bernstein and Don Fussell. 2009. Fast, exact, linear booleans. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 1269--1278."},{"key":"e_1_2_2_10_1","unstructured":"Blender Doc. 2022. Blender. https:\/\/docs.blender.org\/manual\/en\/latest\/modeling\/modifiers\/generate\/booleans.html"},{"key":"e_1_2_2_11_1","volume-title":"Computer Graphics Forum","author":"Campen Marcel","unstructured":"Marcel Campen and Leif Kobbelt. 2010a. Exact and robust (self-) intersections for polygonal meshes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 397--406."},{"key":"e_1_2_2_12_1","volume-title":"Computer Graphics Forum","author":"Campen Marcel","unstructured":"Marcel Campen and Leif Kobbelt. 2010b. Polygonal boundary evaluation of minkowski sums and swept volumes. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 1613--1622."},{"key":"e_1_2_2_13_1","unstructured":"Shouxin Chen Ming Chen and Shenglian Lu. 2022. A Real Time Visual Boolean Operation on Triangular Mesh Models. (2022)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.34"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201342"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2019.102801"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.30"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","unstructured":"O. Devillers and F. P. Preparata. 1998. A Probabilistic Analysis of the Power of Arithmetic Filters. Discrete & Computational Geometry 20 4 (01 Dec 1998) 523--547. 10.1007\/PL00009400","DOI":"10.1007\/PL00009400"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480564"},{"key":"e_1_2_2_21_1","volume-title":"Geometric Tools (2008)","author":"Eberly David","year":"2008","unstructured":"David Eberly. 2008. Triangulation by ear clipping. Geometric Tools (2008), 2002--2005."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2018.10.010"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009480"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925900"},{"key":"e_1_2_2_25_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3. http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_2_26_1","first-page":"11","article-title":"TetGen, a Delaunay-based quality tetrahedral mesh generator","volume":"41","author":"Hang Si","year":"2015","unstructured":"Si Hang. 2015. TetGen, a Delaunay-based quality tetrahedral mesh generator. ACM Trans. Math. Softw 41, 2 (2015), 11.","journal-title":"ACM Trans. Math. Softw"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392385"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_29_1","volume-title":"Computer Graphics Forum","author":"Jacobson Alec","unstructured":"Alec Jacobson. 2017. Generalized matryoshka: Computational design of nesting objects. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 27--35."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Alec Jacobson Daniele Panozzo et al. 2018. libigl: A simple C++ geometry processing library. https:\/\/libigl.github.io\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_33_1","unstructured":"Bruno Levy. 2022. Graphite. https:\/\/github.com\/BrunoLevy\/GraphiteThree."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-59958-7_4"},{"key":"e_1_2_2_35_1","volume-title":"Deterministic Linear Time Constrained Triangulation using Simplified Earcut","author":"Livesu Marco","year":"2021","unstructured":"Marco Livesu, Gianmarco Cherchi, Riccardo Scateni, and Marco Attene. 2021. Deterministic Linear Time Constrained Triangulation using Simplified Earcut. IEEE Transactions on Visualization and Computer Graphics (2021)."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3140001"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459748"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.5987"},{"key":"e_1_2_2_39_1","unstructured":"Maya Doc. 2022. AutoDesk. https:\/\/knowledge.autodesk.com\/support\/maya\/learn-explore\/caas\/CloudHelp\/cloudhelp\/2020\/ENU\/Maya-Modeling\/files\/GUID-302821C5-343C-4F2B-8228-C5333896B207-htm.html"},{"key":"e_1_2_2_40_1","volume-title":"Simple and robust boolean operations for triangulated surfaces. arXiv preprint arXiv:1308.4434","author":"Mei Gang","year":"2013","unstructured":"Gang Mei and John C Tipper. 2013. Simple and robust boolean operations for triangulated surfaces. arXiv preprint arXiv:1308.4434 (2013)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.10.003"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1997.10487468"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3204458"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2021.103015"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356542"},{"key":"e_1_2_2_46_1","first-page":"1","article-title":"Topological computing of arrangements with (co) chains","volume":"7","author":"Paoluzzi Alberto","year":"2020","unstructured":"Alberto Paoluzzi, Vadim Shapiro, Antonio DiCarlo, Francesco Furiani, Giulio Martella, and Giorgio Scorzelli. 2020. Topological computing of arrangements with (co) chains. ACM Transactions on Spatial Algorithms and Systems (TSAS) 7, 1 (2020), 1--29.","journal-title":"ACM Transactions on Spatial Algorithms and Systems (TSAS)"},{"key":"e_1_2_2_47_1","volume-title":"Finite Boolean Algebras for Solid Geometry using Julia's Sparse Arrays. arXiv preprint arXiv:1910.11848","author":"Paoluzzi Alberto","year":"2019","unstructured":"Alberto Paoluzzi, Vadim Shapiro, Antonio DiCarlo, Giorgio Scorzelli, and Elia Onofri. 2019. Finite Boolean Algebras for Solid Geometry using Julia's Sparse Arrays. arXiv preprint arXiv:1910.11848 (2019)."},{"key":"e_1_2_2_48_1","volume-title":"Eurographics\/ACM SIGGRAPH Workshop Implicit Surfaces' 99","author":"Pasko Alexander","year":"1999","unstructured":"Alexander Pasko, V Adzhiev, R Cartwright, E Fausett, A Ossipov, and V Savchenko. 1999. HyperFun project: A framework for collaborative multidimensional F-rep modeling. In Eurographics\/ACM SIGGRAPH Workshop Implicit Surfaces' 99. 59--69."},{"key":"e_1_2_2_49_1","volume-title":"Computer Graphics Forum","author":"Pavi\u0107 Darko","unstructured":"Darko Pavi\u0107, Marcel Campen, and Leif Kobbelt. 2010. Hybrid booleans. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 75--87."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2010.09.003"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1925059.1925089"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459780"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2018.03.021"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014497"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.04.006"},{"key":"e_1_2_2_57_1","volume-title":"Symposium on Geometry processing","volume":"4","author":"Sorkine Olga","year":"2007","unstructured":"Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symposium on Geometry processing, Vol. 4. 109--116."},{"key":"e_1_2_2_58_1","first-page":"380","article-title":"A solid modelling system free from topological inconsistency","volume":"12","author":"Sugihara Kokichi","year":"1989","unstructured":"Kokichi Sugihara, Masao Iri, et al. 1989. A solid modelling system free from topological inconsistency. Journal of Information Processing 12, 4 (1989), 380--393.","journal-title":"Journal of Information Processing"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356543"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530181"},{"key":"e_1_2_2_61_1","volume-title":"Computer Graphics Forum","author":"Ureta Francisca Gil","unstructured":"Francisca Gil Ureta, Chelsea Tymms, and Denis Zorin. 2016. Interactive modeling of mechanical objects. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 145--155."},{"key":"e_1_2_2_62_1","volume-title":"Computer Graphics Forum","author":"Wyvill Brian","unstructured":"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."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.10.036"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3054740"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203198"},{"key":"e_1_2_2_66_1","volume-title":"Fast Updates for Least-Squares Rotational Alignment. Computer Graphics Forum","author":"Zhang Jiayi Eris","year":"2021","unstructured":"Jiayi Eris Zhang, Alec Jacobson, and Marc Alexa. 2021. Fast Updates for Least-Squares Rotational Alignment. Computer Graphics Forum (2021)."},{"key":"e_1_2_2_67_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2897824.2925901","article-title":"Mesh arrangements for solid geometry","volume":"35","author":"Zhou Qingnan","year":"2016","unstructured":"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.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1605.04797"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555460","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3550454.3555460","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:11Z","timestamp":1750182551000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3550454.3555460"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,30]]},"references-count":68,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1145\/3550454.3555460"],"URL":"https:\/\/doi.org\/10.1145\/3550454.3555460","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,30]]},"assertion":[{"value":"2022-11-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}