T. F. Gast, C. Schroeder, A. Stomakhin, C. Jiang and J. M. Teran, "Optimization Integrator for Large Time Steps," in IEEE Transactions on Visualization and Computer Graphics, vol. 21, no. 10, pp. 1103-1115, Oct. 1 2015. doi: 10.1109/TVCG.2015.2459687
Practical time steps in today's state-of-the-art simulators typically rely on Newton's method to solve large systems of nonlinear equations. In practice, this works well for small time steps but is unreliable at large time steps at or near the frame rate, particularly for difficult or stiff simulations. We show that recasting backward Euler as a minimization problem allows Newton's method to be stabilized by standard optimization techniques with some novel improvements of our own. The resulting solver is capable of solving even the toughest simulations at the 24 Hz frame rate and beyond. We show how simple collisions can be incorporated directly into the solver through constrained minimization without sacrificing efficiency. We also present novel penalty collision formulations for self collisions and collisions against scripted bodies designed for the unique demands of this solver. Finally, we show that these techniques improve the behavior of Material Point Method (MPM) simulations by recasting it as an optimization problem.