“Stabilizing Integrators for Real-Time Physics” by Dinev, Liu and Kavan

  • ©Dimitar Dinev, TianTian Liu, and Ladislav Kavan

Conference:


Title:

    Stabilizing Integrators for Real-Time Physics

Session/Category Title: That's Elastic

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We present a new time integration method featuring excellent stability and energy conservation properties, making it particularly suitable for real-time physics. The commonly used backward Euler method is stable but introduces artificial damping. Methods such as implicit midpoint do not suffer from artificial damping but are unstable in many common simulation scenarios. We propose an algorithm that blends between the implicit midpoint and forward/backward Euler integrators such that the resulting simulation is stable while introducing only minimal artificial damping. We achieve this by tracking the total energy of the simulated system, taking into account energy-changing events: damping and forcing. To facilitate real-time simulations, we propose a local/global solver, similar to Projective Dynamics, as an alternative to Newton’s method. Compared to the original Projective Dynamics, which is derived from backward Euler, our final method introduces much less numerical damping at the cost of minimal computing overhead. Stability guarantees of our method are derived from the stability of backward Euler, whose stability is a widely accepted empirical fact. However, to our knowledge, theoretical guarantees have so far only been proven for linear ODEs. We provide preliminary theoretical results proving the stability of backward Euler also for certain cases of nonlinear potential functions.

References:


    1. Samantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf. 2012. Speculative parallel asynchronous contact mechanics. ACM Transactions on Graphics 31, 6, 151.
    2. Uri M. Ascher and Linda R. Petzold. 1998. Computer Methods for Ordinary Differential Equations and Differential-algebraic Equations. Vol. 61. SIAM. 
    3. Uri M. Ascher and Sebastian Reich. 1999. The midpoint scheme and variants for Hamiltonian systems: Advantages and pitfalls. SIAM Journal on Scientific Computing 21, 3, 1045–1065. 
    4. David Baraff and Andrew Witkin. 1998. Large steps in cloth simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’98). ACM, New York, NY, 43–54. DOI:http://dx.doi.org/10.1145/280814.280821 
    5. Jan Bender, Dan Koschier, Patrick Charrier, and Daniel Weber. 2014. Position-based simulation of continuous materials. Computers and Graphics 44, 1–10. 
    6. Jan Bender, Matthias Müller, Miguel A. Otaduy, Matthias Teschner, and Miles Macklin. 2014. A survey on position-based simulation methods in computer graphics. Computer Graphics Forum, 33, 6, 228–251.
    7. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective Dynamics: Fusing constraint projections for fast simulation. ACM Transactions on Graphics 33, 4, 154.
    8. Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, New York, NY. 
    9. Robert Bridson, Ronald Fedkiw, and John Anderson. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics 21, 3, 594–603. 
    10. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Transactions on Graphics 29, 4, 38.
    11. Kwang-Jin Choi and Hyeong-Seok Ko. 2002. Stable but responsive cloth. ACM Transactions on Graphics 21, 3, 604–611. 
    12. J. Chung and G. M. Hulbert. 1993. A time integration algorithm for structural dynamics with improved numerical dissipation: The generalized- method. Journal of Applied Mechanics 60, 2, 371–375. 
    13. K. Dekker and J. G. Verwer. 1987. Stability of Runge-Kutta methods for stiff nonlinear differential equations. ZAMM—Journal of Applied Mathematics and Mechanics/Zeitschrift fr Angewandte Mathematik und Mechanik 67, 1, 68. DOI:http://dx.doi.org/10.1002/zamm.19870670128 
    14. Robert W. Easton. 1998. Geometric Methods for Discrete Dynamical Systems. Oxford University Press.
    15. Robert D. Engle, Robert D. Skeel, and Matthew Drees. 2005. Monitoring energy drift with shadow Hamiltonians. JJournal of Computational Physics 206, 2, 432–452. 
    16. Theodore F. Gast and Craig Schroeder. 2014. Optimization integrator for large time steps. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Computer Animation.
    17. 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, 1103–1115. 
    18. O. Gonzalez and J. C. Simo. 1996. On the stability of symplectic and energy-momentum algorithms for non-linear Hamiltonian systems with symmetry. Computer Methods in Applied Mechanics and Engineering 134, 3, 197–222. 
    19. Ernst Hairer. 2006. Long-Time Energy Conservation of Numerical Integrators. Cambridge University Press, CambridgeNY.
    20. Ernst Hairer, Christian Lubich, and Gerhard Wanner. 2006. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Vol. 31. Springer Science and Business Media.
    21. David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun. 2009. Asynchronous contact mechanics. ACM Transactions on Graphics 28, 3, Article No. 87. 
    22. T. J. R. Hughes, T. K. Caughey, and W. K. Liu. 1978. Finite-element methods for nonlinear elastodynamics which conserve energy. Journal of Applied Mechanics 45, 2, 366–370. 
    23. Arieh Iserles. 2009. A First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, Cambridge, NY.
    24. Couro Kane. 1999. Variational Integrators and the Newmark Algorithm for Conservative and Dissipative Mechanical Systems. Ph.D. Dissertation. California Institute of Technology, Pasadena, CA.
    25. C. Kane, J. E. Marsden, and M. Ortiz. 1999. Symplectic-energy-momentum preserving variational integrators. Journal of Mathematical Physics 40, 7, 3353–3371. 
    26. 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 Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 43–51.
    27. Tae-Yong Kim, Nuttapong Chentanez, and Matthias Müller-Fischer. 2012. Long range attachments—a method to simulate inextensible clothing in computer games. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 305–310.
    28. D. Kuhl and M. A. Crisfield. 1999. Energy-conserving and decaying algorithms in non-linear structural dynamics. International Journal for Numerical Methods in Engineering 45, 5, 569–599. 
    29. Robert A. LaBudde and Donald Greenspan. 1975. Energy and momentum conserving methods of arbitrary order for the numerical integration of equations of motion. Numerische Mathematik 25, 4, 323–346. 
    30. J. D. Lambert. 1991. Numerical Methods for Ordinary Differential Systems: The Initial Value Problem. John Wiley 8 Sons, New York, NY.
    31. Adrian Lew, Jerrold E. Marsden, Michael Ortiz, and Matthew West. 2003. Asynchronous variational integrators. Archive for Rational Mechanics and Analysis 167, 2, 85–146. 
    32. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Transactions on Graphics 32, 6, 209:1–209:7. http://cg.cis.upenn.edu/publications/Liu-FMS
    33. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2016. Towards real-time simulation of hyperelastic materials. arXiv:1604.07378.
    34. Tiantian Liu, Ming Gao, Lifeng Zhu, Eftychios Sifakis, and Ladislav Kavan. 2016. Fast and robust inversion-free shape manipulation. Computer Graphics Forum 35, 2, 1–11. 
    35. Miles Macklin and Matthias Müller. 2013. Position based fluids. ACM Transactions on Graphics 32, 4, 104.
    36. Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2014. Unified particle physics for real-time applications. ACM Transactions on Graphics 33, 4, 153.
    37. Aleka McAdams, Yongning Zhu, Andrew Selle, Mark Empey, Rasmus Tamstorf, Joseph Teran, and Eftychios Sifakis. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Transactions on Graphics 30, 4, Article No. 37. 
    38. Dominik L. Michels and Mathieu Desbrun. 2015. A semi-analytical approach to molecular dynamics. Journal of Computational Physics 303, 336–354. 
    39. Dominik L. Michels, Gerrit A. Sobottka, and Andreas G. Weber. 2014. Exponential integrators for stiff elastodynamic problems. ACM Transactions on Graphics 33, 1, 7.
    40. Matthias Müller. 2008. Hierarchical position based dynamics. In Proceedings of the Workshop in Virtual Reality Interactions and Physical Simulation (VRIPHYS’08). DOI:http://dx.doi.org/10.2312/PE/vriphys/vriphys08/001-010
    41. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2014. Strain based dynamics. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Symposium on Computer Animation (SCA’14), Vol. 2.
    42. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air meshes for robust collision handling. ACM Transactions on Graphics 34, 4, 133.
    43. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. Journal of Visual Communication and Image Representation 18, 2, 109–118.
    44. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM Projective Dynamics: Fast simulation of general constitutive models. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’16). 21–28.
    45. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Transactions on Graphics 31, 6, 152.
    46. Nathan Mortimore Newmark. 1959. A method of computation for structural dynamics. Journal of the Engineering Mechanics Division 85, 3, 69–74.
    47. Eftychios Sifakis and Jernej Barbič. 2012. FEM simulation of 3D deformable solids: A practitioner’s guide to theory, discretization and model reduction. In ACM SIGGRAPH 2012 Courses. ACM, New York, NY, 20.
    48. 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, 63–116. 
    49. F. S. Sin, D. Schroeder, and J. Barbič. 2013. Vega: Non-linear FEM deformable object simulator. Computer Graphics Forum 32, 1, 36–48.
    50. Gerrit Sobottka, Tomás Lay, and Andreas Weber. 2008. Stable integration of the dynamic Cosserat equations with application to hair modeling. Journal of WSCG 16, 73–80.
    51. Jos Stam. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In Proceedings of the IEEE International Conference on Computer-Aided Design and Computer Graphics.1–11. 
    52. Ari Stern and Mathieu Desbrun. 2006. Discrete geometric mechanics for variational time integrators. In ACM SIGGRAPH 2006 Courses. ACM, New York, NY, 75–80.
    53. Jonathan Su, Rahul Sheth, and Ronald Fedkiw. 2013. Energy conservation for the simulation of deformable bodies. IEEE Transactions on Visualization and Computer Grahics 19, 2, 189–200. 
    54. Demetri Terzopoulos and Kurt Fleischer. 1988. Deformable models. Visual Computer 4, 6, 306–331. 
    55. Demetri Terzopoulos and Kurt Fleischer. 1988. Modeling inelastic deformation: Viscolelasticity, plasticity, fracture. In ACM Siggraph Computer Graphics, Vol. 22. ACM, 269–278.
    56. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. ACM SIGGRAPH Computer Graphics 22, 4, 269–278. 
    57. Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straßer. 2008. Asynchronous cloth simulation. In Computer Graphics International, Vol. 2. Wilhelm Schickard Institute for Computer Science, Graphical-Interactive Systems.
    58. Huamin Wang. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics 34, 6, 246.
    59. Huamin Wang, James O’Brien, and Ravi Ramamoorthi. 2010. Multi-resolution isotropic strain limiting. ACM Transactions on Graphics 29, 6, Article , 10 pages.
    60. Matthew West. 2004. Variational Integrators. Ph.D. Dissertation. California Institute of Technology.
    61. M. West, C. Kane, J. E. Marsden, and M. Ortiz. 1999. Variational integrators, the Newmark scheme, and dissipative systems. In Proceedings of the International Conference on Differential Equations, Vol. 1. World Scientific, 7.
    62. Danyong Zhao, Yijing Li Li, and Jernej Barbič. 2016. Asynchronous implicit backward Euler integration. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA’16). 1–9.
    63. Ge Zhong and Jerrold E. Marsden. 1988. Lie-Poisson Hamilton-Jacobi theory and Lie-Poisson integrators. Physics Letters A 133, 3, 134–139.

ACM Digital Library Publication: