{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T18:30:27Z","timestamp":1775845827217,"version":"3.50.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008530","name":"European Regional Development Fund","doi-asserted-by":"publisher","award":["EFRE-0500038"],"award-info":[{"award-number":["EFRE-0500038"]}],"id":[{"id":"10.13039\/501100008530","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3528223.3530181","type":"journal-article","created":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T21:06:27Z","timestamp":1658523987000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["EMBER"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3706-2259","authenticated-orcid":false,"given":"Philip","family":"Trettner","sequence":"first","affiliation":[{"name":"Shaped Code GmbH, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2194-2227","authenticated-orcid":false,"given":"Julius","family":"Nehring-Wirxel","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7880-9470","authenticated-orcid":false,"given":"Leif","family":"Kobbelt","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}]}],"member":"320","published-online":{"date-parts":[[2022,7,22]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2015.06.016"},{"key":"e_1_2_2_3_1","volume-title":"Cork Boolean Library. https:\/\/github.com\/gilbo\/cork Accessed","author":"Bernstein Gilbert","year":"2022","unstructured":"Gilbert Bernstein. 2013. Cork Boolean Library. https:\/\/github.com\/gilbo\/cork Accessed January 19, 2022."},{"key":"e_1_2_2_4_1","volume-title":"Linear Booleans. In Proceedings of the Symposium on Geometry Processing","author":"Bernstein Gilbert","year":"2009","unstructured":"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."},{"key":"e_1_2_2_5_1","volume-title":"Computer Graphics Forum","author":"Campen Marcel","unstructured":"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."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417818"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2019.102801"},{"key":"e_1_2_2_8_1","volume-title":"QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558","author":"Douze Matthijs","year":"2017","unstructured":"Matthijs Douze, Jean-S\u00e9bastien Franco, and Bruno Raffin. 2017. QuickCSG: Fast Arbitrary Boolean Combinations of N Solids. arXiv preprint arXiv:1706.01558 (2017)."},{"key":"e_1_2_2_9_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library. https:\/\/gmplib.org\/.","author":"Granlund Torbj\u00f6rn","year":"2020","unstructured":"Torbj\u00f6rn Granlund and the GMP development team. 2020. GNU MP: The GNU Multiple Precision Arithmetic Library. https:\/\/gmplib.org\/."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2006.11.009"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97892"},{"key":"e_1_2_2_13_1","unstructured":"Walter Nef. 1978. Beitr\u00e4ge zur Theorie der Polyeder: Mit Anwendungen in der Computergraphik. (1978)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2021.103015"},{"key":"e_1_2_2_15_1","volume-title":"Bar Chair Round 01. https:\/\/polyhaven.com\/a\/bar_chair_round_01 Accessed","author":"Sanchez Dairon","year":"2022","unstructured":"Dairon Sanchez. 2021. Bar Chair Round 01. https:\/\/polyhaven.com\/a\/bar_chair_round_01 Accessed January 19, 2022."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"},{"key":"e_1_2_2_18_1","first-page":"3D","article-title":"Thingi10K","volume":"10","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv preprint arXiv:1605.04797 (2016).","journal-title":"A Dataset of"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530181","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3528223.3530181","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:49Z","timestamp":1750186969000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530181"}},"subtitle":["exact mesh booleans via efficient &amp; robust local arrangements"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.1145\/3528223.3530181"],"URL":"https:\/\/doi.org\/10.1145\/3528223.3530181","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"2022-07-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}