Fast Simulation of Mass-Spring Systems


Tiantian Liu
University of Pennsylvania
 
Adam W. Bargteil
University of Utah
 
James F. O'Brien
University of California, Berkeley
 
Ladislav Kavan
University of Pennsylvania
 


When used to simulate the motion of a cloth sheet with 6561 vertices our method (left) produces real-time results on a single CPU comparable to those obtained with a much slower off-line method (middle). The method also performs well for one dimensional strands, volumetric objects, and character clothing (right).



Abstract

We describe a scheme for time integration of mass-spring systems that makes use of a solver based on block coordinate descent. This scheme provides a fast solution for classical linear (Hookean) springs. We express the widely used implicit Euler method as an energy minimization problem and introduce spring directions as auxiliary unknown variables. The system is globally linear in the node positions, and the non-linear terms involving the directions are strictly local. Because the global linear system does not depend on run-time state, the matrix can be pre-factored, allowing for very fast iterations. Our method converges to the same final result as would be obtained by solving the standard form of implicit Euler using Newton's method. Although the asymptotic convergence of Newton's method is faster than ours, the initial ratio of work to error reduction with our method is much faster than Newton's. For real-time visual applications, where speed and stability are more important than precision, we obtain visually acceptable results at a total cost per timestep that is only a fraction of that required for a single Newton iteration. When higher accuracy is required, our algorithm can be used to compute a good starting point for subsequent Newton's iteration.






Publication

Tiantian Liu, Adam W. Bargteil, James F. O'Brien, Ladislav Kavan. Fast Simulation of Mass-Spring Systems. ACM Transaction on Graphics 32(6) [Proceedings of SIGGRAPH Asia], 2013.  


Links and Downloads

Paper

 
BibTeX

 
Code (Visual Studio)



Acknowledgements

The authors thank Stelian Coros, Alec Jacobson, Lily Kharevych, Sebastian Martin, Dominik Michels, Rahul Narain, Mark Pauly, Bernhard Thomaszewski, Andreas Weber, and Changxi Zheng for many insightful discussions, Rahul Narain and Armin Samii for help with ARCSim, and the anonymous reviewers for their helpful suggestions. The original ideas for this work were developed at the Bellairs workshop sponsored by McGill University and organized by Paul Kry. This work was supported in part by funding from the Intel Science and Technology Center for Visual Computing, gifts from Pixar Animation Studios, Adobe Systems Incorporated, and National Science Foundation Awards IIS-1249756 and CNS-0855167.