Cited By
View all- Ruan LWang BLiu TChen B(2024)MiNNIE: a Mixed Multigrid Method for Real-time Simulation of Nonlinear Near-Incompressible ElasticsACM Transactions on Graphics10.1145/368775843:6(1-15)Online publication date: 19-Dec-2024
Vertex Block Descent
Article No.: 116, Pages 1 - 16
Abstract
We introduce vertex block descent, a block coordinate descent solution for the variational form of implicit Euler through vertex-level Gauss-Seidel iterations. It operates with local vertex position updates that achieve reductions in global variational energy with maximized parallelism. This forms a physics solver that can achieve numerical convergence with unconditional stability and exceptional computation performance. It can also fit in a given computation budget by simply limiting the iteration count while maintaining its stability and superior convergence rate.
We present and evaluate our method in the context of elastic body dynamics, providing details of all essential components and showing that it outperforms alternative techniques. In addition, we discuss and show examples of how our method can be used for other simulation systems, including particle-based simulations and rigid bodies.
Supplementary Material
supplemental
- Download
- 475.36 MB
References
[1]
Uri M Ascher and Eddy Boxerman. 2003. On the modified conjugate gradient method in cloth simulation. The Visual Computer 19 (2003), 526--531.
[2]
David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. (1998).
[3]
Markus Becker, Markus Ihmsen, and Matthias Teschner. 2009. Corotated SPH for deformable solids. In Proceedings of the Fifth Eurographics Conference on Natural Phenomena (Munich, Germany) (NPH'09). Eurographics Association, Goslar, DEU, 27--34.
[4]
Jeff Bolz, Ian Farmer, Eitan Grinspun, and Peter Schröder. 2003. Sparse matrix solvers on the GPU: conjugate gradients and multigrid. ACM transactions on graphics (TOG) 22, 3 (2003), 917--924.
[5]
Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2023. Projective dynamics: Fusing constraint projections for fast simulation. In Seminal Graphics Papers: Pushing the Boundaries, Volume 2. 787--797.
[6]
Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. In Proceedings of the 29th annual conference on Computer graphics and interactive techniques. 594--603.
[7]
Robert Bridson, Sebastian Marino, and Ronald Fedkiw. 2005. Simulation of clothing with folds and wrinkles. In ACM SIGGRAPH 2005 Courses. 3--es.
[8]
Steve Capell, Seth Green, Brian Curless, Tom Duchamp, and Zoran Popović. 2002. A multiresolution framework for dynamic deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. ACM, San Antonio Texas, 41--47.
[9]
Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics 29, 4 (July 2010), 1--6.
[10]
He Chen, Elie Diaz, and Cem Yuksel. 2023. Shortest Path to Boundary for Self-Intersecting Meshes. 42, 4, Article 146 (2023), 15 pages.
[11]
Kwang-Jin Choi and Hyeong-Seok Ko. 2005. Stable but responsive cloth. In ACM SIGGRAPH 2005 Courses on - SIGGRAPH '05. ACM Press, Los Angeles, California, 1.
[12]
B. Eberhardt, O. Etzmuß, and M. Hauth. 2000. Implicit-Explicit Schemes for Fast Animation with Particle Systems. In Computer Animation and Simulation 2000, W. Hansmann, W. Purgathofer, F. Sillion, Nadia Magnenat-Thalmann, Daniel Thalmann, and Bruno Arnaldi (Eds.). Springer Vienna, Vienna, 137--151. Series Title: Eurographics.
[13]
Zachary Ferguson, Minchen Li, Teseo Schneider, Francisca Gil-Ureta, Timothy Langlois, Chenfanfu Jiang, Denis Zorin, Danny M. Kaufman, and Daniele Panozzo. 2021. Intersection-free Rigid Body Dynamics. ACM Transactions on Graphics (SIGGRAPH) 40, 4, Article 183 (2021).
[14]
M. Fratarcangeli and F. Pellacini. 2015. Scalable Partitioning for Parallel Position Based Dynamics. Computer Graphics Forum 34, 2 (May 2015), 405--413.
[15]
Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: a practical gauss-seidel method for stable soft body dynamics. ACM Transactions on Graphics 35, 6 (Nov. 2016), 1--9.
[16]
Theodore F. Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M. Teran. 2015. Optimization Integrator for Large Time Steps. IEEE Transactions on Visualization and Computer Graphics 21, 10 (Oct. 2015), 1103--1115.
[17]
Gene H Golub and Charles F Van Loan. 2013. Matrix computations. JHU press.
[18]
Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A simple framework for adaptive simulation. ACM transactions on graphics (TOG) 21, 3 (2002), 281--290.
[19]
L. Grippo and M. Sciandrone. 2000. On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Operations Research Letters 26, 3 (2000), 127--136.
[20]
LA Hageman and TA Porsching. 1975. Aspects of nonlinear block successive overrelaxation. SIAM J. Numer. Anal. 12, 3 (1975), 316--335.
[21]
Michael Hauth and Olaf Etzmuss. 2001. A High Performance Solver for the Animation of Deformable Objects using Advanced Numerical Methods. Computer Graphics Forum 20, 3 (Sept. 2001), 319--328.
[22]
Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O'Brien. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Transactions on Graphics 31, 5 (Aug. 2012), 1--13.
[23]
G. Hirota, S. Fisher, A. State, C. Lee, and H. Fuchs. 2001. An implicit finite element method for elastic solids in contact. In Proceedings Computer Animation 2001. Fourteenth Conference on Computer Animation (Cat. No.01TH8596). IEEE Comput. Soc, Seoul, South Korea, 136--254.
[24]
Peter Huthwaite. 2014. Accelerated finite element elastodynamic simulations using the GPU. J. Comput. Phys. 257 (2014), 687--707.
[25]
C. Kane, J. E. Marsden, and M. Ortiz. 1999. Symplectic-energy-momentum preserving variational integrators. J. Math. Phys. 40, 7 (July 1999), 3353--3371.
[26]
Couro Kane, Jerrold E Marsden, Michael Ortiz, and Matthew West. 2000. Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems. International Journal for numerical methods in engineering 49, 10 (2000), 1295--1325.
[27]
Liliya Kharevych, Weiwei Yang, Yiying Tong, Eva Kanso, Jerrold E. Marsden, Peter Schröder, and Matthieu Desbrun. 2006. Geometric, Variational Integrators for Computer Animation. In ACM SIGGRAPH / Eurographics Symposium on Computer Animation, Marie-Paule Cani and James O'Brien (Eds.). The Eurographics Association.
[28]
Lei Lan, Minchen Li, Chenfanfu Jiang, Huamin Wang, and Yin Yang. 2023. Second-order Stencil Descent for Interior-point Hyperelasticity. ACM Transactions on Graphics 42, 4 (Aug. 2023), 1--16.
[29]
Lei Lan, Guanqun Ma, Yin Yang, Changxi Zheng, Minchen Li, and Chenfanfu Jiang. 2022. Penetration-free projective dynamics on the GPU. ACM Transactions on Graphics (TOG) 41, 4 (2022), 1--16.
[30]
J. A. Levine, A. W. Bargteil, C. Corsi, J. Tessendorf, and R. Geist. 2015. A peridynamic perspective on spring-mass fracture. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Copenhagen, Denmark) (SCA '14). Eurographics Association, Goslar, DEU, 47--55.
[31]
A. Lew, J. E. Marsden, M. Ortiz, and M. West. 2004. Variational time integrators. Internat. J. Numer. Methods Engrg. 60, 1 (May 2004), 153--212.
[32]
Cheng Li, Min Tang, Ruofeng Tong, Ming Cai, Jieyi Zhao, and Dinesh Manocha. 2020b. P-cloth: interactive complex cloth simulation on multi-GPU systems using dynamic matrix assembly and pipelined implicit integrators. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1--15.
[33]
Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy R Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M Kaufman. 2020a. Incremental potential contact: intersection-and inversion-free, large-deformation dynamics. ACM Trans. Graph. 39, 4 (2020), 49.
[34]
Minchen Li, Ming Gao, Timothy Langlois, Chenfanfu Jiang, and Danny M. Kaufman. 2019. Decomposed optimization time integrator for large-step elastodynamics. ACM Transactions on Graphics 38, 4 (Aug. 2019), 1--10.
[35]
Xuan Li, Yu Fang, Lei Lan, Huamin Wang, Yin Yang, Minchen Li, and Chenfanfu Jiang. 2023. Subspace-Preconditioned GPU Projective Dynamics with Contact for Cloth Simulation. In SIGGRAPH Asia 2023 Conference Papers. 1--12.
[36]
Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Transactions on Graphics 36, 3 (June 2017), 1--16.
[37]
M. Macklin, K. Erleben, M. Müller, N. Chentanez, S. Jeschke, and T.Y. Kim. 2020. Primal/Dual Descent Methods for Dynamics. Computer Graphics Forum 39, 8 (Dec. 2020), 89--100.
[38]
Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4, Article 153 (jul 2014), 12 pages.
[39]
Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proceedings of the 9th International Conference on Motion in Games. ACM, Burlingame California, 49--54.
[40]
Sebastian Martin, Peter Kaufmann, Mario Botsch, Eitan Grinspun, and Markus Gross. 2010. Unified simulation of elastic rods, shells, and solids. ACM Trans. Graph. 29, 4, Article 39 (jul 2010), 10 pages.
[41]
Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. In ACM SIGGRAPH 2011 papers. 1--8.
[42]
Brian Vincent Mirtich. 1996. Impulse-based dynamic simulation of rigid body systems. Ph. D. Dissertation. AAI9723116.
[43]
Matthias Müller, David Charypar, and Markus Gross. 2003. Particle-based fluid simulation for interactive applications. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (San Diego, California) (SCA '03). Eurographics Association, Goslar, DEU, 154--159.
[44]
Matthias Müller, Julie Dorsey, Leonard McMillan, Robert Jagnow, and Barbara Cutler. 2002. Stable real-time deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation. 49--54.
[45]
Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. Journal of Visual Communication and Image Representation 18, 2 (2007), 109--118.
[46]
Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless deformations based on shape matching. ACM transactions on graphics (TOG) 24, 3 (2005), 471--478.
[47]
M. Müller, R. Keiser, A. Nealen, M. Pauly, M. Gross, and M. Alexa. 2004. Point based animation of elastic, plastic and melting objects. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Grenoble, France) (SCA '04). Eurographics Association, Goslar, DEU, 141--151.
[48]
Alexander Naitsat, Yufeng Zhu, and Yehoshua Y Zeevi. 2020. Adaptive block coordinate descent for distortion optimization. In Computer Graphics Forum, Vol. 39. Wiley Online Library, 360--376.
[49]
Andreas Peer, Markus Ihmsen, Jens Cornelis, and Matthias Teschner. 2015. An implicit viscosity formulation for SPH fluids. ACM Trans. Graph. 34, 4, Article 114 (jul 2015), 10 pages.
[50]
Eftychios Sifakis and Jernej Barbic. 2012. FEM simulation of 3D deformable solids: A practitioner's guide to theory, discretization and model reduction. ACM SIGGRAPH 2012 Courses, SIGGRAPH'12 (08 2012).
[51]
J.C. Simo, N. Tarnow, and K.K. Wong. 1992. Exact energy-momentum conserving algorithms and symplectic schemes for nonlinear dynamics. Computer Methods in Applied Mechanics and Engineering 100, 1 (Oct. 1992), 63--116.
[52]
Breannan Smith, Fernando De Goes, and Theodore Kim. 2018. Stable neo-hookean flesh simulation. ACM Transactions on Graphics (TOG) 37, 2 (2018), 1--15.
[53]
Barbara Solenthaler, Jürg Schläfli, and Renato Pajarola. 2007. A unified particle model for fluid-solid interactions: Research Articles. Comput. Animat. Virtual Worlds 18, 1 (feb 2007), 69--82.
[54]
Ari Stern and Eitan Grinspun. 2009. Implicit-Explicit Variational Integration of Highly Oscillatory Problems. Multiscale Modeling & Simulation 7, 4 (Jan. 2009), 1779--1794. arXiv:0808.2239 [math].
[55]
Tetsuya Takahashi, Yoshinori Dobashi, Issei Fujishiro, Tomoyuki Nishita, and Ming C. Lin. 2015. Implicit Formulation for SPH-based Viscous Fluids. Comput. Graph. Forum 34, 2 (may 2015), 493--502.
[56]
Rasmus Tamstorf, Toby Jones, and Steve McCormick. 2015. Smoothed Aggregation Multigrid for Cloth Simulation. ACM Transactions on Graphics 34 (Oct. 2015), 1--13.
[57]
Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation. 181--190.
[58]
Quoc-Minh Ton-That, Paul G. Kry, and Sheldon Andrews. 2023. Parallel block Neo-Hookean XPBD using graph clustering. Computers & Graphics 110 (Feb. 2023), 1--10.
[59]
P. Volino and N. Magnenat-Thalmann. 2001. Comparing efficiency of integration methods for cloth simulation. In Proceedings. Computer Graphics International 2001. IEEE Comput. Soc, Hong Kong, China, 265--272.
[60]
Pascal Volino, Nadia Magnenat-Thalmann, and Francois Faure. 2009. A simple approach to nonlinear tensile stiffness for accurate cloth simulation. ACM Trans. Graph. 28, 4, Article 105 (sep 2009), 16 pages.
[61]
Ingo Wald, Sven Woop, Carsten Benthin, Gregory S Johnson, and Manfred Ernst. 2014. Embree: a kernel framework for efficient CPU ray tracing. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1--8.
[62]
Endong Wang, Qing Zhang, Bo Shen, Guangyong Zhang, Xiaowei Lu, Qing Wu, Yajuan Wang, Endong Wang, Qing Zhang, Bo Shen, et al. 2014. Intel math kernel library. High-Performance Computing on the Intel® Xeon Phi™: How to Fully Exploit MIC Architectures (2014), 167--188.
[63]
Huamin Wang. 2015. A chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics 34, 6 (Nov. 2015), 1--9.
[64]
Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics 35, 6 (Nov. 2016), 1--10.
[65]
Xinlei Wang, Minchen Li, Yu Fang, Xinxin Zhang, Ming Gao, Min Tang, Danny M. Kaufman, and Chenfanfu Jiang. 2020. Hierarchical Optimization Time Integration for CFL-Rate MPM Stepping. ACM Transactions on Graphics 39, 3 (June 2020), 1--16.
[66]
Stephen J Wright. 2015. Coordinate descent algorithms. Mathematical programming 151, 1 (2015), 3--34.
[67]
Zangyueyang Xian, Xin Tong, and Tiantian Liu. 2019. A scalable galerkin multigrid method for real-time simulation of deformable objects. ACM Transactions on Graphics 38, 6 (Dec. 2019), 1--13.
[68]
Y. Chen, Y. Han, J. Chen, Z. Zhang, A. McAdams, and J. Teran. 2024. Position-Based Nonlinear Gauss-Seidel for Quasistatic Hyperelasticity. ACM Transactions on Graphics (TOG) 115 (2024), 115:1--115:15.
[69]
Yongning Zhu, Eftychios Sifakis, Joseph Teran, and Achi Brandt. 2010. An efficient multi-grid method for the simulation of high-resolution elastic solids. ACM Transactions on Graphics 29, 2 (March 2010), 1--18.
Index Terms
- Vertex Block Descent
Recommendations
On the complexity analysis of randomized block-coordinate descent methods
In this paper we analyze the randomized block-coordinate descent (RBCD) methods proposed in Nesterov (SIAM J Optim 22(2):341---362, 2012), Richtárik and Takáă (Math Program 144(1---2):1---38, 2014) for minimizing the sum of a smooth convex function and ...
Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization
We consider the problem of minimizing the weighted sum of a smooth function f and a convex function P of n real variables subject to m linear equality constraints. We propose a block-coordinate gradient descent method for solving this problem, ...
Descent Directions of Quasi-Newton Methods for Symmetric Nonlinear Equations
In general, when a quasi-Newton method is applied to solve a system of nonlinear equations, the quasi-Newton direction is not necessarily a descent direction for the norm function. In this paper, we show that when applied to solve symmetric nonlinear ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 July 2024
Published in TOG Volume 43, Issue 4
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- NSF
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 371Total Downloads
- Downloads (Last 12 months)371
- Downloads (Last 6 weeks)141
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View all- Ruan LWang BLiu TChen B(2024)MiNNIE: a Mixed Multigrid Method for Real-time Simulation of Nonlinear Near-Incompressible ElasticsACM Transactions on Graphics10.1145/368775843:6(1-15)Online publication date: 19-Dec-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in