“Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials”

  • ©TianTian Liu, Sofien Bouaziz, and Ladislav Kavan

Conference:


Type(s):


Title:

    Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials

Session/Category Title:   Sound & Elastics


Presenter(s)/Author(s):


Moderator(s):



Abstract:


    We present a new method for real-time physics-based simulation supporting many different types of hyperelastic materials. Previous methods such as Position-Based or Projective Dynamics are fast but support only a limited selection of materials; even classical materials such as the Neo-Hookean elasticity are not supported. Recently, Xu et al. [2015] introduced new “spline-based materials” that can be easily controlled by artists to achieve desired animation effects. Simulation of these types of materials currently relies on Newton’s method, which is slow, even with only one iteration per timestep. In this article, we show that Projective Dynamics can be interpreted as a quasi-Newton method. This insight enables very efficient simulation of a large class of hyperelastic materials, including the Neo-Hookean, spline-based materials, and others. The quasi-Newton interpretation also allows us to leverage ideas from numerical optimization. In particular, we show that our solver can be further accelerated using L-BFGS updates (Limited-memory Broyden-Fletcher-Goldfarb-Shanno algorithm). Our final method is typically more than 10 times faster than one iteration of Newton’s method without compromising quality. In fact, our result is often more accurate than the result obtained with one iteration of Newton’s method. Our method is also easier to implement, implying reduced software development costs.

References:


    1. Steven S. An, Theodore Kim, and Doug L. James. 2008. Optimizing cubature for efficient integration of subspace deformations. ACM Trans. Graph. 27 (2008), 165:1–165:10.Google ScholarDigital Library
    2. Jernej Barbič and Doug L. James. 2005. Real-time subspace integration for St. Venant-kirchhoff deformable models. ACM Trans. Graph. 24 (2005), 982–990. Google ScholarDigital Library
    3. Adam W. Bargteil and Elaine Cohen. 2014. Animation of deformable bodies with quadratic Bézier finite elements. ACM Trans. Graph. 33 (2014), 27:1–27:10.Google ScholarDigital Library
    4. Adam W. Bargteil, Chris Wojtan, Jessica K. Hodgins, and Greg Turk. 2007. A finite element method for animating large viscoplastic flow. ACM Trans. Graph. 26 (2007), 16:1–16:8.Google ScholarDigital Library
    5. Klaus Jürgen Bathe and Arthur P. Cimento. 1980. Some practical procedures for the solution of nonlinear finite element equations. In Computer Methods in Applied Mechanics and Engineering 22 (1980), 59–85. Google ScholarCross Ref
    6. Jan Bender, Dan Koschier, Patrick Charrier, and Daniel Weber. 2014a. Position-based simulation of continuous materials. Computers 8 Graphics 44 (2014), 1–10.Google Scholar
    7. Jan Bender, Matthias Müller, Miguel A. Otaduy, Matthias Teschner, and Miles Macklin. 2014b. A survey on position-based simulation methods in computer graphics. In Comput. Graph. Forum. 33 (2014), 228–251. Google ScholarDigital Library
    8. Sofien Bouaziz, Mario Deuss, Yuliy Schwartzburg, Thibaut Weise, and Mark Pauly. 2012. Shape-up: Shaping discrete geometry with projections. In Comput. Graph. Forum, Vol. 31. 1657–1667. Google ScholarDigital Library
    9. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: Fusing constraint projections for fast simulation. ACM Trans. Graph. 33 (2014), 154:1–154:11.Google ScholarDigital Library
    10. Isaac Chao, Ulrich Pinkall, Patrick Sanan, and Peter Schröder. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29 (2010), 38:1–38:6.Google ScholarDigital Library
    11. Desai Chen, David Levin, Shinjiro Sueda, and Wojciech Matusik. 2015. Data-driven finite elements for geometry and material design. ACM Trans. Graph. 34 (2015), 74:1–74:10.Google ScholarDigital Library
    12. Bailin Deng, Sofien Bouaziz, Mario Deuss, Juyong Zhang, Yuliy Schwartzburg, and Mark Pauly. 2013. Exploring local modifications for constrained meshes. In Comput. Graph. Forum, Vol. 32. 11–20. Google ScholarCross Ref
    13. Mathieu Desbrun, Peter Schröder, and Alan Barr. 1999. Interactive animation of structured deformable objects. Graphics Interface 99 (1999), 10.Google Scholar
    14. Peter Deuflhard. 2011. Newton Methods for Nonlinear Problems: Affine Invariance and Adaptive Algorithms. Springer Science 8 Business Media.Google Scholar
    15. Jacob Fish, Murali Pandheeradi, and Vladimir Belsky. 1995. An efficient multilevel solution scheme for large scale non-linear systems. Internat. J. Numer. Methods Engrg. 38 (1995), 1597–1610. Google ScholarCross Ref
    16. Marco Fratarcangeli and Fabio Pellacini. 2015. Scalable partitioning for parallel position based dynamics. In Comput. Graph. Forum. 34 (2015), 405–413. Google ScholarDigital Library
    17. Theodore F. Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M. Teran. 2015. Optimization integrator for large time steps. IEEE Trans. Visualization Comp. Graph. 21 (2015), 1103–1115. Google ScholarDigital Library
    18. Joachim Georgii and Rüdiger Westermann. 2006. A multigrid framework for real-time simulation of deformable bodies. Comput. Graphics 30, 3 (2006), 408–415. Google ScholarDigital Library
    19. Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2007. Efficient simulation of inextensible cloth. ACM Trans. Graph. 26 (2007), 49:1–49:7.Google ScholarDigital Library
    20. Fabian Hahn, Sebastian Martin, Bernhard Thomaszewski, Robert Sumner, Stelian Coros, and Markus Gross. 2012. Rig-space physics. ACM Trans. Graph. 31 (2012), 72:1–72:8.Google ScholarDigital Library
    21. Ernst Hairer, Christian Lubich, and Gerhard Wanner. 2002. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer. Google ScholarCross Ref
    22. David Harmon, Daniele Panozzo, Olga Sorkine, and Denis Zorin. 2011. Interference-aware geometric modeling. ACM Trans. Graph. 30 (2011), 137:1–137:10.Google ScholarDigital Library
    23. David Harmon and Denis Zorin. 2013. Subspace Integration with Local Deformations. ACM Trans. Graph. 32 (2013), 107:1–107:10.Google ScholarDigital Library
    24. Michael Hauth and Olaf Etzmuss. 2001. A high performance solver for the animation of deformable objects using advanced numerical methods. In Comput. Graph. Forum. 20 (2001), 319–328. Google ScholarCross Ref
    25. Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O’Brien. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Trans. Graph. 31 (2012), 123:1–123:13.Google ScholarDigital Library
    26. Magnus Rudolph Hestenes and Eduard Stiefel. 1952. Methods of Conjugate Gradients for Solving Linear Systems. Vol. 49. NBS.Google Scholar
    27. Alexandru-Eugen Ichim, Ladislav Kavan, Merlin Nimier-David, and Mark Pauly. 2016. Building and animating user-specific volumetric face rigs. In Proc. EG Symp. Computer Animation. 107–117.Google Scholar
    28. Geoffrey Irving, Joseph Teran, and Ron Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proc. EG Symp. Computer Animation. 131–140. Google ScholarDigital Library
    29. 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 Proc. EG Symp. Computer Animation. 43–51.Google Scholar
    30. Tae-Yong Kim, Nuttapong Chentanez, and Matthias Müller-Fischer. 2012. Long range attachments-a method to simulate inextensible clothing in computer games. In Proc. EG Symp. Computer Animation. 305–310.Google Scholar
    31. Shahar Z. Kovalsky, Meirav Galun, and Yaron Lipman. 2016. Accelerated quadratic proxy for geometric optimization. ACM Trans. Graph. 35 (2016), 134:1–134:11.Google ScholarDigital Library
    32. Siwang Li, Jin Huang, Fernando de Goes, Xiaogang Jin, Hujun Bao, and Mathieu Desbrun. 2014. Space-time editing of elastic motion through material optimization and reduction. ACM Trans. Graph. 33 (2014), 108:1–108:10.Google ScholarDigital Library
    33. Tiantian Liu, Adam W. Bargteil, James F. O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Trans. Graph. 32 (2013), 214:1–214:7.Google ScholarDigital Library
    34. Miles Macklin and Matthias Müller. 2013. Position based fluids. ACM Trans. Graph. 32 (2013), 104:1–104:12.Google ScholarDigital Library
    35. Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-Yong Kim. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33 (2014), 153:1–153:12.Google ScholarDigital Library
    36. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. ACM Trans. Graph. 30 (2011), 72:1–72:8.Google ScholarDigital Library
    37. Tobias Martin, Pushkar Joshi, Miklós Bergou, and Nathan Carr. 2013. Efficient non-linear optimization via multi-scale gradient filtering. In Comput. Graph. Forum. 32 (2013), 89–100. Google ScholarDigital Library
    38. 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 Trans. Graph. 30 (2011), 37:1–37:12.Google ScholarDigital Library
    39. Matthias Müller. 2008. Hierarchical position based dynamics. In Workshop in Virtual Reality Interactions and Physical Simulation “VRIPHYS” (2008). Eurographics Association.Google Scholar
    40. Matthias Müller and Nuttapong Chentanez. 2011. Solid simulation with oriented particles. ACM Trans. Graph. 30 (2011), 92:1–92:10.Google ScholarDigital Library
    41. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2014. Strain based dynamics. In Proc. EG Symp. Computer Animation, Vol. 2 (2014), 149–157.Google Scholar
    42. Matthias Müller, Nuttapong Chentanez, Tae-Yong Kim, and Miles Macklin. 2015. Air meshes for robust collision handling. ACM Trans. Graph. 34 (2015), 133:1–133:9.Google ScholarDigital Library
    43. Matthias Müller, Julie Dorsey, Leonard McMillan, Robert Jagnow, and Barbara Cutler. 2002. Stable real-time deformations. In Proc. EG Symp. Computer Animation. 49–54. Google ScholarDigital Library
    44. Matthias Müller and Markus Gross. 2004. Interactive virtual materials. In Proceedings of Graphics Interface (2004), 239–246.Google Scholar
    45. Matthias Müller, Bruno Heidelberger, Marcus Hennix, and John Ratcliff. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18 (2007), 109–118. Google ScholarDigital Library
    46. Matthias Müller, Bruno Heidelberger, Matthias Teschner, and Markus Gross. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24 (2005), 471–478. Google ScholarDigital Library
    47. Rahul Narain, Matthew Overby, and George E. Brown. 2016. ADMM ⊇ projective dynamics: Fast simulation of general constitutive models. In Proc. ACM SIGGRAPH/Eurographics Symp. on Computer Animation (SCA’16). 21–28.Google Scholar
    48. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. 31 (2012), 152:1–152:10.Google ScholarDigital Library
    49. J.W. Neuberger. 1983. Steepest descent for general systems of linear differential equations in hilbert space. In Ordinary Differential Equations and Operators. Springer. Google ScholarCross Ref
    50. John Neuberger. 2009. Sobolev Gradients and Differential Equations. Springer Science 8 Business Media.Google Scholar
    51. Jorge Nocedal and Stephen J. Wright. 2006. Numerical Optimization. Springer Verlag.Google Scholar
    52. Alec R. Rivers and Doug L. James. 2007. FastLSM: Fast lattice shape matching for robust real-time deformation. ACM Trans. Graph. 26 (2007), 82:1–82:6.Google ScholarDigital Library
    53. Martin Servin, C. Lacoursière, and N. Melin. 2006. Interactive simulation of elastic deformable materials. In The Annual SIGRAD Conference; Special Theme: Computer Games 19 (2006).Google Scholar
    54. 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 Courses. 20:1–20:50.Google Scholar
    55. Jos Stam. 2009. Nucleus: Towards a unified dynamics solver for computer graphics. In IEEE Int. Conf. on CAD and Comput. Graph. 1–11.Google ScholarCross Ref
    56. Rasmus Tamstorf, Toby Jones, and Stephen F. McCormick. 2015. Smoothed aggregation multigrid for cloth simulation. ACM Trans. Graph. 34 (2015), 245:1–245:13.Google ScholarDigital Library
    57. Yun Teng, Mark Meyer, Tony DeRose, and Theodore Kim. 2015. Subspace condensation: Full space adaptivity for subspace deformations. ACM Trans. Graph. 34 (2015), 76:1–76:9.Google ScholarDigital Library
    58. Yun Teng, Miguel A. Otaduy, and Theodore Kim. 2014. Simulating articulated subspace self-contact. ACM Trans. Graph. 33 (2014), 106:1–106:9.Google ScholarDigital Library
    59. Joseph Teran, Eftychios Sifakis, Geoffrey Irving, and Ronald Fedkiw. 2005. Robust quasistatic finite elements and flesh simulation. In Proc. EG Symp. Computer Animation. 181–190. Google ScholarDigital Library
    60. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. In Computer Graphics (Proc. SIGGRAPH), Vol. 21. 205–214. Google ScholarDigital Library
    61. Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straßer. 2009. Continuum-based strain limiting. In Comput. Graph. Forum. 28 (2009), 569–576. Google ScholarCross Ref
    62. Maxime Tournier, Matthieu Nesme, Benjamin Gilles, and Francois Faure. 2015. Stable constrained dynamics. ACM Trans. Graph. 34 (2015), 132:1–132:10.Google ScholarDigital Library
    63. K. C. Valanis and Robert F. Landel. 1967. The strain-energy function of a hyperelastic material in terms of the extension ratios. Journal of Applied Physics 38 (1967), 2997–3002. Google ScholarCross Ref
    64. Huamin Wang. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. 34 (2015), 246:1–246:9.Google ScholarDigital Library
    65. Huamin Wang, James O’Brien, and Ravi Ramamoorthi. 2010. Multi-resolution isotropic strain limiting. ACM Trans. Graph. 29 (2010), 156:1–156:10.Google ScholarDigital Library
    66. Hongyi Xu, Funshing Sin, Yufeng Zhu, and Jernej Barbič. 2015. Nonlinear material design using principal stretches. ACM Trans. Graph. 34 (2015), 75:1–75:11.Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: