“Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials”
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
