“Fast simulation of mass-spring systems”
Conference:
Type(s):
Title:
- Fast simulation of mass-spring systems
Session/Category Title: Dressing and Jiggling Soft Bodies
Presenter(s)/Author(s):
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.
References:
1. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of SIGGRAPH 1998, 43–54.
2. Bergou, M., Mathur, S., Wardetzky, M., and Grinspun, E. 2007. TRACKS: Toward directable thin shells. ACM Trans. Graph. 26, 3, 50:1–50:10.
3. Bonet, J., and Wood, R. D. 1997. Nonlinear continuum mechanics for finite element analysis. Cambridge university press.
4. Botsch, M., Bommes, D., and Kobbelt, L. 2005. Efficient linear system solvers for mesh processing. In Mathematics of Surfaces XI. Springer, 62–83.
5. Boyd, S., and Vandenberghe, L. 2004. Convex optimization. Cambridge university press.
6. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. In Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, 28–36.
7. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4, 38:1–38:6.
8. Choi, K.-J., and Ko, H.-S. 2005. Stable but responsive cloth. In ACM SIGGRAPH 2005 Courses, ACM, 1.
9. Goldenthal, R., Harmon, D., Fattal, R., Bercovier, M., and Grinspun, E. 2007. Efficient simulation of inextensible cloth. ACM Trans. Graph. 26, 3, 49:1–49:8.
10. Guennebaud, G., Jacob, B., et al., 2013. Eigen v3. http://eigen.tuxfamily.org.
11. Hahn, F., Martin, S., Thomaszewski, B., Sumner, R., Coros, S., and Gross, M. 2012. Rig-space physics. ACM Transactions on Graphics (TOG) 31, 4, 72.
12. Harmon, D., Vouga, E., Tamstorf, R., and Grinspun, E. 2008. Robust treatment of simultaneous collisions. In ACM Transactions on Graphics (TOG), vol. 27, ACM, 23.
13. Hecht, F., Lee, Y. J., Shewchuk, J. R., and O’brien, J. F. 2012. Updated sparse cholesky factors for corotational elastodynamics. ACM Transactions on Graphics (TOG) 31, 5, 123.
14. Kharevych, L., Yang, W., Tong, Y., Kanso, E., Marsden, J. E., Schröder, P., and Desbrun, M. 2006. Geometric, variational integrators for computer animation. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, 43–51.
15. Martin, S., Thomaszewski, B., Grinspun, E., and Gross, M. 2011. Example-based elastic materials. In ACM Transactions on Graphics (TOG), vol. 30, ACM, 72.
16. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2007. Position based dynamics. J. Vis. Comun. Image Represent. 18, 2, 109–118.
17. Narain, R., Samii, A., and O’Brien, J. F. 2012. Adaptive anisotropic remeshing for cloth simulation. ACM Transactions on Graphics (TOG) 31, 6, 152.
18. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.
19. Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 2007. Numerical recipes 3rd edition: The art of scientific computing. Cambridge university press.
20. Provot, X. 1995. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Graphics Interface 1995, 147–154.
21. Selle, A., Lentine, M., and Fedkiw, R. 2008. A mass spring model for hair simulation. In ACM Transactions on Graphics (TOG), vol. 27, ACM, 64.
22. Shewchuk, J. R. 1994. An introduction to the conjugate gradient method without the agonizing pain. Tech. rep., Pittsburgh, PA, USA.
23. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. Symposium on Geometry Processing, 109–116.
24. Stam, J. 2009. Nucleus: towards a unified dynamics solver for computer graphics. In IEEE Int. Conf. on CAD and Comput. Graph., 1–11.
25. Stern, A., and Desbrun, M. 2006. Discrete geometric mechanics for variational time integrators. In ACM SIGGRAPH 2006 Courses, ACM, 75–80.
26. Stern, A., and Grinspun, E. 2009. Implicit-explicit variational integration of highly oscillatory problems. Multiscale Modeling & Simulation 7, 4, 1779–1794.
27. Su, J., Sheth, R., and Fedkiw, R. 2013. Energy conservation for the simulation of deformable bodies. IEEE Trans. Vis. Comput. Graph. 19, 2, 189–200.
28. Tang, M., Manocha, D., and Tong, R. 2010. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games, ACM, 7–13.
29. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. SIGGRAPH Comput. Graph. 21, 4 (Aug.), 205–214.
30. Teschner, M., Heidelberger, B., Muller, M., and Gross, M. 2004. A versatile and robust model for geometrically complex deformable solids. In Computer Graphics International, 2004. Proceedings, IEEE, 312–319.
31. Thomaszewski, B., Pabst, S., and Strasser, W. 2009. Continuum-based strain limiting. Comput. Graph. Forum 28, 2, 569–576.
32. Wang, H., O’Brien, J., and Ramamoorthi, R. 2010. Multiresolution isotropic strain limiting. ACM Transactions on Graphics (TOG) 29, 6, 156.
