Stabilizing Integrators for Real-Time Physics

We present a new time integration method featuring excellent stability and energy conservation properties, making it particularly suitable for realtime 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.

Dimitar Dinev, Tiantian Liu, Ladislav Kavan. Stabilizing Integrators for Real-Time Physics. ACM Transactions on Graphics 37(1) [Presented at SIGGRAPH], 2018.  

We thank Robert Bridson, Mathieu Desbrun, Eitan Grinspun, Dominik Michels, Daniele Panozzo, and Eftychios Sifakis formany inspiring discussions. We also thank Cem Yuksel, Petr Kadlecek, and Nghia Troung for proofreading. This material was based on work supported by the National Science Foundation under grants IIS-1617172 and IIS-1622360. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. We also gratefully acknowledge the support of Activision and hardware donation from NVIDIA Corporation.