{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T23:47:37Z","timestamp":1769039257209,"version":"3.49.0"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"Department of Energy","doi-asserted-by":"crossref","award":["ORNL 4000171342"],"award-info":[{"award-number":["ORNL 4000171342"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2016414;2011471;2153851;2153863;2023780"],"award-info":[{"award-number":["2016414;2011471;2153851;2153863;2023780"]}],"id":[{"id":"10.13039\/100000001","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":[[2022,7]]},"abstract":"<jats:p>We present a GPU algorithm for deformable simulation. Our method offers good computational efficiency and penetration-free guarantee at the same time, which are not common with existing techniques. The main idea is an algorithmic integration of projective dynamics (PD) and incremental potential contact (IPC). PD is a position-based simulation framework, favored for its robust convergence and convenient implementation. We show that PD can be employed to handle the variational optimization with the interior point method e.g., IPC. While conceptually straightforward, this requires a dedicated rework over the collision resolution and the iteration modality to avoid incorrect collision projection with improved numerical convergence. IPC exploits a barrier-based formulation, which yields an infinitely large penalty when the constraint is on the verge of being violated. This mechanism guarantees intersection-free trajectories of deformable bodies during the simulation, as long as they are apart at the rest configuration. On the downside, IPC brings a large amount of nonlinearity to the system, making PD slower to converge. To mitigate this issue, we propose a novel GPU algorithm named A-Jacobi for faster linear solve at the global step of PD. A-Jacobi is based on Jacobi iteration, but it better harvests the computation capacity on modern GPUs by lumping several Jacobi steps into a single iteration. In addition, we also re-design the CCD root finding procedure by using a new minimum-gradient Newton algorithm. Those saved time budgets allow more iterations to accommodate stiff IPC barriers so that the result is both realistic and collision-free. Putting together, our algorithm simulates complicated models of both solids and shells on the GPU at an interactive rate or even in real time.<\/jats:p>","DOI":"10.1145\/3528223.3530069","type":"journal-article","created":{"date-parts":[[2022,7,22]],"date-time":"2022-07-22T21:06:27Z","timestamp":1658523987000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":40,"title":["Penetration-free projective dynamics on the GPU"],"prefix":"10.1145","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5743-9987","authenticated-orcid":false,"given":"Lei","family":"Lan","sequence":"first","affiliation":[{"name":"Clemson University &amp; University of Utah"}]},{"given":"Guanqun","family":"Ma","sequence":"additional","affiliation":[{"name":"Clemson University &amp; University of Utah"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Clemson University and University of Utah &amp; Timestep Inc."}]},{"given":"Changxi","family":"Zheng","sequence":"additional","affiliation":[{"name":"Columbia University &amp; Tencent Pixel Lab"}]},{"given":"Minchen","family":"Li","sequence":"additional","affiliation":[{"name":"University of California &amp; TimeStep Inc."}]},{"given":"Chenfanfu","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of California &amp; TimeStep Inc."}]}],"member":"320","published-online":{"date-parts":[[2022,7,22]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Complementarity and nondegeneracy in semidefinite programming. Mathematical programming 77, 1","author":"Alizadeh Farid","year":"1997","unstructured":"Farid Alizadeh, Jean-Pierre A Haeberly, and Michael L Overton. 1997. Complementarity and nondegeneracy in semidefinite programming. Mathematical programming 77, 1 (1997), 111--128."},{"key":"e_1_2_2_2_1","volume-title":"Sparse matrix techniques","author":"Axelsson Owe","unstructured":"Owe Axelsson. 1977. Solution of linear systems of equations: iterative methods. In Sparse matrix techniques. Springer, 1--51."},{"key":"e_1_2_2_3_1","volume-title":"Real-time large-deformation substructuring. ACM transactions on graphics (TOG) 30, 4","author":"Barbi\u010d Jernej","year":"2011","unstructured":"Jernej Barbi\u010d and Yili Zhao. 2011. Real-time large-deformation substructuring. ACM transactions on graphics (TOG) 30, 4 (2011), 1--8."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073300"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566623"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566622"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545268"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.13"},{"key":"e_1_2_2_11_1","unstructured":"Jinhyun Choo Yidong Zhao Yupeng Jiang Minchen Li Chenfanfu Jiang and Kenichi Soga. 2021. A barrier method for frictional contact on embedded interfaces. arXiv:2107.05814 [math.NA]"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3221308.3221497"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Richard W Cottle Jong-Shi Pang and Richard E Stone. 2009. The linear complementarity problem. SIAM.","DOI":"10.1137\/1.9780898719000"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024156.2024173"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459757"},{"key":"e_1_2_2_16_1","volume-title":"A scalable dual-primal domain decomposition method. Numerical linear algebra with applications 7, 7--8","author":"Farhat Charbel","year":"2000","unstructured":"Charbel Farhat, Michael Lesoinne, and Kendall Pierson. 2000. A scalable dual-primal domain decomposition method. Numerical linear algebra with applications 7, 7--8 (2000), 687--714."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964968"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Marco Fratarcangeli Huamin Wang and Yin Yang. 2018. Parallel iterative solvers for real-time elastic deformations. In SIGGRAPH Asia 2018 Courses. 1--45.","DOI":"10.1145\/3277644.3277779"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3130800.3130879"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1944846.1944855"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386014"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566578"},{"key":"e_1_2_2_25_1","series-title":"SIAM review 31, 2","volume-title":"Updating the inverse of a matrix","author":"Hager William W","year":"1989","unstructured":"William W Hager. 1989. Updating the inverse of a matrix. SIAM review 31, 2 (1989), 221--239."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1576246.1531393"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1399504.1360622"},{"key":"e_1_2_2_28_1","first-page":"16","article-title":"Interactive Deformation Using Modal Analysis with Constraints","volume":"3","author":"Hauser Kris K","year":"2003","unstructured":"Kris K Hauser, Chen Shen, and James F O'Brien. 2003. Interactive Deformation Using Modal Analysis with Constraints.. In Graphics Interface, Vol. 3. 16--17.","journal-title":"Graphics Interface"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2231816.2231821"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2011.04.025"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/wics.18"},{"key":"e_1_2_2_32_1","volume-title":"As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3","author":"Igarashi Takeo","year":"2005","unstructured":"Takeo Igarashi, Tomer Moscovich, and John F Hughes. 2005. As-rigid-as-possible shape manipulation. ACM transactions on Graphics (TOG) 24, 3 (2005), 1134--1141."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028523.1028541"},{"key":"e_1_2_2_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_2_2_35_1","doi-asserted-by":"crossref","unstructured":"Carl T Kelley. 1995. Iterative methods for linear and nonlinear equations. SIAM.","DOI":"10.1137\/1.9781611970944"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1618452.1618469"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.78"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203203"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Martin Komaritzan and Mario Botsch. 2019. Fast projective skinning. In Motion Interaction and Games. 1--10.","DOI":"10.1145\/3359566.3360073"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384515"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459753"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_2_2_44_1","volume-title":"BFEMP: Interpenetrationfree MPM-FEM coupling with barrier contact. Computer Methods in Applied Mechanics and Engineering","author":"Li Xuan","year":"2021","unstructured":"Xuan Li, Yu Fang, Minchen Li, and Chenfanfu Jiang. 2021a. BFEMP: Interpenetrationfree MPM-FEM coupling with barrier contact. Computer Methods in Applied Mechanics and Engineering (2021), 114350."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2990496"},{"key":"e_1_2_2_47_1","volume-title":"NNWarp: Neural network-based nonlinear deformation","author":"Luo Ran","year":"2018","unstructured":"Ran Luo, Tianjia Shao, Huamin Wang, Weiwei Xu, Xiang Chen, Kun Zhou, and Yin Yang. 2018. NNWarp: Neural network-based nonlinear deformation. IEEE transactions on visualization and computer graphics 26, 4 (2018), 1745--1759."},{"key":"e_1_2_2_48_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_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309486.3340247"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778776"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1964921.1964967"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_2_55_1","volume-title":"Symposium on Computer Animation","volume":"1","author":"Narain Rahul","year":"2016","unstructured":"Rahul Narain, Matthew Overby, and George E Brown. 2016. ADMM &supe; projective dynamics: fast simulation of general constitutive models.. In Symposium on Computer Animation, Vol. 1. 2016."},{"key":"e_1_2_2_56_1","volume-title":"Numerical optimization","author":"Nocedal Jorge","unstructured":"Jorge Nocedal and Stephen Wright. 2006. Numerical optimization. Springer Science & Business Media."},{"key":"e_1_2_2_57_1","volume-title":"Non-linear elastic deformations","author":"Ogden Raymond W","unstructured":"Raymond W Ogden. 1997. Non-linear elastic deformations. Courier Corporation."},{"key":"e_1_2_2_58_1","volume-title":"Computer Graphics Forum","author":"Otaduy Miguel A","unstructured":"Miguel A Otaduy, Rasmus Tamstorf, Denis Steinemann, and Markus Gross. 2009. Implicit contact handling for deformable objects. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 559--568."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730875"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355621"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/74333.74355"},{"key":"e_1_2_2_62_1","volume-title":"Computer Animation and Simulation'97","author":"Provot Xavier","unstructured":"Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation'97. Springer, 177--189."},{"key":"e_1_2_2_63_1","volume-title":"CUDA by example: an introduction to generalpurpose GPU programming","author":"Sanders Jason","unstructured":"Jason Sanders and Edward Kandrot. 2010. CUDA by example: an introduction to generalpurpose GPU programming. Addison-Wesley Professional."},{"key":"e_1_2_2_64_1","volume-title":"High-order Differentiable Autoencoder for Nonlinear Model Reduction. arXiv preprint arXiv:2102.11026","author":"Shen Siyuan","year":"2021","unstructured":"Siyuan Shen, Yang Yin, Tianjia Shao, He Wang, Chenfanfu Jiang, Lei Lan, and Kun Zhou. 2021. High-order Differentiable Autoencoder for Nonlinear Model Reduction. arXiv preprint arXiv:2102.11026 (2021)."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180491"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818081"},{"key":"e_1_2_2_67_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3272127.3275005","article-title":"I-Cloth: Incremental collision handling for GPU-based interactive cloth simulation","volume":"37","author":"Tang Min","year":"2018","unstructured":"Min Tang, Tongtong Wang, Zhongyuan Liu, Ruofeng Tong, and Dinesh Manocha. 2018. I-Cloth: Incremental collision handling for GPU-based interactive cloth simulation. ACM Transactions on Graphics (TOG) 37, 6 (2018), 1--10.","journal-title":"ACM Transactions on Graphics (TOG)"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766904"},{"key":"e_1_2_2_69_1","volume-title":"Deformable models. The visual computer 4, 6","author":"Terzopoulos Demetri","year":"1988","unstructured":"Demetri Terzopoulos and Kurt Fleischer. 1988. Deformable models. The visual computer 4, 6 (1988), 306--331."},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37427"},{"key":"e_1_2_2_71_1","volume-title":"Constraints on deformable models: Recovering 3D shape and nonrigid motion. Artificial intelligence 36, 1","author":"Terzopoulos Demetri","year":"1988","unstructured":"Demetri Terzopoulos, Andrew Witkin, and Michael Kass. 1988. Constraints on deformable models: Recovering 3D shape and nonrigid motion. Artificial intelligence 36, 1 (1988), 91--123."},{"key":"e_1_2_2_72_1","doi-asserted-by":"crossref","unstructured":"Matthias Teschner Stefan Kimmerle Bruno Heidelberger Gabriel Zachmann Laks Raghupathi Arnulph Fuhrmann M-P Cani Fran\u00e7ois Faure Nadia Magnenat-Thalmann Wolfgang Strasser et al. 2005. Collision detection for deformable objects. In Computer graphics forum Vol. 24. Wiley Online Library 61--81.","DOI":"10.1111\/j.1467-8659.2005.00829.x"},{"key":"e_1_2_2_73_1","volume-title":"High-Performance Computing on the Intel\u00ae Xeon Phi\u2122","author":"Wang Endong","unstructured":"Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, and Yajuan Wang. 2014. Intel math kernel library. In High-Performance Computing on the Intel\u00ae Xeon Phi\u2122. Springer, 167--188."},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_2_76_1","volume-title":"Computer Graphics Forum","author":"Wang Qisi","unstructured":"Qisi Wang, Yutian Tao, Eric Brandt, Court Cutting, and Eftychios Sifakis. 2021. Optimized processing of localized collisions in projective dynamics. In Computer Graphics Forum, Vol. 40. Wiley Online Library, 382--393."},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386760"},{"key":"e_1_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2007.07.006"},{"key":"e_1_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00852.x"},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417865"},{"key":"e_1_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818065"},{"key":"e_1_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356486"},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818089"},{"key":"e_1_2_2_84_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2013.12"},{"key":"e_1_2_2_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356491"},{"key":"e_1_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0060-0"},{"key":"e_1_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/1731047.1731054"},{"key":"e_1_2_2_88_1","volume-title":"Perumal Nithiarasu, and JZ Zhu.","author":"Zienkiewicz Olgierd Cecil","year":"1977","unstructured":"Olgierd Cecil Zienkiewicz, Robert Leroy Taylor, Perumal Nithiarasu, and JZ Zhu. 1977. The finite element method. Vol. 3. McGraw-hill London."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530069","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3528223.3530069","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3528223.3530069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:25Z","timestamp":1750186945000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3528223.3530069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":88,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.1145\/3528223.3530069"],"URL":"https:\/\/doi.org\/10.1145\/3528223.3530069","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"2022-07-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}