{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T09:54:45Z","timestamp":1762509285764,"version":"3.41.2"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"name":"NSF","award":["OAC-2411349 and IIS-2313156"],"award-info":[{"award-number":["OAC-2411349 and IIS-2313156"]}]},{"name":"MUR-PRIN Project","award":["2022YB4NRS"],"award-info":[{"award-number":["2022YB4NRS"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,10,31]]},"abstract":"<jats:p>We propose a conservative algorithm to test the geometrical validity of simplicial (triangles, tetrahedra), tensor product (quadrilaterals, hexahedra), and mixed (prisms) elements of arbitrary polynomial order as they deform linearly within a time interval.<\/jats:p>\n          <jats:p>Our algorithm uses a combination of adaptive B\u00e9zier refinement and bisection search to determine if, when, and where the Jacobian determinant of an element\u2019s polynomial geometric map becomes negative in the transition from one configuration to another. In elastodynamic simulation, our algorithm guarantees that the system remains physically valid during the entire trajectory, not only at discrete time steps. Unlike previous approaches, physical validity is preserved even when our method is implemented using floating point arithmetic. Hence, our algorithm is only slightly slower than existing non-conservative methods while providing guarantees and while being an easy drop-in replacement for current validity tests.<\/jats:p>\n          <jats:p>To prove the practical effectiveness of our algorithm, we demonstrate its use in a high-order Incremental Potential Contact (IPC) elastodynamic simulator and experimentally show that it prevents invalid, simulation-breaking configurations that would otherwise occur using non-conservative methods.<\/jats:p>","DOI":"10.1145\/3745763","type":"journal-article","created":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T05:49:26Z","timestamp":1750916966000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["High-Order Continuous Geometrical Validity"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2805-306X","authenticated-orcid":false,"given":"Federico","family":"Sichetti","sequence":"first","affiliation":[{"name":"University of Genoa","place":["Genova, Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6529-4694","authenticated-orcid":false,"given":"Zizhou","family":"Huang","sequence":"additional","affiliation":[{"name":"Computer Science, New York University","place":["New York, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9012-7245","authenticated-orcid":false,"given":"Marco","family":"Attene","sequence":"additional","affiliation":[{"name":"IMATI CNR Genova","place":["Genova, Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7733-5501","authenticated-orcid":false,"given":"Denis","family":"Zorin","sequence":"additional","affiliation":[{"name":"Computer Science, New York University","place":["New York, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9780-5283","authenticated-orcid":false,"given":"Enrico","family":"Puppo","sequence":"additional","affiliation":[{"name":"University of Genoa","place":["Genova, Italy"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1183-2454","authenticated-orcid":false,"given":"Daniele","family":"Panozzo","sequence":"additional","affiliation":[{"name":"Computer Science, New York University","place":["New York, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,9]]},"reference":[{"issue":"3","key":"e_1_3_4_2_1","first-page":"19","article-title":"A recursive algebraic coloring technique for hardware-efficient symmetric sparse matrix-vector multiplication","volume":"7","author":"Alappat Christie","year":"2020","unstructured":"Christie Alappat, Achim Basermann, Alan R. Bishop, Holger Fehske, Georg Hager, Olaf Schenk, Jonas Thies, and Gerhard Wellein. 2020. A recursive algebraic coloring technique for hardware-efficient symmetric sparse matrix-vector multiplication. ACM Transactions on Parallel Computing 7, 3, Article 19 (June2020), 37 pages.","journal-title":"ACM Transactions on Parallel Computing"},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/fld.3965"},{"key":"e_1_3_4_4_1","article-title":"Indirect Predicates Library","author":"Attene M.","year":"2019","unstructured":"M. Attene. 2019. Indirect Predicates Library. Retrieved from https:\/\/github.com\/MarcoAttene\/Indirect_Predicates. (2019).","journal-title":"Retrieved from https:\/\/github.com\/MarcoAttene\/Indirect_Predicates"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102856"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567943"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1147615"},{"key":"e_1_3_4_8_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-030-43736-7_1","article-title":"State-of-the-art sparse direct solvers","author":"Bollh\u00f6fer Matthias","year":"2020","unstructured":"Matthias Bollh\u00f6fer, Olaf Schenk, Radim Janalik, Steve Hamm, and Kiran Gullapalli. 2020. State-of-the-art sparse direct solvers. Parallel Algorithms in Computational Science and Engineering, Ananth Grama and Ahmed H. Sameh (Eds.). (2020), 3\u201333.","journal-title":"Parallel Algorithms in Computational Science and Engineering"},{"key":"e_1_3_4_9_1","first-page":"165","volume-title":"Proceedings of the 14th annual symposium on Computational geometry","author":"Br\u00f6nnimann H.","year":"1998","unstructured":"H. Br\u00f6nnimann, C. Burnikel, and S. Pion. 1998. Interval arithmetic yields efficient dynamic filters for computational geometry. In Proceedings of the 14th annual symposium on Computational geometryACM, New York, NY, USA, 165\u2013174."},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530076"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470749081"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/99.660313"},{"issue":"3","key":"e_1_3_4_13_1","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0010-4485(00)00120-2","article-title":"Towards curvilinear meshing in 3D: The case of quadratic simplices","volume":"33","author":"Dey S.","year":"2001","unstructured":"S. Dey, R. M. O\u2019Bara, and M. S. Shephard. 2001. Towards curvilinear meshing in 3D: The case of quadratic simplices. Computer-Aided Design 33, 3 (2001), 199\u2013209.","journal-title":"Computer-Aided Design"},{"issue":"1","key":"e_1_3_4_14_1","first-page":"B50\u2013B68","article-title":"The target-matrix optimization paradigm for high-order meshes","volume":"41","author":"Dobrev V.","year":"2019","unstructured":"V. Dobrev, P. Knupp, T. Kolev, K. Mittal, and V. Tomov. 2019. The target-matrix optimization paradigm for high-order meshes. SIAM Jou. Sci. Comp. 41, 1 (2019), B50\u2013B68.","journal-title":"SIAM Jou. Sci. Comp."},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2023.3295656"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459757"},{"key":"e_1_3_4_17_1","volume-title":"Curves and Surfaces for CAGD: A Practical Guide (5th ed.)","author":"Farin G.","year":"2001","unstructured":"G. Farin. 2001. Curves and Surfaces for CAGD: A Practical Guide (5th ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA."},{"key":"e_1_3_4_18_1","article-title":"IPC Toolkit","author":"Ferguson Zachary","year":"2020","unstructured":"Zachary Ferguson et\u00a0al. 2020. IPC Toolkit. Retrieved from https:\/\/ipc-sim.github.io\/ipc-toolkit\/. (2020). Retrieved from https:\/\/ipc-sim.github.io\/ipc-toolkit\/","journal-title":"Retrieved from https:\/\/ipc-sim.github.io\/ipc-toolkit\/"},{"key":"e_1_3_4_19_1","volume-title":"Proceedings of the ACM SIGGRAPH 2023 Conference Proceedings (SIGGRAPH\u201923)","author":"Ferguson Z.","year":"2023","unstructured":"Z. Ferguson, P. Jain, D. Zorin, T. Schneider, and D. Panozzo. 2023. High-order incremental potential contact for elastodynamic simulation on curved meshes. In Proceedings of the ACM SIGGRAPH 2023 Conference Proceedings (SIGGRAPH\u201923). Association for Computing Machinery, New York, NY, USA, Article 77, 11 pages."},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_3_4_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-014-0370-1"},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","unstructured":"P. L. George and H. Borouchaki. 2014. Validity of lagrange (B\u00e9zier) and rational B\u00e9zier quads of degree 2. 99 8 (2014) 611\u2013632. DOI:10.1002\/nme.4696","DOI":"10.1002\/nme.4696"},{"key":"e_1_3_4_23_1","first-page":"15","volume-title":"The Generation of Valid Curvilinear Meshes","author":"Geuzaine C.","year":"2015","unstructured":"C. Geuzaine, A. Johnen, J. Lambrechts, J. F. Remacle, and T. Toulorge. 2015. The Generation of Valid Curvilinear Meshes. Springer International Publishing, Cham, 15\u201339."},{"key":"e_1_3_4_24_1","article-title":"Gaol: NOT Just Another Interval Library","author":"Goualard F.","year":"2005","unstructured":"F. Goualard. 2005. Gaol: NOT Just Another Interval Library. Retrieved from https:\/\/sourceforge.net\/projects\/gaol\/. (2005).","journal-title":"Retrieved from https:\/\/sourceforge.net\/projects\/gaol\/"},{"key":"e_1_3_4_25_1","volume-title":"GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.)","author":"Granlund T.","year":"2012","unstructured":"T. Granlund and the GMP development team. 2012. GNU MP: The GNU Multiple Precision Arithmetic Library (5.0.5 ed.). Retrieved from http:\/\/gmplib.org\/"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3643028"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3657648"},{"issue":"4","key":"e_1_3_4_28_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3450626.3459840","article-title":"Bijective and coarse high-order tetrahedral meshes","volume":"40","author":"Jiang Z.","year":"2021","unstructured":"Z. Jiang, Z. Zhang, Y. Hu, T. Schneider, D. Zorin, and D. Panozzo. 2021a. Bijective and coarse high-order tetrahedral meshes. ACM Trans. Graph. 40, 4 (2021), 1\u201316.","journal-title":"ACM Trans. Graph."},{"issue":"4","key":"e_1_3_4_29_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3450626.3459840","article-title":"Bijective and coarse high-order tetrahedral meshes","volume":"40","author":"Jiang Z.","year":"2021","unstructured":"Z. Jiang, Z. Zhang, Y. Hu, T. Schneider, D. Zorin, and D. Panozzo. 2021b. Bijective and coarse high-order tetrahedral meshes. ACM Trans. Graph. 40, 4 (2021), 1\u201316.","journal-title":"ACM Trans. Graph."},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2018.03.001"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2012.08.051"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2633467.2633565"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2017.09.809"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0207(20001210)49:10<1295::AID-NME993>3.0.CO;2-W"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02307379"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85521-7_6"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530064"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592104"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530069"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459753"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141885.1141893"},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_3_4_43_1","unstructured":"Minchen Li Zachary Ferguson Teseo Schneider Timothy Langlois Denis Zorin Daniele Panozzo Chenfanfu Jiang and Danny M. Kaufman. 2023. Convergent Incremental Potential Contact. arXiv:2307.15908. Retrieved from https:\/\/arxiv.org\/abs\/2307.15908. (2023)."},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610548.3618157"},{"key":"e_1_3_4_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cma.2021.114350"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641519.3657449"},{"issue":"1","key":"e_1_3_4_48_1","article-title":"FEBio: Finite elements for biomechanics","volume":"134","author":"Maas S. A.","year":"2012","unstructured":"S. A. Maas, B. J. Ellis, G. A. Ateshian, and J. A. Weiss. 2012. FEBio: Finite elements for biomechanics. Jou. of Biomechanical Engineering 134, 1 (2012), 01005-1\u201301005-10.","journal-title":"Jou. of Biomechanical Engineering"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2020.102862"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14074"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cmpb.2023.107938"},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.103"},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.09.009"},{"key":"e_1_3_4_54_1","volume-title":"Advanced Compiler Design and Implementation","author":"Muchnick Steven S.","year":"1997","unstructured":"Steven S. Muchnick. 1997. Advanced Compiler Design and Implementation. Morgan Kaufmann, Oxford, England."},{"key":"e_1_3_4_55_1","volume-title":"Non-Linear Elastic Deformations","author":"Ogden R. W.","year":"2013","unstructured":"R. W. Ogden. 2013. Non-Linear Elastic Deformations. Dover Publications. Retrieved from https:\/\/books.google.com\/books?id=52XDAgAAQBAJ"},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766937"},{"key":"e_1_3_4_57_1","article-title":"The boost C++ libraries","author":"Schling B.","year":"2011","unstructured":"B. Schling. 2011. The boost C++ libraries. XML Press (2011).","journal-title":"XML Press"},{"key":"e_1_3_4_58_1","article-title":"PolyFEM","author":"Schneider T.","year":"2019","unstructured":"T. Schneider, J. Dumas, X. Gao, D. Zorin, and D. Panozzo. 2019. PolyFEM. Retrieved from https:\/\/polyfem.github.io\/. (2019).","journal-title":"Retrieved from https:\/\/polyfem.github.io\/"},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3508372"},{"key":"e_1_3_4_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3641519.3657490"},{"key":"e_1_3_4_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009321"},{"key":"e_1_3_4_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766947"},{"key":"e_1_3_4_63_1","first-page":"121","article-title":"Interval analysis for computer graphics","author":"Snyder J.","year":"1992","unstructured":"J. Snyder. 1992. Interval analysis for computer graphics. ACM SIGGRAPH 26, 2 (1992), 121\u2013130.","journal-title":"ACM SIGGRAPH"},{"key":"e_1_3_4_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485895.2485914"},{"key":"e_1_3_4_65_1","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/978-3-031-30445-3_35","volume-title":"Proceedings of the Parallel Processing and Applied Mathematics","author":"Tang X.","year":"2023","unstructured":"X. Tang, Z. Ferguson, T. Schneider, D. Zorin, S. Kamil, and D. Panozzo. 2023. A cross-platform benchmark for interval computation libraries. In Proceedings of the Parallel Processing and Applied Mathematics, R. Wyrzykowski, J. Dongarra, E. Deelman, and K. Karczewski (Eds.). Springer International Publishing, Cham, 415\u2013427."},{"key":"e_1_3_4_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2013.07.022"},{"issue":"17","key":"e_1_3_4_67_1","doi-asserted-by":"crossref","first-page":"1649","DOI":"10.1016\/j.cma.2011.01.014","article-title":"Nondegeneracy tests for hexahedral cells","volume":"200","author":"Ushakova O. V.","year":"2011","unstructured":"O. V. Ushakova. 2011. Nondegeneracy tests for hexahedral cells. Computer Methods in Applied Mechanics and Engineering 200, 17\u201320 (2011), 1649\u20131658.","journal-title":"Computer Methods in Applied Mechanics and Engineering"},{"key":"e_1_3_4_68_1","unstructured":"S. Vavasis. 2003. A bernstein-bezier sufficient condition for invertibility of polynomial mapping functions. (2003)."},{"key":"e_1_3_4_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_3_4_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3478513.3480561"},{"key":"e_1_3_4_71_1","unstructured":"Inc. Wolfram Research. 2023. Mathematica Version 13.3. (2023). Retrieved from https:\/\/www.wolfram.com\/mathematicaChampaign IL."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3745763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,9]],"date-time":"2025-07-09T12:20:36Z","timestamp":1752063636000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3745763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,9]]},"references-count":70,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10,31]]}},"alternative-id":["10.1145\/3745763"],"URL":"https:\/\/doi.org\/10.1145\/3745763","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2025,7,9]]},"assertion":[{"value":"2024-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-25","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}