{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T05:38:37Z","timestamp":1770529117679,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T00:00:00Z","timestamp":1690329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["1764071"],"award-info":[{"award-number":["1764071"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>We introduce a method for efficiently computing the exact shortest path to the boundary of a mesh from a given internal point in the presence of self-intersections. We provide a formal definition of shortest boundary paths for self-intersecting objects and present a robust algorithm for computing the actual shortest boundary path. The resulting method offers an effective solution for collision and self-collision handling while simulating deformable volumetric objects, using fast simulation techniques that provide no guarantees on collision resolution. Our evaluation includes complex self-collision scenarios with a large number of active contacts, showing that our method can successfully handle them by introducing a relatively minor computational overhead.<\/jats:p>","DOI":"10.1145\/3592136","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T15:47:45Z","timestamp":1690386465000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Shortest Path to Boundary for Self-Intersecting Meshes"],"prefix":"10.1145","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5819-3453","authenticated-orcid":false,"given":"He","family":"Chen","sequence":"first","affiliation":[{"name":"Kahlert School of Computing, University of Utah, Salt Lake City, UT, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9493-1684","authenticated-orcid":false,"given":"Elie","family":"Diaz","sequence":"additional","affiliation":[{"name":"Kahlert School of Computing, University of Utah, Salt Lake City, UT, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0122-4159","authenticated-orcid":false,"given":"Cem","family":"Yuksel","sequence":"additional","affiliation":[{"name":"Kahlert School of Computing, University of Utah, Salt Lake City, UT, United States of America"},{"name":"Roblox, San Mateo, CA, United States of America"}]}],"member":"320","published-online":{"date-parts":[[2023,7,26]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1833349.1778819"},{"key":"e_1_2_2_2_1","volume-title":"Compact tetrahedralization-based acceleration structures for ray tracing. Journal of Visualization","author":"Aman Aytek","year":"2022","unstructured":"Aytek Aman, Serkan Demirci, and U\u011fur G\u00fcd\u00fckbay. 2022. Compact tetrahedralization-based acceleration structures for ray tracing. Journal of Visualization (2022), 1--13."},{"key":"e_1_2_2_3_1","volume-title":"Exact geodesics and shortest paths on polyhedral surfaces","author":"Balasubramanian Mukund","year":"2008","unstructured":"Mukund Balasubramanian, Jonathan R Polimeni, and Eric L Schwartz. 2008. Exact geodesics and shortest paths on polyhedral surfaces. IEEE transactions on pattern analysis and machine intelligence 31, 6 (2008), 1006--1016."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192168"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620310309"},{"key":"e_1_2_2_6_1","unstructured":"Jan Bender Matthias M\u00fcller and Miles Macklin. 2015. Position-Based Simulation Methods in Computer Graphics.. In Eurographics (tutorials). 8."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.606761"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_2_11_1","volume-title":"A Survey of Algorithms for Geodesic Paths and Distances. arXiv preprint arXiv:2007.10430","author":"Crane Keenan","year":"2020","unstructured":"Keenan Crane, Marco Livesu, Enrico Puppo, and Yipeng Qin. 2020. A Survey of Algorithms for Geodesic Paths and Distances. arXiv preprint arXiv:2007.10430 (2020)."},{"key":"e_1_2_2_12_1","volume-title":"Penalty force for coupling materials with Coulomb friction","author":"Ding Ounan","year":"2019","unstructured":"Ounan Ding and Craig Schroeder. 2019. Penalty force for coupling materials with Coulomb friction. IEEE transactions on visualization and computer graphics 26, 7 (2019), 2443--2455."},{"key":"e_1_2_2_13_1","volume-title":"A fast and stable penalty method for rigid body simulation","author":"Drumwright Evan","year":"2007","unstructured":"Evan Drumwright. 2007. A fast and stable penalty method for rigid body simulation. IEEE transactions on visualization and computer graphics 14, 1 (2007), 231--240."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-6240-8_10"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2001.973379"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/166117.166157"},{"key":"e_1_2_2_18_1","volume-title":"Realistic animation of rigid bodies. ACM Siggraph computer graphics 22, 4","author":"Hahn James K","year":"1988","unstructured":"James K Hahn. 1988. Realistic animation of rigid bodies. ACM Siggraph computer graphics 22, 4 (1988), 299--308."},{"key":"e_1_2_2_19_1","first-page":"339","article-title":"Consistent penetration depth estimation for deformable collision response","volume":"4","author":"Heidelberger Bruno","year":"2004","unstructured":"Bruno Heidelberger, Matthias Teschner, Richard Keiser, Matthias M\u00fcller, and Markus H Gross. 2004. Consistent penetration depth estimation for deformable collision response.. In VMV, Vol. 4. 339--346.","journal-title":"VMV"},{"key":"e_1_2_2_20_1","volume-title":"GRAPP 2008-3rd International Conference on Computer Graphics Theory and Applications. INSTICC, 293--299","author":"Hermann Everton","year":"2008","unstructured":"Everton Hermann, Fran\u00e7ois Faure, and Bruno Raffin. 2008. Ray-traced collision detection for deformable bodies. In GRAPP 2008-3rd International Conference on Computer Graphics Theory and Applications. INSTICC, 293--299."},{"key":"e_1_2_2_22_1","volume-title":"On a penalty formulation for contact-impact problems. Computers & structures 48, 2","author":"Hun\u011bk I","year":"1993","unstructured":"I Hun\u011bk. 1993. On a penalty formulation for contact-impact problems. Computers & structures 48, 2 (1993), 193--203."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2077341.2077346"},{"key":"e_1_2_2_24_1","volume-title":"Rigid body collision response. Vectors 1000, 2","author":"Kavan Ladislav","year":"2003","unstructured":"Ladislav Kavan. 2003. Rigid body collision response. Vectors 1000, 2 (2003)."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730202"},{"key":"e_1_2_2_26_1","volume-title":"Computer Graphics Forum","author":"Lagae Ares","unstructured":"Ares Lagae and Philip Dutr\u00e9. 2008. Accelerating ray tracing using constrained tetrahe-dralizations. In Computer Graphics Forum, Vol. 27. Wiley Online Library, 1303--1312."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530064"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3528223.3530069","article-title":"Penetration-free projective dynamics on the GPU","volume":"41","author":"Lan Lei","year":"2022","unstructured":"Lei Lan, Guanqun Ma, Yin Yang, Changxi Zheng, Minchen Li, and Chenfanfu Jiang. 2022b. Penetration-free projective dynamics on the GPU. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1--16.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275055"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.11.005"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384538"},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Miles Macklin and Matthias Muller. 2021. A Constraint-based Formulation of Stable Neo-Hookean Materials. In Motion Interaction and Games. 1--7.","DOI":"10.1145\/3487983.3488289"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5220\/0006131002360243"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2384796.2384832"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964932"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199436"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818100"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378528"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_43_1","unstructured":"Carol O'Sullivan and John Dingliana. 1999. Real-time collision detection and response using sphere-trees. (1999)."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198555.1198754"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/54852.378524"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129216"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/VIS49827.2021.9623298"},{"key":"e_1_2_2_48_1","volume-title":"Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG) 24, 3","author":"Surazhsky Vitaly","year":"2005","unstructured":"Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM transactions on graphics (TOG) 24, 3 (2005), 553--560."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601181"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37427"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209887"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601199"},{"key":"e_1_2_2_53_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2185520.2185593","article-title":"Adaptive image-based intersection volume","volume":"31","author":"Wang Bin","year":"2012","unstructured":"Bin Wang, Fran\u00e7ois Faure, and Dinesh K Pai. 2012. Adaptive image-based intersection volume. ACM Transactions on Graphics (TOG) 31, 4 (2012), 1--9.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_54_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3460775","article-title":"A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection","volume":"40","author":"Wang Bolun","year":"2021","unstructured":"Bolun Wang, Zachary Ferguson, Teseo Schneider, Xin Jiang, Marco Attene, and Daniele Panozzo. 2021. A Large-scale Benchmark and an Inclusion-based Algorithm for Continuous Collision Detection. ACM Transactions on Graphics (TOG) 40, 5 (2021), 1--16.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_56_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\/3592136","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592136","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3592136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:46Z","timestamp":1750178266000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3592136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,26]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8]]}},"alternative-id":["10.1145\/3592136"],"URL":"https:\/\/doi.org\/10.1145\/3592136","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,26]]},"assertion":[{"value":"2023-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}