{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T19:23:09Z","timestamp":1776108189000,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,7,11]],"date-time":"2017-07-11T00:00:00Z","timestamp":1499731200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-11-29917"],"award-info":[{"award-number":["CMMI-11-29917"]}],"id":[{"id":"10.13039\/100000001","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":[[2016,7,11]]},"abstract":"<jats:p>\n                    Many high-level geometry processing tasks rely on low-level constructive solid geometry operations. Though trivial for implicit representations, boolean operations are notoriously difficult to execute robustly for explicit boundary representations. Existing methods for 3D triangle meshes fall short in one way or another. Some methods are fast but fail to produce closed, self-intersection free output. Other methods are robust but place prohibitively strict assumptions on the input, e.g., no hollow cavities, non-manifold edges or self-intersections. We propose a systematic recipe for conducting a family of exact constructive solid geometry operations. The two-stage method makes no general position assumptions and does not resort to numerical perturbation. The method is\n                    <jats:italic toggle=\"yes\">variadic<\/jats:italic>\n                    , operating on any number of input meshes. This generalizes\n                    <jats:italic toggle=\"yes\">unary<\/jats:italic>\n                    mesh-repair operations, classic\n                    <jats:italic toggle=\"yes\">binary<\/jats:italic>\n                    boolean differencing, and\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -ary operations such as finding all regions inside at least\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    out of\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    inputs. We demonstrate the superior effectiveness and robustness of our method on a dataset of 10,000 \"real-world\" meshes from a popular online repository. To encourage development, validation, and comparison, we release both our code and dataset to the public.\n                  <\/jats:p>","DOI":"10.1145\/2897824.2925901","type":"journal-article","created":{"date-parts":[[2016,7,11]],"date-time":"2016-07-11T12:04:33Z","timestamp":1468238673000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":132,"title":["Mesh arrangements for solid geometry"],"prefix":"10.1145","volume":"35","author":[{"given":"Qingnan","family":"Zhou","sequence":"first","affiliation":[{"name":"New York University"}]},{"given":"Eitan","family":"Grinspun","sequence":"additional","affiliation":[{"name":"Columbia University"}]},{"given":"Denis","family":"Zorin","sequence":"additional","affiliation":[{"name":"New York University"}]},{"given":"Alec","family":"Jacobson","sequence":"additional","affiliation":[{"name":"Columbia University"}]}],"member":"320","published-online":{"date-parts":[[2016,7,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-010-0416-3"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","unstructured":"Attene M. 2014. Direct repair of self-intersecting meshes. Graphical Models. 10.1016\/j.gmod.2014.09.002","DOI":"10.1016\/j.gmod.2014.09.002"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Banerjee R. P. and Rossignac J. R. 1996. Topologically exact evaluation of polyhedra defined in CSG with loose primitives. Comput. Graph. Forum.","DOI":"10.1111\/1467-8659.1540205"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","unstructured":"Barki H. Guennebaud G. and Foufou S. 2015. Exact robust and efficient regularized booleans on general 3d meshes. Computers and Mathematics with Applications. 10.1016\/j.camwa.2015.06.016","DOI":"10.1016\/j.camwa.2015.06.016"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735606"},{"key":"e_1_2_2_6_1","unstructured":"Bernstein G. 2013. Cork boolean library. https:\/\/github.com\/gilbo\/cork."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/53477.53486"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Campen M. and Kobbelt L. 2010. Exact and robust (self-) intersections for polygonal meshes. Comput. Graph. Forum.","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Campen M. and Kobbelt L. 2010. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Comput. Graph. Forum.","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Campen M. Attene M. and Kobbelt L. 2012. A practical guide to polygon mesh repairing. Eurographics Tutorial.","DOI":"10.1145\/2431211.2431214"},{"key":"e_1_2_2_11_1","volume-title":"Carve: An efficient and robust library for boolean operations on polyhedra","author":"CARVE","year":"2014","unstructured":"CARVE, 2014. Carve: An efficient and robust library for boolean operations on polyhedra. http:\/\/carve-csg.com\/."},{"key":"e_1_2_2_12_1","unstructured":"CGAL 2015. Cgal Computational Geometry Algorithms Library. http:\/\/www.cgal.org."},{"key":"e_1_2_2_13_1","volume-title":"Tech. Rep. 01121419","author":"Douze M.","year":"2015","unstructured":"Douze, M., Franco, J.-S., and Raffin, B. 2015. QuickCSG: Arbitrary and faster boolean combinations of n solids. Tech. Rep. 01121419, Inria Research Centre Grenoble, Rhone-Alpes."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","unstructured":"Edelsbrunner H. and M\u00fccke E. P. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph.. 10.1145\/77635.77639","DOI":"10.1145\/77635.77639"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Fortune S. 1997. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete Comput. Geom.","DOI":"10.1145\/276884.276897"},{"key":"e_1_2_2_16_1","volume-title":"Proc. ESA.","author":"Granados M.","unstructured":"Granados, M., Hachenberger, P., Hert, S., Kettner, L., Mehlhorn, K., and Seel, M. 2003. Boolean operations on 3d selective nef complexes: Data structure, algorithms, and implementation. In Proc. ESA."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","unstructured":"Jacobson A. Kavan L. and Sorkine-Hornung O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph.. 10.1145\/2461912.2461916","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Jacobson A. Panozzo D. et al. 2016. libigl: A simple C++ geometry processing library. http:\/\/libigl.github.io\/libigl\/.","DOI":"10.1145\/3134472.3134497"},{"key":"e_1_2_2_19_1","unstructured":"Mei G. and Tipper J. C. 2013. Simple and robust boolean operations for triangulated surfaces. arXiv preprint arXiv:1308.4434."},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Milenkovic V. J. and Nackman L. R. 1990. Finding compact coordinate representations for polygons and polyhedra.","DOI":"10.1145\/98524.98579"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","unstructured":"Museth K. Breen D. E. Whitaker R. T. and Barr A. H. 2002. Level set surface editing operators. ACM Trans. Graph.. 10.1145\/566654.566585","DOI":"10.1145\/566654.566585"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/97879.97892"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Pavic D. Campen M. and Kobbelt L. 2010. Hybrid Booleans. Comput. Graph. Forum.","DOI":"10.1111\/j.1467-8659.2009.01545.x"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12181"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","unstructured":"Sacks E. and Milenkovic V. 2014. Robust cascading of operations on polyhedra. Computer-Aided Design (Tech. Note). 10.1016\/j.cad.2013.08.035","DOI":"10.1016\/j.cad.2013.08.035"},{"key":"e_1_2_2_26_1","volume-title":"Proc. of the IEEE.","author":"Sugihara K.","unstructured":"Sugihara, K., and Iri, M. 1992. Construction of the Voronoi diagram for one million generators in single-precision arithmetic. Proc. of the IEEE."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37421"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057464"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.106"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","unstructured":"Xu S. and Keyser J. 2013. Fast and robust booleans on polyhedra. Computer-Aided Design. 10.1016\/j.cad.2012.10.036","DOI":"10.1016\/j.cad.2012.10.036"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-011-0571-1"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","unstructured":"Zhou Q. Panetta J. and Zorin D. 2013. Worst-case structural analysis. ACM Trans. Graph.. 10.1145\/2461912.2461967","DOI":"10.1145\/2461912.2461967"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925901","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897824.2925901","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2897824.2925901","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:50Z","timestamp":1763458070000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2897824.2925901"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,11]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,11]]}},"alternative-id":["10.1145\/2897824.2925901"],"URL":"https:\/\/doi.org\/10.1145\/2897824.2925901","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,11]]},"assertion":[{"value":"2016-07-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}