{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T02:15:08Z","timestamp":1774059308840,"version":"3.50.1"},"reference-count":88,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012166","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":[[2024,12,19]]},"abstract":"<jats:p>We propose a GPU-based iterative method for accelerated elastodynamic simulation with the log-barrier-based contact model. While Newton's method is a conventional choice for solving the interior-point system, the presence of ill-conditioned log barriers often necessitates a direct solution at each linearized substep and costs substantial storage and computational overhead. Moreover, constraint sets that vary in each iteration present additional challenges in algorithm convergence. Our method employs a novel barrier-augmented Lagrangian method to improve system conditioning and solver efficiency by adaptively updating an augmentation constraint sets. This enables the utilization of a scalable, inexact Newton-PCG solver with sparse GPU storage, eliminating the need for direct factorization. We further enhance PCG convergence speed with a domain-decomposed warm start strategy based on an eigenvalue spectrum approximated through our in-time assembly. Demonstrating significant scalability improvements, our method makes simulations previously impractical on 128 GB of CPU memory feasible with only 8 GB of GPU memory and orders-of-magnitude faster. Additionally, our method adeptly handles stiff problems, surpassing the capabilities of existing GPU-based interior-point methods. Our results, validated across various complex collision scenarios involving intricate geometries and large deformations, highlight the exceptional performance of our approach.<\/jats:p>","DOI":"10.1145\/3687988","type":"journal-article","created":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T15:46:04Z","timestamp":1732031164000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Barrier-Augmented Lagrangian for GPU-based Elastodynamic Contact"],"prefix":"10.1145","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7393-5486","authenticated-orcid":false,"given":"Dewen","family":"Guo","sequence":"first","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9868-7311","authenticated-orcid":false,"given":"Minchen","family":"Li","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7645-5931","authenticated-orcid":false,"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Utah, Salt Lake City, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8901-2184","authenticated-orcid":false,"given":"Sheng","family":"Li","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7819-0076","authenticated-orcid":false,"given":"Guoping","family":"Wang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3532720.3535640"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008292328909"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891843"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192168"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/142920.134084"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of Computer Animation'94","author":"Baraff David","year":"1994","unstructured":"David Baraff and Andrew Witkin. 1994. Global methods for simulating contacting flexible bodies. In Proceedings of Computer Animation'94. IEEE, 1--12."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882357"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600425"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882364"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_1_12_1","volume-title":"Multi-level adaptive solutions to boundary-value problems. Mathematics of computation 31, 138","author":"Brandt Achi","year":"1977","unstructured":"Achi Brandt. 1977. Multi-level adaptive solutions to boundary-value problems. Mathematics of computation 31, 138 (1977), 333--390."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201387"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566623"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185592"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459942"},{"key":"e_1_2_1_17_1","volume-title":"A restricted additive Schwarz preconditioner for general sparse linear systems. Siam journal on scientific computing 21, 2","author":"Cai Xiao-Chuan","year":"1999","unstructured":"Xiao-Chuan Cai and Marcus Sarkis. 1999. A restricted additive Schwarz preconditioner for general sparse linear systems. Siam journal on scientific computing 21, 2 (1999), 792--797."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1134\/S1995080219050056"},{"key":"e_1_2_1_20_1","volume-title":"Multilevel additive methods for elliptic finite element problems","author":"Dryja Maksymilian","unstructured":"Maksymilian Dryja and Olof B Widlund. 1990. Multilevel additive methods for elliptic finite element problems. New York University, Department of Computer Science, Courant Institute of \u2026."},{"key":"e_1_2_1_21_1","volume-title":"Intersection-free Robot Manipulation with Soft-Rigid Coupled Incremental Potential Contact. arXiv preprint arXiv:2311.05945","author":"Du Wenxin","year":"2023","unstructured":"Wenxin Du, Siqiong Yao, Xinlei Wang, Yuhang Xu, Wenqiang Xu, and Cewu Lu. 2023. Intersection-free Robot Manipulation with Soft-Rigid Coupled Incremental Potential Contact. arXiv preprint arXiv:2311.05945 (2023)."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3096239"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459757"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459802"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_1_26_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_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142903425409"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2459687"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3414685.3417766"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360622"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3643028"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1028523.1028541"},{"key":"e_1_2_1_33_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_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3388769.3407490"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3359566.3360073"},{"key":"e_1_2_1_36_1","volume-title":"Affine body dynamics: Fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:2201.10022","author":"Lan Lei","year":"2022","unstructured":"Lei Lan, Danny M Kaufman, Minchen Li, Chenfanfu Jiang, and Yin Yang. 2022. Affine body dynamics: Fast, stable & intersection-free simulation of stiff materials. arXiv preprint arXiv:2201.10022 (2022)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592104"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384515"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459753"},{"key":"e_1_2_1_40_1","volume-title":"Computer Graphics Forum","author":"Lauterbach Christian","unstructured":"Christian Lauterbach, Michael Garland, Shubhabrata Sengupta, David Luebke, and Dinesh Manocha. 2009. Fast BVH construction on GPUs. In Computer Graphics Forum, Vol. 28. Wiley Online Library, 375--384."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392425"},{"key":"e_1_2_1_42_1","volume-title":"Convergent Incremental Potential Contact. arXiv preprint arXiv:2307.15908","author":"Li Minchen","year":"2023","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 preprint arXiv:2307.15908 (2023)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322951"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450626.3459767"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530072"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2990496"},{"key":"e_1_2_1_47_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_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/199404.199436"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/140980260"},{"key":"e_1_2_1_53_1","volume-title":"Numerical optimization","author":"Nocedal Jorge","unstructured":"Jorge Nocedal and Stephen J Wright. 2006. Numerical optimization. Springer."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2017.2730875"},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"165","DOI":"10.9728\/dcs.2016.17.3.165","article-title":"Analysis of morton code conversion for 32 bit IEEE 754 floating point variables","volume":"17","author":"Park Taejung","year":"2016","unstructured":"Taejung Park. 2016. Analysis of morton code conversion for 32 bit IEEE 754 floating point variables. Journal of Digital Contents Society 17, 3 (2016), 165--172.","journal-title":"Journal of Digital Contents Society"},{"key":"e_1_2_1_56_1","volume-title":"Computer Animation and Simulation'97: Proceedings of the Eurographics Workshop in Budapest, Hungary, September 2--3","author":"Provot Xavier","year":"1997","unstructured":"Xavier Provot. 1997. Collision and self-collision handling in cloth model dedicated to design garments. In Computer Animation and Simulation'97: Proceedings of the Eurographics Workshop in Budapest, Hungary, September 2--3, 1997. Springer, 177--189."},{"key":"e_1_2_1_57_1","doi-asserted-by":"crossref","DOI":"10.2172\/6560074","volume-title":"Krylov subspace methods for solving large unsymmetric linear systems. Mathematics of computation 37, 155","author":"Saad Yousef","year":"1981","unstructured":"Yousef Saad. 1981. Krylov subspace methods for solving large unsymmetric linear systems. Mathematics of computation 37, 155 (1981), 105--126."},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Yousef Saad. 2003. Iterative methods for sparse linear systems. SIAM.","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180491"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241041"},{"key":"e_1_2_1_61_1","volume-title":"Symposium on Computer Animation","volume":"1","author":"Stomakhin Alexey","year":"2012","unstructured":"Alexey Stomakhin, Russell Howes, Craig A Schroeder, and Joseph M Teran. 2012. Energetically Consistent Invertible Elasticity.. In Symposium on Computer Animation, Vol. 1."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3203188"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1730804.1730806"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661237"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275005"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073368.1073394"},{"key":"e_1_2_1_67_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_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/37401.37427"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550469.3555418"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209887"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3105762.3105782"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1142007"},{"key":"e_1_2_1_73_1","volume-title":"Computer Graphics Forum","author":"Wang Bolun","unstructured":"Bolun Wang, Zachary Ferguson, Xin Jiang, Marco Attene, Daniele Panozzo, and Teseo Schneider. 2022. Fast and Exact Root Parity for Continuous Collision Detection. In Computer Graphics Forum, Vol. 41. Wiley Online Library, 355--363."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460775"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980236"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604551"},{"key":"e_1_2_1_78_1","volume-title":"Computer Graphics Forum","author":"Wang Zhendong","unstructured":"Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel multigrid for nonlinear cloth simulation. In Computer Graphics Forum, Vol. 37. Wiley Online Library, 131--141."},{"key":"e_1_2_1_79_1","volume-title":"Proc. of Vision, Modeling, and Visualization. 349--356","author":"Wicke Martin","year":"2006","unstructured":"Martin Wicke, Hermes Lanker, and Markus Gross. 2006. Untangling cloth with boundaries. In Proc. of Vision, Modeling, and Visualization. 349--356."},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/3528223.3530085"},{"key":"e_1_2_1_81_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3606929","article-title":"An Eigenanalysis of Angle-Based Deformation Energies","volume":"6","author":"Wu Haomiao","year":"2023","unstructured":"Haomiao Wu and Theodore Kim. 2023. An Eigenanalysis of Angle-Based Deformation Energies. Proceedings of the ACM on Computer Graphics and Interactive Techniques 6, 3 (2023), 1--19.","journal-title":"Proceedings of the ACM on Computer Graphics and Interactive Techniques"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/3430025"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356486"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592115"},{"key":"e_1_2_1_85_1","volume-title":"An end-to-end differentiable framework for contact-aware robot design. arXiv preprint arXiv:2107.07501","author":"Xu Jie","year":"2021","unstructured":"Jie Xu, Tao Chen, Lara Zlokapa, Michael Foshey, Wojciech Matusik, Shinjiro Sueda, and Pulkit Agrawal. 2021. An end-to-end differentiable framework for contact-aware robot design. arXiv preprint arXiv:2107.07501 (2021)."},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543865"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12752"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276396"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687988","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3687988","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:58Z","timestamp":1750295398000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3687988"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":88,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,19]]}},"alternative-id":["10.1145\/3687988"],"URL":"https:\/\/doi.org\/10.1145\/3687988","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"2024-11-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}