“Stable constrained dynamics” by Tournier, Nesme, Gilles and Faure

We present a unification of the two main approaches to simulate deformable solids, namely elasticity and constraints. Elasticity accurately handles soft to moderately stiff objects, but becomes numerically hard as stiffness increases. Constraints efficiently handle high stiffness, but when integrated in time they can suffer from instabilities in the nullspace directions, generating spurious transverse vibrations when pulling hard on thin inextensible objects or articulated rigid bodies. We show that geometric stiffness, the tensor encoding the change of force directions (as opposed to intensities) in response to a change of positions, is the missing piece between the two approaches. This previously neglected stiffness term is easy to implement and dramatically improves the stability of inextensible objects and articulated chains, without adding artificial bending forces. This allows time step increases up to several orders of magnitude using standard linear solvers.

1. Anitescu, M., and Hart, G. D. 2004. A fixed-point iteration approach for multibody dynamics with contact and small friction. Mathematical Programming 101.Google Scholar
2. Ascher, U. M., H. Chin, L. R. Petzold, and Reich, S. 1995. Stabilization of Constrained Mechanical Systems with DAEs and Invariant Manifold. Journal of Mechanics of Structures and Machines 23.Google ScholarCross Ref
3. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proc. 25th annual conference on Computer graphics and interactive techniques (ACM SIGGRAPH). Google ScholarDigital Library
4. Baraff, D. 1996. Linear-time Dynamics Using Lagrange Multipliers. In Proc. 23th annual conference on Computer graphics and interactive techniques (ACM SIGGRAPH). Google ScholarDigital Library
5. Barzel, R., and Barr, A. H. 1988. A Modeling System Based On Dynamic Constraints. In Computer Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
6. Bender, J., Müller, M., Otaduy, M. A., and Teschner, M. 2013. Position-based Methods for the Simulation of Solid Objects in Computer Graphics. In Computer Graphics Forum (Eurographics State of the Art Report).Google Scholar
7. Bertails, F., Audoly, B., Cani, M.-P., Querleux, B., Leroy, F., and Lévêque, J.-L. 2006. Super-helices for Predicting the Dynamics of Natural Hair. In ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
8. Bouaziz, S., Martin, S., Liu, T., Kavan, L., and Pauly, M. 2014. Projective Dynamics: Fusing Constraint Projections for Fast Simulation. ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
9. Cline, M. B., and Pai, D. K. 2003. Post-stabilization for rigid body simulation with contact and constraints. In International Conference on Robotics and Automation.Google Scholar
10. Cook, R. D. 1995. Finite Element Modeling for Stress Analysis. JohnWiley & Sons, Inc. Google ScholarDigital Library
11. Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2008. Realistic Haptic Rendering of Interacting Deformable Objects in Virtual Environments. CoRR.Google Scholar
12. Erleben, K. 2013. Numerical Methods for Linear Complementarity Problems in Physics-based Animation. In ACM SIGGRAPH Courses. Google ScholarDigital Library
13. Faure, F., Duriez, C., Delingette, H., Allard, J., Gilles, B., Marchesseau, S., Talbot, H., Courtecuisse, H., Bousquet, G., Peterlik, I., and Cotin, S. 2012. SOFA: A Multi-Model Framework for Interactive Physical Simulation. In Soft Tissue Biomechanical Modeling for Computer Assisted Surgery. Springer. http://www.sofa-framework.org.Google Scholar
14. Featherstone, R. 1987. Robot Dynamics Algorithm. Kluwer Academic Publishers, Norwell, MA, USA. Google ScholarDigital Library
15. García-Fernández, I., Pla-Castells, M., and Martínez-Durá, R. J. 2008. Elevation Cable Modeling for Interactive Simulation of Cranes. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
16. Gascuel, J.-d., and Gascuel, M.-P. 1994. Displacement constraints for interactive modeling and animation of articulated structures. Visual Computer 10, 4.Google ScholarCross Ref
17. Goldenthal, R., Harmon, D., Fattal, R., Bercovier, M., and Grinspun, E. 2007. Efficient Simulation of Inextensible Cloth. ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
18. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
19. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Transactions on Graphics (Proc. SIGGRAPH Asia). Google ScholarDigital Library
20. Kaufman, D. M., Tamstorf, R., Smith, B., Aubry, J.- M., and Grinspun, E. 2014. Adaptive Nonlinearity for Collisions in Complex Rod Assemblies. ACM Transaction on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
21. Lacoursière, C. 2007. Ghosts and machines: regularized variational methods for interactive simulations of multibodies with dry frictional contacts. PhD thesis, Umeå University.Google Scholar
22. Macklin, M., Müller, M., Chentanez, N., and Kim, T.- Y. 2014. Unified Particle Physics for Real-Time Applications. ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
23. Mirtich, B. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. PhD thesis, University of California. Google ScholarDigital Library
24. Müller, M., Heidelberger, B., Hennix, M., and Ratcliff, J. 2006. Position Based Dynamics. Proc. VRIPhys.Google Scholar
25. Narain, R., Samii, A., and O’Brien, J. F. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Transactions on Graphics (Proc. SIGGRAPH Asia). Google ScholarDigital Library
26. Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically Based Deformable Models in Computer Graphics. Computer Graphics Forum (Eurographics State of the Art Report).Google Scholar
27. Nocedal, J., and Wright, S. J. 2006. Numerical Optimization (2nd ed.). Springer-Verlag.Google Scholar
28. Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit Contact Handling for Deformable Objects. Computer Graphics Forum (Proc. of Eurographics).Google Scholar
29. Papadopoulo, T., and Lourakis, M. I. A. 2000. Estimating the jacobian of the singular value decomposition: Theory and applications. In Proc. European Conference on Computer Vision. Google ScholarDigital Library
30. Provot, X. 1995. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Proc. Graphics Interface.Google Scholar
31. Servin, M., and Lacoursière, C. 2008. Rigid Body Cable for Virtual Environments. IEEE Transactions on Visualization and Computer Graphics 14. Google ScholarDigital Library
32. Servin, M., Lacoursière, C., and Melin, N. 2006. Interactive simulation of elastic deformable materials. In Proc. SIGRAD.Google Scholar
33. Servin, M., Lacoursière, C., Nordfelth, F., and Bodin, K. 2011. Hybrid, Multiresolution Wires with Massless Frictional Contacts. IEEE Trans. on Visualization and Computer Graphics 17. Google ScholarDigital Library
34. Sifakis, E., Shinar, T., Irving, G., and Fedkiw, R. 2007. Hybrid Simulation of Deformable Solids. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
35. Sueda, S., Jones, G. L., Levin, D. I. W., and Pai, D. K. 2011. Large-scale Dynamic Simulation of Highly Constrained Strands. In ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
36. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In Proc. ACM SIGGRAPH/Eurographics Symposium on Computer Animation. Google ScholarDigital Library
37. Thomaszewski, B., Pabst, S., and Strasser, W. 2009. Continuum-based Strain Limiting. Computer Graphics Forum (Proc. Eurographics).Google Scholar
38. Tomcin, R., Sibbing, D., and Kobbelt, L. 2014. Efficient enforcement of hard articulation constraints in the presence of closed loops and contacts. Computer Graphics Forum (Proc. Eurographics). Google ScholarDigital Library
39. Wang, H., O’brien, J. F., and Ramamoorthi, R. 2010. Multi-Resolution Isotropic Strain Limiting. ACM Transactions on Graphics (Proc. SIGGRAPH Asia). Google ScholarDigital Library
40. Weinstein, R., Teran, J., and Fedkiw, R. 2006. Dynamic simulation of articulated rigid bodies with contact and collision. IEEE Transactions on Visualization and Computer Graphics. Google ScholarDigital Library
41. Witkin, A. 1997. Physically Based Modeling: Principles and Practice — Constrained Dynamics. Computer Graphics.Google Scholar
42. Zheng, C., and James, D. L. 2011. Toward High-Quality Modal Contact Sound. ACM Transactions on Graphics (Proc. SIGGRAPH). Google ScholarDigital Library
43. Zienkiewicz, O. C., and Taylor, R. L. 2000. The Finite Element Method: Solid Mechanics, 5 ed., vol. 2. Butterworth-Heinemann.Google Scholar