{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T09:25:28Z","timestamp":1780392328224,"version":"3.54.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T00:00:00Z","timestamp":1606435200000},"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":[[2020,12,31]]},"abstract":"<jats:p>\n            We introduce a novel algorithm to transform any generic set of triangles in 3D space into a well-formed simplicial complex. Intersecting elements in the input are correctly identified, subdivided, and connected to arrange a valid configuration, leading to a topologically sound partition of the space into piece-wise linear cells. Our approach does not require the exact coordinates of intersection points to calculate the resulting complex. We represent any intersection point as an unevaluated combination of input vertices. We then extend the recently introduced concept of\n            <jats:italic>indirect predicates<\/jats:italic>\n            [Attene 2020] to define all the necessary geometric tests that, by construction, are both exact and efficient since they fully exploit the floating-point hardware. This design makes our method robust and guaranteed correct, while being virtually as fast as non-robust floating-point based implementations. Compared with existing robust methods, our algorithm offers a number of advantages: it is much faster, has a better memory layout, scales well on extremely challenging models, and allows fully exploiting modern multi-core hardware with a parallel implementation. We thoroughly tested our method on thousands of meshes, concluding that it consistently outperforms prior art. We also demonstrate its usefulness in various applications, such as computing efficient mesh booleans, Minkowski sums, and volume meshes.\n          <\/jats:p>","DOI":"10.1145\/3414685.3417818","type":"journal-article","created":{"date-parts":[[2020,11,27]],"date-time":"2020-11-27T21:51:05Z","timestamp":1606513865000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Fast and robust mesh arrangements using floating-point arithmetic"],"prefix":"10.1145","volume":"39","author":[{"given":"Gianmarco","family":"Cherchi","sequence":"first","affiliation":[{"name":"University of Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Livesu","sequence":"additional","affiliation":[{"name":"IMATI - CNR, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Riccardo","family":"Scateni","sequence":"additional","affiliation":[{"name":"University of Cagliari, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"IMATI - CNR, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,11,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323004"},{"key":"e_1_2_2_2_1","volume-title":"A lightweight approach to repair polygon meshes. The Visual Computer","author":"Attene Marco","year":"2010","unstructured":"Marco Attene . 2010. A lightweight approach to repair polygon meshes. The Visual Computer ( 2010 ), 1393--1406. Marco Attene. 2010. A lightweight approach to repair polygon meshes. The Visual Computer (2010), 1393--1406."},{"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":"ImatiSTL - Fast and Reliable Mesh Processing with a Hybrid Kernel. LNCS Transactions on Computational Science XXIX","author":"Attene Marco","year":"2017","unstructured":"Marco Attene . 2017. ImatiSTL - Fast and Reliable Mesh Processing with a Hybrid Kernel. LNCS Transactions on Computational Science XXIX ( 2017 ), 86--96. Marco Attene. 2017. ImatiSTL - Fast and Reliable Mesh Processing with a Hybrid Kernel. LNCS Transactions on Computational Science XXIX (2017), 86--96."},{"key":"e_1_2_2_5_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 ). Marco Attene. 2018. As-exact-as-possible repair of unprintable STL files. Rapid Prototyping Journal (2018)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431214"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2015.06.016"},{"key":"e_1_2_2_9_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, AirelaVille, Switzerland, Switzerland, 1269--1278. http:\/\/dl.acm.org\/citation.cfm?id=1735603.1735606 Gilbert Bernstein and Don Fussell. 2009. Fast, Exact, Linear Booleans. In Proceedings of the Symposium on Geometry Processing (SGP '09). Eurographics Association, AirelaVille, Switzerland, Switzerland, 1269--1278. http:\/\/dl.acm.org\/citation.cfm?id=1735603.1735606"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00878.x"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276884.276903"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01770.x"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2019.102801"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2018.30"},{"key":"e_1_2_2_16_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 . 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_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161015"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236463.1236468"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925900"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.2003.10487592"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9219-6"},{"key":"e_1_2_2_22_1","volume-title":"Fast Tetrahedral Meshing in the Wild. arXiv preprint arXiv:1908.03581","author":"Hu Yixin","year":"2019","unstructured":"Yixin Hu , Teseo Schneider , Bolun Wang , Denis Zorin , and Daniele Panozzo . 2019. Fast Tetrahedral Meshing in the Wild. arXiv preprint arXiv:1908.03581 ( 2019 ). Yixin Hu, Teseo Schneider, Bolun Wang, Denis Zorin, and Daniele Panozzo. 2019. Fast Tetrahedral Meshing in the Wild. arXiv preprint arXiv:1908.03581 (2019)."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201353"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_25_1","unstructured":"Wonhyung Jung Hayong Shin and Byoung Kyu Choi. 2003. Self-intersection Removal in Triangular Mesh Offsetting.  Wonhyung Jung Hayong Shin and Byoung Kyu Choi. 2003. Self-intersection Removal in Triangular Mesh Offsetting."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2015.10.004"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jlap.2004.07.006"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-59958-7_4"},{"key":"e_1_2_2_29_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. 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_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.10.003"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3204458"},{"key":"e_1_2_2_32_1","volume-title":"SGP 2014 Graduate School.","author":"Panozzo Daniele","year":"2014","unstructured":"Daniele Panozzo and Alec Jacobson . 2014 . LIBIGL: A C++ library for geometry processing without a mesh data structure . SGP 2014 Graduate School. Daniele Panozzo and Alec Jacobson. 2014. LIBIGL: A C++ library for geometry processing without a mesh data structure. SGP 2014 Graduate School."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2010.09.003"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392374"},{"key":"e_1_2_2_35_1","volume-title":"Yuming Ma, Mitchell Dembowski, and Alec Jacobson.","author":"Sell\u00e1n Silvia","year":"2019","unstructured":"Silvia Sell\u00e1n , Herng Yi Cheng , Yuming Ma, Mitchell Dembowski, and Alec Jacobson. 2019 . Solid Geometry Processing on Deconstructed Domains. In Computer Graphics Forum, Vol. 38 . Wiley Online Library , 564--579. Silvia Sell\u00e1n, Herng Yi Cheng, Yuming Ma, Mitchell Dembowski, and Alec Jacobson. 2019. Solid Geometry Processing on Deconstructed Domains. In Computer Graphics Forum, Vol. 38. Wiley Online Library, 564--579."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2015.04.006"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629697"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/81617.81622"},{"key":"e_1_2_2_40_1","unstructured":"The CGAL Project. 2019. CGAL User and Reference Manual (4.14.1 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.14.1\/Manual\/packages.html  The CGAL Project. 2019. CGAL User and Reference Manual (4.14.1 ed.). CGAL Editorial Board. https:\/\/doc.cgal.org\/4.14.1\/Manual\/packages.html"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392426"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3054740"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"},{"key":"e_1_2_2_44_1","volume-title":"Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797","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 ). Qingnan Zhou and Alec Jacobson. 2016. Thingi10k: A dataset of 10,000 3d-printing models. arXiv preprint arXiv:1605.04797 (2016)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417818","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3414685.3417818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:14Z","timestamp":1750197794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3414685.3417818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,27]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3414685.3417818"],"URL":"https:\/\/doi.org\/10.1145\/3414685.3417818","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,27]]},"assertion":[{"value":"2020-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}