“FEPR: fast energy projection for real-time simulation of deformable objects” by Dinev, Liu, Li and Thomaszewski
Conference:
Type(s):
Entry Number: 79
Title:
- FEPR: fast energy projection for real-time simulation of deformable objects
Session/Category Title: That's Elastic
Presenter(s)/Author(s):
Moderator(s):
Abstract:
We propose a novel projection scheme that corrects energy fluctuations in simulations of deformable objects, thereby removing unwanted numerical dissipation and numerical “explosions”. The key idea of our method is to first take a step using a conventional integrator, then project the result back to the constant energy-momentum manifold. We implement this strategy using fast projection, which only adds a small amount of overhead to existing physics-based solvers. We test our method with several implicit integration rules and demonstrate its benefits when used in conjunction with Position Based Dynamics and Projective Dynamics. When added to a dissipative integrator such as backward Euler, our method corrects the artificial damping and thus produces more vivid motion. Our projection scheme also effectively prevents instabilities that can arise due to approximate solves or large time steps. Our method is fast, stable, and easy to implement—traits that make it well-suited for real-time physics applications such as games or training simulators.
References:
1. Samantha Ainsley, Etienne Vouga, Eitan Grinspun, and Rasmus Tamstorf. 2012. Speculative parallel asynchronous contact mechanics. ACM Trans. Graph. 31, 6 (2012), 151. Google ScholarDigital Library
2. Sheldon Andrews, Kenny Erleben, Paul G Kry, and Marek Teichmann. 2017. Constraint reordering for iterative multi-body simulation with contact. In ECCOMAS Thematic Conference on Multibody Dynamic.Google Scholar
3. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proc. of ACM SIGGRAPH. 43–54. Google ScholarDigital Library
4. Jan Bender, Matthias Müller, 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. 228–251. Google ScholarDigital Library
5. Sofien Bouaziz, Sebastian Martin, Tiantian Liu, Ladislav Kavan, and Mark Pauly. 2014. Projective dynamics: fusing constraint projections for fast simulation. ACM Trans. Graph. 33, 4 (2014), 154. Google ScholarDigital Library
6. Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. 2011. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends® in Machine Learning 3, 1 (2011), 1–122. Google ScholarDigital Library
7. Robert Bridson, Sebastian Marino, and Ronald Fedkiw. 2003. Simulation of clothing with folds and wrinkles. Proc. EG/ACM Symp. Computer Animation, 28–36. Google ScholarDigital Library
8. Yu Ju Chen, Uri Ascher, and Dinesh Pai. 2017. Exponential Rosenbrock-Euler Integrators for Elastodynamic Simulation. TVCG (2017).Google Scholar
9. Kwang-Jin Choi and Hyeong-Seok Ko. 2002. Stable but responsive cloth. ACM Trans. Graph. 21, 3 (2002), 604–611. Google ScholarDigital Library
10. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H Barr. 2001. Dynamic real-time deformations using space & time adaptive sampling. In Proc. of Computer graphics and interactive techniques. 31–36. Google ScholarDigital Library
11. Dimitar Dinev, Tiantian Liu, and Ladislav Kavan. 2018. Stabilizing Integrators for Real-Time Physics. ACM Trans. Graph. 37, 1 (Jan. 2018), 9:1–9:19. Google ScholarDigital Library
12. Bernhard Eberhardt, Olaf Etzmuß, and Michael Hauth. 2000. Implicit-explicit schemes for fast animation with particle systems. Springer.Google ScholarCross Ref
13. Robert D Engle, Robert D Skeel, and Matthew Drees. 2005. Monitoring energy drift with shadow Hamiltonians. J. Comput. Phys. 206, 2 (2005), 432–452. Google ScholarDigital Library
14. Elliot English and Robert Bridson. 2008. Animating developable surfaces using nonconforming elements. ACM Trans. Graph. 27, 3, 66. Google ScholarDigital Library
15. Basil Fierz, Jonas Spillmann, and Matthias Harders. 2011. Element-wise mixed implicit-explicit integration for stable dynamic simulation of deformable objects. Proc. EG/ACM Symp. Computer Animation, 257–266. Google ScholarDigital Library
16. Mihai Frâncu and Florica Moldoveanu. 2017. Position based simulation of solids with accurate contact handling. Computers & Graphics 69 (2017), 12–23. Google ScholarDigital Library
17. Marco Fratarcangeli, Valentina Tibaldo, and Fabio Pellacini. 2016. Vivace: a practical gauss-seidel method for stable soft body dynamics. ACM Trans. Graph. 35, 6 (2016), 214. Google ScholarDigital Library
18. Theodore F Gast, Craig Schroeder, Alexey Stomakhin, Chenfanfu Jiang, and Joseph M Teran. 2015. Optimization integrator for large time steps. TVCG 21, 10 (2015), 1103–1115. Google ScholarDigital Library
19. Zhong Ge and Jerrold E Marsden. 1988. Lie-poisson hamilton-jacobi theory and lie-poisson integrators. Physics Letters A 133, 3 (1988), 134–139.Google ScholarCross Ref
20. Rony Goldenthal, David Harmon, Raanan Fattal, Michel Bercovier, and Eitan Grinspun. 2007. Efficient simulation of inextensible cloth. ACM Trans. Graph. 26, 3 (2007), 49. Google ScholarDigital Library
21. Oscar Gonzalez. 1996. Time integration and discrete Hamiltonian systems. Journal of Nonlinear Science 6, 5 (1996), 449–467.Google ScholarCross Ref
22. Oscar Gonzalez. 2000. Exact energy and momentum conserving algorithms for general models in nonlinear elasticity. Computer Methods in Applied Mechanics and Engineering 190, 13 (2000), 1763–1783.Google ScholarCross Ref
23. Ernst Hairer. 2006. Long-time energy conservation of numerical integrators. 162–180.Google Scholar
24. Ernst Hairer, Christian Lubich, and Gerhard Wanner. 2006. Geometric numerical integration: structure-preserving algorithms for ordinary differential equations. Vol. 31.Google Scholar
25. David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, and Eitan Grinspun. 2009. Asynchronous contact mechanics. In ACM Trans. Graph., Vol. 28. 87. Google ScholarDigital Library
26. Amiram Harten, Peter D Lax, and Bram Van Leer. 1997. On upstream differencing and Godunov-type schemes for hyperbolic conservation laws. In Upwind and High-Resolution Schemes. Springer, 53–79.Google Scholar
27. TJR Hughes, TK Caughey, and WK Liu. 1978. Finite-element methods for nonlinear elastodynamics which conserve energy. Journal of Applied Mechanics 45, 2 (1978), 366–370.Google ScholarCross Ref
28. Arieh Iserles, Hans Z Munthe-Kaas, Syvert P Nørsett, and Antonella Zanna. 2000. Lie-group methods. Acta Numerica 2000 9 (2000), 215–365.Google Scholar
29. Ning Jin, Wenlong Lu, Zhenglin Geng, and Ronald P Fedkiw. 2017. Inequality cloth. In Proc. EG/ACM Symp. Computer Animation. ACM, 16. Google ScholarDigital Library
30. Liliya Kharevych, Weiwei Yang, Yiying Tong, Eva Kanso, Jerrold E Marsden, Peter Schröder, and Matthieu Desbrun. 2006. Geometric, variational integrators for computer animation. Proc. EG/ACM Symp. Computer Animation, 43–51. Google ScholarDigital Library
31. Marin Kobilarov, Keenan Crane, and Mathieu Desbrun. 2009. Lie group integrators for animation and control of vehicles. ACM Trans. Graph. 28, 2 (2009), 16. Google ScholarDigital Library
32. D Kuhl and MA Crisfield. 1999. Energy-conserving and decaying algorithms in nonlinear structural dynamics. International journal for numerical methods in engineering 45, 5 (1999), 569–599.Google Scholar
33. Detlef Kuhl and Ekkehard Ramm. 1996. Constraint energy momentum algorithm and its application to non-linear dynamics of shells. Computer methods in applied mechanics and engineering 136, 3–4 (1996), 293–315.Google Scholar
34. Robert A LaBudde and Donald Greenspan. 1975. Energy and momentum conserving methods of arbitrary order for the numerical integration of equations of motion. Numer. Math. 25, 4 (1975), 323–346. Google ScholarDigital Library
35. Tiantian Liu, Adam W Bargteil, James F O’Brien, and Ladislav Kavan. 2013. Fast simulation of mass-spring systems. ACM Trans. Graph. 32, 6 (2013), 209:1–7. Google ScholarDigital Library
36. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans. Graph. 36, 3 (2017), 23. Google ScholarDigital Library
37. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: position-based simulation of compliant constrained dynamics. In Proc. of Motion in Games. 49–54. Google ScholarDigital Library
38. Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae-YongKim. 2014. Unified particle physics for real-time applications. ACM Trans. Graph. 33, 4 (2014), 153. Google ScholarDigital Library
39. Jerrold E Marsden and Matthew West. 2001. Discrete mechanics and variational integrators. Acta Numerica 2001 10 (2001), 357–514.Google Scholar
40. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-based elastic materials. In ACM Trans. Graph., Vol. 30. ACM, 72. Google ScholarDigital Library
41. 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. In ACM Trans. Graph., Vol. 30. 37. Google ScholarDigital Library
42. Robert I McLachlan, GRW Quispel, and Nicolas Robidoux. 1999. Geometric integration using discrete gradients. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 357, 1754 (1999), 1021–1045.Google Scholar
43. Dominik Michels, Vu Thai Luan, and Mayya Tokman. 2017. A Stiffly Accurate Integrator for Elastodynamic Problems. ACM Trans. Graph. (2017). Google ScholarDigital Library
44. Dominik L Michels, Gerrit A Sobottka, and Andreas G Weber. 2014. Exponential integrators for stiff elastodynamic problems. ACM Trans. Graph. 33, 1 (2014), 7. Google ScholarDigital Library
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.Google ScholarDigital Library
46. Jorge Nocedal and Stephen Wright. 2006. Numerical optimization.Google Scholar
47. Michael Ortiz. 1986. A note on energy conservation and stability of nonlinear time-stepping algorithms. Computers & structures 24, 1 (1986), 167–168.Google Scholar
48. Matthew Overby, George E Brown, Jie Li, and Rahul Narain. 2017. ADMM ⊇ Projective Dynamics: Fast Simulation of Hyperelastic Models with Dynamic Constraints. TVCG 23, 10 (2017), 2222–2234.Google ScholarDigital Library
49. Eric G Parker and James F O’Brien. 2009. Real-time deformation and fracture in a game environment. Proc. EG/ACM Symp. Computer Animation, 165–175. Google ScholarDigital Library
50. Juan C Simo, N Tarnow, and KK Wong. 1992. Exact energy-momentum conserving algorithms and symplectic schemes for nonlinear dynamics. Computer methods in applied mechanics and engineering 100, 1 (1992), 63–116. Google ScholarDigital Library
51. Ari Stern and Eitan Grinspun. 2009. Implicit-explicit variational integration of highly oscillatory problems. Multiscale Modeling & Simulation 7, 4 (2009), 1779–1794.Google ScholarCross Ref
52. Jonathan Su, Rahul Sheth, and Ronald Fedkiw. 2013. Energy conservation for the simulation of deformable bodies. TVCG 19, 2 (2013), 189–200. Google ScholarDigital Library
53. Yuan Sui, Jun J Pan, Hong Qin, Hao Liu, and Yun Lu. 2017. Real-time simulation of soft tissue deformation and electrocautery procedures in laparoscopic rectal cancer radical surgery. The International Journal of Medical Robotics and Computer Assisted Surgery (2017).Google Scholar
54. Demetri Terzopoulos and Kurt Fleischer. 1988a. Deformable models. The Visual Computer 4, 6 (1988), 306–331.Google ScholarCross Ref
55. Demetri Terzopoulos and Kurt Fleischer. 1988b. Modeling inelastic deformation: viscolelasticity, plasticity, fracture. In Computer Graphics (Proceedings of SIGGRAPH), Vol. 22. 269–278. Google ScholarDigital Library
56. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically deformable models. In Computer Graphics (Proceedings of SIGGRAPH), Vol. 21. 205–214. Google ScholarDigital Library
57. Bernhard Thomaszewski, Simon Pabst, and Wolfgang Straßer. 2008. Asynchronous cloth simulation. Computer Graphics International.Google Scholar
58. Pascal Volino and Nadia Magnenat-Thalmann. 2005. Implicit midpoint integration and adaptive damping for efficient cloth simulation. Computer Animation and Virtual Worlds 16, 3–4 (2005), 163–175. Google ScholarDigital Library
59. Andreas Wächter and Lorenz T Biegler. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical programming 106, 1 (2006), 25–57. Google ScholarDigital Library
60. Huamin Wang. 2015. A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Trans. Graph. 34, 6 (2015), 246. Google ScholarDigital Library
61. Huamin Wang and Yin Yang. 2016. Descent methods for elastic body simulation on the GPU. ACM Trans. Graph. 35, 6 (2016), 212. Google ScholarDigital Library
62. Mianlun Zheng, Zhiyong Yuan, Qianqian Tong, Guian Zhang, and Weixu Zhu. 2017. A novel unconditionally stable explicit integration method for finite element method. The Visual Computer (2017), 1–13. Google ScholarDigital Library
