{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T02:43:42Z","timestamp":1774925022085,"version":"3.50.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T00:00:00Z","timestamp":1587427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2016414 2011471"],"award-info":[{"award-number":["2016414 2011471"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>We propose a framework for the interactive simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform (MAT), a high-fidelity volumetric approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semireduced projective dynamics formulation, which well captures high-frequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are enabled by the local constraints projection, which should not be aggressively reduced, and only apply model reduction at the global stage. From the collision detection (CD)\/collision culling (CC) perspective, MAT is geometrically versatile using linear-interpolated spheres (i.e., the so-called medial primitives (MPs)) to approximate the boundary of the input model. The intersection test between two MPs is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which returns the deepest penetration between a pair of intersecting MPs. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on the GPU within a few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system produces convincing animations with all of the collisions\/self-collisions well handled at an interactive rate.<\/jats:p>","DOI":"10.1145\/3384515","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T09:51:07Z","timestamp":1588585867000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Medial Elastics"],"prefix":"10.1145","volume":"39","author":[{"given":"Lei","family":"Lan","sequence":"first","affiliation":[{"name":"Xiamen University 8 University of New Mexico, Albuquerque, NM"}]},{"given":"Ran","family":"Luo","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM"}]},{"given":"Marco","family":"Fratarcangeli","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Gothenburg, Sweden"}]},{"given":"Weiwei","family":"Xu","sequence":"additional","affiliation":[{"name":"State Ley Lab of CAD 8 CG, Zhejiang University, Hangzhou, China"}]},{"given":"Huamin","family":"Wang","sequence":"additional","affiliation":[{"name":"Ohio State University, Columbus, OH"}]},{"given":"Xiaohu","family":"Guo","sequence":"additional","affiliation":[{"name":"University of Texas at Dallas, Richardson, Texas"}]},{"given":"Junfeng","family":"Yao","sequence":"additional","affiliation":[{"name":"Xiamen University, Xiamen, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7645-5931","authenticated-orcid":false,"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Clemson University 8 University of New Mexico, Albuquerque, NM"}]}],"member":"320","published-online":{"date-parts":[[2020,4,21]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Surface reconstruction by Voronoi filtering. Discrete 8 Computational Geometry 22, 4","author":"Amenta Nina","year":"1999"},{"key":"e_1_2_2_2_1","volume-title":"James","author":"An Steven S.","year":"2008"},{"key":"e_1_2_2_3_1","first-page":"2","volume-title":"Proceedings of the ACM in Computer Graphics and Interactive Techniques 2","author":"Angles Baptiste","year":"2019"},{"key":"e_1_2_2_4_1","volume-title":"Practical Optimization: Algorithms and Engineering Applications","author":"Antoniou Andreas","year":"2007"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1997.0536"},{"key":"e_1_2_2_6_1","volume-title":"Computer Graphics and Interactive Techniques","author":"Baraff David"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1272690.1272714"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778818"},{"key":"e_1_2_2_9_1","volume-title":"Real-time large-deformation substructuring. ACM Transactions on Graphics 30","author":"Barbi\u010d Jernej","year":"2011"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073300"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2567943"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1080\/10867651.1997.10487480"},{"key":"e_1_2_2_13_1","volume-title":"Models for the Perception of Speech and Visual Forms","author":"Blum Harry"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201387"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566623"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566622"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2006.04.012"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.13"},{"key":"e_1_2_2_20_1","unstructured":"Andreas Fabri and Monique Teillaud. 2011. CGAL\u2014The computational geometry algorithms library. In 10e colloque national en calcul des structures. 6.  Andreas Fabri and Monique Teillaud. 2011. CGAL\u2014The computational geometry algorithms library. In 10e colloque national en calcul des structures. 6."},{"key":"e_1_2_2_21_1","volume-title":"SIGGRAPH Asia 2013 Technical Briefs","author":"Faraj Noura"},{"key":"e_1_2_2_22_1","volume-title":"Pai","author":"Faure Fran\u00e7ois","year":"2011"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_2_24_1","volume-title":"SIGGRAPH Asia 2018 Courses","author":"Fratarcangeli Marco"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130879"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944855"},{"key":"e_1_2_2_27_1","volume-title":"Computer Graphics and Interactive Techniques","author":"Gottschalk Stefan"},{"key":"e_1_2_2_28_1","volume-title":"Proceedings of Graphics Interface","volume":"3","author":"Hauser Kris K.","year":"2003"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.466717"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015735"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00861.x"},{"key":"e_1_2_2_33_1","volume-title":"James","author":"Kim Theodore","year":"2009"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203203"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.00278"},{"key":"e_1_2_2_36_1","volume-title":"Proceedings of the 2002 ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201902)","author":"Kry Paul G."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2753755"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2783335"},{"key":"e_1_2_2_40_1","volume-title":"Unified simulation of elastic rods, shells, and solids. ACM Transactions on Graphics 29","author":"Martin Sebastian","year":"2010"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/378456.378528"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_2_43_1","volume-title":"Proceedings of the ACM SIGGRAPH\/Eurographics Symposium on Computer Animation (SCA\u201916)","author":"Narain Rahul"},{"key":"e_1_2_2_45_1","volume-title":"Preserving topology and elasticity for embedded deformable models. ACM Transactions on Graphics 28","author":"Nesme Matthieu","year":"2009"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2010.01769.x"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/74334.74355"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/325165.325242"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2343483.2343501"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.254"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2448080"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203188"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601181"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508384"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898350"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980226"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13356"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3026479"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818089"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.12"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/585740.585761"},{"key":"e_1_2_2_65_1","volume-title":"Geometric Data Structures for Computer Graphics","author":"Zachmann Gabriel"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185594"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3384515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3384515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:12Z","timestamp":1750199592000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3384515"}},"subtitle":["Efficient and Collision-Ready Deformation via Medial Axis Transform"],"short-title":[],"issued":{"date-parts":[[2020,4,21]]},"references-count":66,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3384515"],"URL":"https:\/\/doi.org\/10.1145\/3384515","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,21]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}