{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T16:18:54Z","timestamp":1782317934365,"version":"3.54.5"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T00:00:00Z","timestamp":1597190400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100011199","name":"European Research Council","doi-asserted-by":"publisher","award":["694515"],"award-info":[{"award-number":["694515"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREEER-1652515, OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091"],"award-info":[{"award-number":["CAREEER-1652515, OAC-1835712, OIA-1937043, CHS-1908767, CHS-1901091"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key Research and Development Program of China","award":["2018YFB1107402"],"award-info":[{"award-number":["2018YFB1107402"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            We introduce a new technique to check containment of a triangle within an envelope built around a given triangle mesh. While existing methods conservatively check containment within a Euclidean envelope, our approach makes use of a non-Euclidean envelope where containment can be checked both\n            <jats:italic toggle=\"yes\">exactly<\/jats:italic>\n            and\n            <jats:italic toggle=\"yes\">efficiently.<\/jats:italic>\n            Exactness is crucial to address major robustness issues in existing geometry processing algorithms, which we demonstrate by integrating our technique in two surface triangle remeshing algorithms and a volumetric tetrahedral meshing algorithm. We provide a quantitative comparison of our method and alternative algorithms, showing that our solution, in addition to being exact, is also more efficient. Indeed, while containment within large envelopes can be checked in a comparable time, we show that our algorithm outperforms alternative methods when the envelope becomes thin.\n          <\/jats:p>","DOI":"10.1145\/3386569.3392426","type":"journal-article","created":{"date-parts":[[2020,8,12]],"date-time":"2020-08-12T11:44:27Z","timestamp":1597232667000},"update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Exact and efficient polyhedral envelope containment check"],"prefix":"10.1145","volume":"39","author":[{"given":"Bolun","family":"Wang","sequence":"first","affiliation":[{"name":"Beihang University, China and New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Teseo","family":"Schneider","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixin","family":"Hu","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"Italian National Research Council, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"New York University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,8,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90042-X"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2010.04.004"},{"key":"e_1_2_2_3_1","volume-title":"Linear Booleans. In Proceedings of the Symposium on Geometry Processing (SGP '09)","author":"Bernstein Gilbert","year":"2009","unstructured":"Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. In Proceedings of the Symposium on Geometry Processing (SGP '09). Eurographics Association, Goslar, DEU, 1269--1278."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"H. Borouchaki and P. J. Frey. 2005. Simplification of surface mesh using Hausdorff envelope.","DOI":"10.1016\/j.cma.2004.11.016"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276903"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Marcel Campen and Leif Kobbelt. 2010a. Exact and Robust (Self-)Intersections for Polygonal Meshes. Comput. Graph. Forum 29 (05 2010) 397--406.","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2019.05.019"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/868963"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00236"},{"key":"e_1_2_2_11_1","volume-title":"Simplification Envelopes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '96)","author":"Cohen Jonathan","year":"1996","unstructured":"Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, Frederick Brooks, and William Wright. 1996. Simplification Envelopes. In Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '96). Association for Computing Machinery, New York, NY, USA, 119--128."},{"key":"e_1_2_2_12_1","volume-title":"Procs. of 5th Workshop Algorithm Eng. Exper. 37--44","author":"Devillers Olivier","year":"2003","unstructured":"Olivier Devillers and Sylvain Pion. 2003. Efficient exact geometric predicates for Delaunay triangulations. In Procs. of 5th Workshop Algorithm Eng. Exper. 37--44."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/231731.231735"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.766"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661235"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '97)","author":"Garland Michael","unstructured":"Michael Garland and Paul S. Heckbert. 1997. Surface Simplification Using Quadric Error Metrics. In Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH '97). ACM Press\/Addison-Wesley Publishing Co., USA, 209--216."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(93)90023-3"},{"key":"e_1_2_2_19_1","unstructured":"Ga\u00ebl Guennebaud Beno\u00eet Jacob et al. 2010. Eigen v3."},{"key":"e_1_2_2_20_1","volume-title":"Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. Algorithmica 55, 2 (01","author":"Hachenberger Peter","year":"2009","unstructured":"Peter Hachenberger. 2009. Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces. Algorithmica 55, 2 (01 Oct 2009), 329--345."},{"key":"e_1_2_2_21_1","unstructured":"Michael Hemmer Susan Hert Sylvain Pion and Stefan Schirra. 2019. Number Types. In CGAL User and Reference Manual (5.0 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/5.0\/Manual\/packages.html#PkgNumberTypes"},{"key":"e_1_2_2_22_1","volume-title":"Association for Computing Machinery","author":"Hoppe Hugues","unstructured":"Hugues Hoppe. 1996. Progressive Meshes. Association for Computing Machinery, Inc., 24."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2016.2632720"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323011"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392385"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2441714"},{"key":"e_1_2_2_28_1","unstructured":"Wonhyung Jung Hayong Shin and Byoung Kyu Choi. 2003. Self-intersection Removal in Triangular Mesh Offsetting."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(92)90077-9"},{"key":"e_1_2_2_30_1","unstructured":"Bruno L\u00e9vy. 2019. Geogram. http:\/\/alice.loria.fr\/index.php\/software\/4-library\/75-geogram.html."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlap.2004.07.006"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766950"},{"key":"e_1_2_2_33_1","unstructured":"S. Loriot Martin Skrodzki. 2019. https:\/\/github.com\/martinskrodzki\/cgal"},{"key":"e_1_2_2_34_1","volume-title":"FPG: A code generator for fast and certified geometric predicates. In Real Numbers and Computers. 47--60.","author":"Meyer Andreas","year":"2008","unstructured":"Andreas Meyer and Sylvain Pion. 2008. FPG: A code generator for fast and certified geometric predicates. In Real Numbers and Computers. 47--60."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2010.09.003"},{"key":"e_1_2_2_36_1","volume-title":"The Boost C++ Libraries","author":"Schling Boris","unstructured":"Boris Schling. 2011. The Boost C++ Libraries. XML Press."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-013-0331-0"},{"key":"e_1_2_2_39_1","volume-title":"Interactive Hausdorf Distance Computation for General Polygonal Models. In ACM SIGGRAPH 2009 Papers (SIGGRAPH '09)","author":"Tang Min","unstructured":"Min Tang, Minkyoung Lee, and Young J. Kim. 2009. Interactive Hausdorf Distance Computation for General Polygonal Models. In ACM SIGGRAPH 2009 Papers (SIGGRAPH '09). ACM, New York, NY, USA, Article 74, 9 pages."},{"key":"e_1_2_2_40_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. CoRR abs\/1605.04797 (2016). arXiv:1605.04797","journal-title":"A Dataset of"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3386569.3392426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T05:35:12Z","timestamp":1750829712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3386569.3392426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3386569.3392426"],"URL":"https:\/\/doi.org\/10.1145\/3386569.3392426","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,12]]},"assertion":[{"value":"2020-08-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}