{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T02:44:16Z","timestamp":1777603456013,"version":"3.51.4"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T00:00:00Z","timestamp":1573171200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2019,12,31]]},"abstract":"<jats:p>We propose a simple yet efficient multigrid scheme to simulate high-resolution deformable objects in their full spaces at interactive frame rates. The point of departure of our method is the Galerkin projection which is simple to construct. However, a na\u00efve Galerkin multigrid does not scale well for large and irregular grids because it trades-off matrix sparsity for smaller sized linear systems which eventually stops improving the performance. Given that observation, we design our special projection criterion which is based on skinning space coordinates with piecewise constant weights, to make our Galerkin multigrid method scale for high-resolution meshes without suffering from dense linear solves. The usage of skinning space coordinates enables us to reduce the resolution of grids more aggressively, and our piecewise constant weights further ensure us to always deal with reasonably-sparse linear solves. Our projection matrices also help us to manage multi-level linear systems efficiently. Therefore, our method can be applied to different optimization schemes such as Newton's method and Projective Dynamics, pushing the resolution of a real-time simulation to orders of magnitudes higher. Our final GPU implementation outperforms the other state-of-the-art GPU deformable body simulators, enabling us to simulate large deformable objects with hundred thousands of degrees of freedom in real-time.<\/jats:p>","DOI":"10.1145\/3355089.3356486","type":"journal-article","created":{"date-parts":[[2019,11,8]],"date-time":"2019-11-08T20:27:58Z","timestamp":1573244878000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["A scalable galerkin multigrid method for real-time simulation of deformable objects"],"prefix":"10.1145","volume":"38","author":[{"given":"Zangyueyang","family":"Xian","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University and Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Tong","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tiantian","family":"Liu","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11,8]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027--1035","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii. 2007. k-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027--1035."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/280814.280821"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073300"},{"key":"e_1_2_2_4_1","unstructured":"Jan Bender Matthias M\u00fcller and Miles Macklin. 2015. Position-Based Simulation Methods in Computer Graphics. In Eurographics (Tutorials)."},{"key":"e_1_2_2_5_1","volume-title":"Comput. Graph. Forum","author":"Bender Jan","unstructured":"Jan Bender, Matthias M\u00fcller, Miguel A Otaduy, Matthias Teschner, and Miles Macklin. 2014. A survey on position-based simulation methods in computer graphics. In Comput. Graph. Forum, Vol. 33. Wiley Online Library, 228--251."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601116"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201387"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2005.13"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpat.2010.11.005"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982437"},{"key":"e_1_2_2_11_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. ACM 14.","DOI":"10.1145\/3277644.3277779"},{"key":"e_1_2_2_12_1","volume-title":"Latent-space Dynamics for Reduced Deformable Simulation. Comput. Graph. Forum","author":"Fulton Lawson","year":"2019","unstructured":"Lawson Fulton, Vismay Modi, David Duvenaud, David I. W. Levin, and Alec Jacobson. 2019. Latent-space Dynamics for Reduced Deformable Simulation. Comput. Graph. Forum (2019)."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2459687"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2006.02.016"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276438"},{"key":"e_1_2_2_16_1","unstructured":"Alec Jacobson. 2015. How does Galerkin multigrid scale for irregular grids? http:\/\/www.alecjacobson.com\/weblog\/?p=4383"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185573"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964973"},{"key":"e_1_2_2_19_1","volume-title":"Comput. Graph. Forum","author":"Jeon Inyong","unstructured":"Inyong Jeon, Kwang-Jin Choi, Tae-Yong Kim, Bong-Ouk Choi, and Hyeong-Seok Ko. 2013. Constrainable multigrid for cloth. In Comput. Graph. Forum, Vol. 32. Wiley Online Library, 31--39."},{"key":"e_1_2_2_20_1","volume-title":"Proc. EG\/ACM Symp. Computer Animation, 43--51","author":"Kharevych Liliya","year":"2006","unstructured":"Liliya Kharevych, Weiwei Yang, Yiying Tong, Eva Kanso, Jerrold E Marsden, Peter Schr\u00f6der, and Matthieu Desbrun. 2006. Geometric, variational integrators for computer animation. Proc. EG\/ACM Symp. Computer Animation, 43--51."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3322951"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275012"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508406"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.2990496"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461984"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994258.2994272"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601152"},{"key":"e_1_2_2_28_1","volume-title":"In Proceedings on Graphics interface'88","author":"Magnenat-Thalmann Nadia","year":"1988","unstructured":"Nadia Magnenat-Thalmann, Richard Laperrire, and Daniel Thalmann. 1988. Joint-dependent local deformations for hand animation and object grasping. In In Proceedings on Graphics interface'88. Citeseer."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964967"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964932"},{"key":"e_1_2_2_31_1","volume-title":"Hierarchical Position Based Dynamics. In Workshop in Virtual Reality Interactions and Physical Simulation \"VRIPHYS\"","author":"M\u00fcller Matthias","year":"2008","unstructured":"Matthias M\u00fcller. 2008. Hierarchical Position Based Dynamics. In Workshop in Virtual Reality Interactions and Physical Simulation \"VRIPHYS\" (2008). The Eurographics Association."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jvcir.2007.01.005"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073216"},{"key":"e_1_2_2_34_1","first-page":"2222","article-title":"ADMM &supe; Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints","volume":"23","author":"Overby Matthew","year":"2017","unstructured":"Matthew Overby, George E Brown, Jie Li, and Rahul Narain. 2017. ADMM &supe; Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. IEEE TVCG 23, 10 (2017), 2222--2234.","journal-title":"IEEE TVCG"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276480"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2343483.2343501"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3241041"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/CADCG.2009.5246818"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Ari Stern and Mathieu Desbrun. 2006. Discrete geometric mechanics for variational time integrators. In ACM SIGGRAPH Courses. ACM 75--80.","DOI":"10.1145\/1185657.1185669"},{"key":"e_1_2_2_40_1","volume-title":"Introduction to applied mathematics","author":"Strang Gilbert","unstructured":"Gilbert Strang and Kaija Aarikka. 1986. Introduction to applied mathematics. Vol. 16. Wellesley-Cambridge Press Wellesley, MA."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818081"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073368.1073394"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/37402.37427"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766969"},{"key":"e_1_2_2_45_1","first-page":"213","article-title":"An efficient construction of reduced deformable objects","volume":"32","author":"Tycowicz Christoph Von","year":"2013","unstructured":"Christoph Von Tycowicz, Christian Schulz, Hans-Peter Seidel, and Klaus Hildebrandt. 2013. An efficient construction of reduced deformable objects. ACM Trans. Graph. 32, 6 (2013), 213.","journal-title":"ACM Trans. Graph."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818063"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766952"},{"key":"e_1_2_2_48_1","volume-title":"Comput. Graph. Forum","author":"Wang Zhendong","unstructured":"Zhendong Wang, Longhua Wu, Marco Fratarcangeli, Min Tang, and Huamin Wang. 2018. Parallel Multigrid for Nonlinear Cloth Simulation. In Comput. Graph. Forum, Vol. 37. Wiley Online Library, 131--141."},{"key":"e_1_2_2_49_1","first-page":"1195","article-title":"A System for High-Resolution Topology Optimization","volume":"22","author":"Wu Jun","year":"2016","unstructured":"Jun Wu, Christian Dick, and Rudiger Westermann. 2016. A System for High-Resolution Topology Optimization. IEEE TVCG 22, 3 (2016), 1195--1208.","journal-title":"IEEE TVCG"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201359"},{"key":"e_1_2_2_51_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\/3355089.3356486","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355089.3356486","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:44:40Z","timestamp":1750203880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355089.3356486"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,8]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,12,31]]}},"alternative-id":["10.1145\/3355089.3356486"],"URL":"https:\/\/doi.org\/10.1145\/3355089.3356486","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,8]]},"assertion":[{"value":"2019-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}