{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T14:16:28Z","timestamp":1778854588125,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"USC Annenberg Graduate Fellowship"},{"name":"the National Science Foundation","award":["CAREER-1055035, IIS-1422869"],"award-info":[{"award-number":["CAREER-1055035, IIS-1422869"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>Self-intersecting, or nearly self-intersecting, meshes are commonly found in 2D and 3D computer graphics practice. Self-intersections occur, for example, in the process of artist manual work, as a by-product of procedural methods for mesh generation, or due to modeling errors introduced by scanning equipment. If the space bounded by such inputs is meshed naively, the resulting mesh joins (\"glues\") self-overlapping parts, precluding efficient further modeling and animation of the underlying geometry. Similarly, near self-intersections force the simulation algorithm to employ an unnecessarily detailed mesh to separate the nearly self-intersecting regions. Our work addresses both of these challenges, by giving an algorithm to generate an \"un-glued\" simulation mesh, of arbitrary user-chosen resolution, that properly accounts for self-intersections and near self-intersections. In order to achieve this result, we study the mathematical concept of immersion, and give a deterministic and constructive algorithm to determine if the input self-intersecting triangle mesh is the boundary of an immersion. For near self-intersections, we give a robust algorithm to properly duplicate mesh elements and correctly embed the underlying geometry into the mesh element copies. Both the self-intersections and near self-intersections are combined into one algorithm that permits successful meshing at arbitrary resolution. Applications of our work include volumetric shape editing, physically based simulation and animation, and volumetric weight and geodesic distance computation on self-intersecting inputs.<\/jats:p>","DOI":"10.1145\/3197517.3201327","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T15:56:23Z","timestamp":1533052583000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Immersion of self-intersecting solids and surfaces"],"prefix":"10.1145","volume":"37","author":[{"given":"Yijing","family":"Li","sequence":"first","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jernej","family":"Barbi\u010d","sequence":"additional","affiliation":[{"name":"University of Southern California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"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","DOI":"10.1016\/j.gmod.2014.09.002"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.49"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882357"},{"key":"e_1_2_2_5_1","unstructured":"Jernej Barbi\u010d Yijing Li Bohan Wang and Danyong Zhao. 2018. Vega FEM Library 4.0. (2018). http:\/\/www.jernejbarbic.com\/vega.  Jernej Barbi\u010d Yijing Li Bohan Wang and Danyong Zhao. 2018. Vega FEM Library 4.0. (2018). http:\/\/www.jernejbarbic.com\/vega."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01609.x"},{"key":"e_1_2_2_7_1","unstructured":"CGAL. 2018. Computational Geometry Algorithms Library. (2018). http:\/\/www.cgal.org  CGAL. 2018. Computational Geometry Algorithms Library. (2018). http:\/\/www.cgal.org"},{"key":"e_1_2_2_8_1","unstructured":"Keenan Crane. 2017. 3D Model Repository. (2017). http:\/\/www.cs.cmu.edu\/~kmcrane\/Projects\/ModelRepository  Keenan Crane. 2017. 3D Model Repository. (2017). http:\/\/www.cs.cmu.edu\/~kmcrane\/Projects\/ModelRepository"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496789"},{"key":"e_1_2_2_10_1","volume-title":"Computational Topology","author":"Erickson Jeff","year":"2009","unstructured":"Jeff Erickson . 2009. Computational Topology ; Cell Complexes. In Course Notes, University of Illinois at Urbana-Champaign. http:\/\/jeffe.cs.illinois.edu\/teaching\/comptop\/ 2009 \/notes\/cell-complexes.pdf Jeff Erickson. 2009. Computational Topology; Cell Complexes. In Course Notes, University of Illinois at Urbana-Champaign. http:\/\/jeffe.cs.illinois.edu\/teaching\/comptop\/2009\/notes\/cell-complexes.pdf"},{"key":"e_1_2_2_11_1","volume-title":"Extending Immersions into the Sphere. arXiv preprint arXiv.1012.4923","author":"Frisch Dennis","year":"2010","unstructured":"Dennis Frisch . 2010. Extending Immersions into the Sphere. arXiv preprint arXiv.1012.4923 ( 2010 ). Dennis Frisch. 2010. Extending Immersions into the Sphere. arXiv preprint arXiv.1012.4923 (2010)."},{"key":"e_1_2_2_12_1","volume-title":"VMV'04","author":"Heidelberger B.","unstructured":"B. Heidelberger , M. Teschner , R. Keiser , M. M\u00fcller , and M. H. Gross . 2004. Consistent penetration depth estimation for deformable collision response . In VMV'04 . 339--346. B. Heidelberger, M. Teschner, R. Keiser, M. M\u00fcller, and M. H. Gross. 2004. Consistent penetration depth estimation for deformable collision response. In VMV'04. 339--346."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.09.012"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661280"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461916"},{"key":"e_1_2_2_17_1","unstructured":"A Jacobson D Panozzo C Sch\u00fcller O Diamanti Q Zhou N Pietroni etal 2013b. libigl: A simple C++ geometry processing library. (2013).  A Jacobson D Panozzo C Sch\u00fcller O Diamanti Q Zhou N Pietroni et al. 2013b. libigl: A simple C++ geometry processing library. (2013)."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/CAD\/Graphics.2011.31"},{"key":"e_1_2_2_19_1","volume-title":"Enriching Triangle Mesh Animations With Physically Based Simulation","author":"Li Yijing","year":"2016","unstructured":"Yijing Li , Hongyi Xu , and Jernej Barbi\u010d . 2016. Enriching Triangle Mesh Animations With Physically Based Simulation . IEEE Trans. on Visualization and Computer Graphics ( 2016 ). Yijing Li, Hongyi Xu, and Jernej Barbi\u010d. 2016. Enriching Triangle Mesh Animations With Physically Based Simulation. IEEE Trans. on Visualization and Computer Graphics (2016)."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818100"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015734"},{"key":"e_1_2_2_22_1","volume-title":"Symposium on Computer Animation (SCA).","author":"Molino Neil","year":"2003","unstructured":"Neil Molino , Robert Bridson , and Ronald Fedkiw . 2003 a. Tetrahedral mesh generation for deformable bodies . In Symposium on Computer Animation (SCA). Neil Molino, Robert Bridson, and Ronald Fedkiw. 2003a. Tetrahedral mesh generation for deformable bodies. In Symposium on Computer Animation (SCA)."},{"key":"e_1_2_2_23_1","volume-title":"12th Int. Meshing Roundtable. 103--114.","author":"Molino Neil","unstructured":"Neil Molino , Robert Bridson , Joseph Teran , and Ron Fedkiw . 2003b. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra . In 12th Int. Meshing Roundtable. 103--114. Neil Molino, Robert Bridson, Joseph Teran, and Ron Fedkiw. 2003b. A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In 12th Int. Meshing Roundtable. 103--114."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2013.08.037"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2425333.2425369"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2021164.2021170"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531358"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03224.x"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12181"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/73833.73838"},{"key":"e_1_2_2_32_1","volume-title":"Arbitrary Cutting of Deformable Tetrahedralized Objects. In Symp. on Computer Animation (SCA). 73--80","author":"Sifakis Eftychios","year":"2007","unstructured":"Eftychios Sifakis , Kevin Der , and Ronald Fedkiw . 2007 . Arbitrary Cutting of Deformable Tetrahedralized Objects. In Symp. on Computer Animation (SCA). 73--80 . Eftychios Sifakis, Kevin Der, and Ronald Fedkiw. 2007. Arbitrary Cutting of Deformable Tetrahedralized Objects. In Symp. on Computer Animation (SCA). 73--80."},{"key":"e_1_2_2_33_1","volume-title":"Symp. on Geometry processing","volume":"4","author":"Sorkine Olga","year":"2007","unstructured":"Olga Sorkine and Marc Alexa . 2007 . As-rigid-as-possible surface modeling . In Symp. on Geometry processing , Vol. 4 . 109--116. Olga Sorkine and Marc Alexa. 2007. As-rigid-as-possible surface modeling. In Symp. on Geometry processing, Vol. 4. 109--116."},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/360767.360802"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.42"},{"key":"e_1_2_2_36_1","volume-title":"Symposium on Computer Animation (SCA). 77--85","author":"Wang Y.","unstructured":"Y. Wang , C. Jiang , C. Schroeder , and J. Teran . 2014. An adaptive virtual node algorithm with robust mesh cutting . In Symposium on Computer Animation (SCA). 77--85 . Y. Wang, C. Jiang, C. Schroeder, and J. Teran. 2014. An adaptive virtual node algorithm with robust mesh cutting. In Symposium on Computer Animation (SCA). 77--85."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601227"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531382"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360646"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461968"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925901"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201327","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201327","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3197517.3201327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:44Z","timestamp":1750210784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3197517.3201327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3197517.3201327"],"URL":"https:\/\/doi.org\/10.1145\/3197517.3201327","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}