“Adaptive rigidification of elastic solids” by Mercier-Aubin, Kry, Winter and Levin

We present a method for reducing the computational cost of elastic solid simulation by treating connected sets of non-deforming elements as rigid bodies. Non-deforming elements are identified as those where the strain rate squared Frobenius norm falls below a threshold for several frames. Rigidification uses a breadth first search to identify connected components while avoiding connections that would form hinges between rigid components. Rigid elements become elastic again when their approximate strain velocity rises above a threshold, which is fast to compute using a single iteration of conjugate gradient with a fixed Laplacian-based incomplete Cholesky preconditioner. With rigidification, the system size to solve at each time step can be greatly reduced, and if all elastic element become rigid, it reduces to solving the rigid body system. We demonstrate our results on a variety of 2D and 3D examples, and show that our method is likewise especially beneficial in contact rich examples.

1. Svetlana Artemova and Stephane Redon. 2012. Adaptively Restrained Particle Simulations. Phys. Rev. Lett. 109 (2012), 190201. Issue 19.Google ScholarCross Ref
2. David Baraff and Andrew Witkin. 1998. Large Steps in Cloth Simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH 1998). Association for Computing Machinery, New York, NY, USA, 43–54. Google ScholarDigital Library
3. Jernej Barbič and Doug L. James. 2005. Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Trans. Graph. 24, 3 (July 2005), 982–990. Google ScholarDigital Library
4. Joachim Baumgarte. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Computer methods in applied mechanics and engineering 1, 1 (1972), 1–16.Google Scholar
5. Desai Chen, David I. W. Levin, Wojciech Matusik, and Danny M. Kaufman. 2017. Dynamics-Aware Numerical Coarsening for Fabrication Design. ACM Trans. Graph. 36, 4, Article 84 (July 2017), 15 pages.Google ScholarDigital Library
6. M.B. Cline and D.K. Pai. 2003. Post-stabilization for rigid body simulation with contact and constraints. In 2003 IEEE International Conference on Robotics and Automation, Vol. 3. 3744–3751 vol.3. Google ScholarCross Ref
7. Eulalie Coevoet, Otman Benchekroun, and Paul G. Kry. 2020. Adaptive Merging for Rigid Body Simulation. ACM Trans. Graph. 39, 4, Article 35 (2020), 12 pages.Google ScholarDigital Library
8. Hadrien Courtecuisse, Jérémie Allard, Christian Duriez, and Stéphane Cotin. 2010. Asynchronous Preconditioners for Efficient Solving of Non-linear Deformations. In Workshop in Virtual Reality Interactions and Physical Simulation “VRIPHYS” (2010). Google ScholarCross Ref
9. Gilles Debunne, Mathieu Desbrun, Marie-Paule Cani, and Alan H. Barr. 2001. Dynamic Real-time Deformations Using Space & Time Adaptive Sampling. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). ACM, New York, NY, USA, 31–36.Google Scholar
10. Kenny Erleben. 2004. Stable, robust, and versatile multibody dynamics animation. Ph.D. Dissertation. University of Copenhagen.Google Scholar
11. Benjamin Gilles, Guillaume Bousquet, Francois Faure, and Dinesh K. Pai. 2011. Frame-Based Elastic Models. ACM Trans. Graph. 30, 2, Article 15 (April 2011), 12 pages. Google ScholarDigital Library
12. Eitan Grinspun, Petr Krysl, and Peter Schröder. 2002. CHARMS: A Simple Framework for Adaptive Simulation. ACM Trans. Graph. 21, 3 (2002), 281–290.Google ScholarDigital Library
13. Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O’Brien. 2012. Updated Sparse Cholesky Factors for Corotational Elastodynamics. ACM Trans. Graph. 31, 5, Article 123 (sep 2012), 13 pages. Google ScholarDigital Library
14. Alec Jacobson et al. 2021. gptoolbox: Geometry Processing Toolbox. http://github.com/alecjacobson/gptoolbox.Google Scholar
15. Johan Jansson and Joris S. M. Vergeest. 2003. Combining Deformable- and Rigid-Body Mechanics Simulation. Vis. Comput. 19, 5 (aug 2003), 280–290. Google ScholarDigital Library
16. Lily Kharevych, Patrick Mullen, Houman Owhadi, and Mathieu Desbrun. 2009. Numerical Coarsening of Inhomogeneous Elastic Materials. ACM Trans. Graph. 28, 3, Article 51 (July 2009), 8 pages. Google ScholarDigital Library
17. Theodore Kim and Doug L. James. 2009. Skipping Steps in Deformable Simulation with Online Model Reduction. ACM Trans. Graph. (2009).Google Scholar
18. Tae-Yong Kim, Nuttapong Chentanez, and Matthias Müller-Fischer. 2012. Long Range Attachments – a Method to Simulate Inextensible Clothing in Computer Games. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Lausanne, Switzerland) (SCA ’12). Eurographics Association, Goslar, DEU, 305–310.Google ScholarDigital Library
19. J. Lenoir and S. Fonteneau. 2004. Mixing deformable and rigid-body mechanics simulation. In Proceedings Computer Graphics International, 2004. 327–334. Google ScholarCross Ref
20. Tiantian Liu, Sofien Bouaziz, and Ladislav Kavan. 2017. Quasi-Newton Methods for Real-Time Simulation of Hyperelastic Materials. ACM Trans. Graph. 36, 4, Article 116a (May 2017), 16 pages. Google ScholarDigital Library
21. Pierre-Luc Manteaux, François Faure, Stephane Redon, and Marie-Paule Cani. 2013. Exploring the Use of Adaptively Restrained Particles for Graphics Simulations. In VRIPHYS 2013 – 10th Workshop on Virtual Reality Interaction and Physical Simulation. 17–24.Google Scholar
22. Richard M. Murray, S. Shankar Sastry, and Li Zexiang. 1994. A Mathematical Introduction to Robotic Manipulation (1st ed.). CRC Press, Inc., USA.Google ScholarDigital Library
23. Rahul Narain, Armin Samii, and James F. O’Brien. 2012. Adaptive Anisotropic Remeshing for Cloth Simulation. ACM Trans. Graph. 31, 6, Article 152 (2012), 10 pages.Google ScholarDigital Library
24. Matthieu Nesme, Paul G. Kry, Lenka Jeřábková, and François Faure. 2009. Preserving Topology and Elasticity for Embedded Deformable Models. ACM Trans. Graph. 28, 3, Article 52 (July 2009), 9 pages. Google ScholarDigital Library
25. H. Schmidl and V. J. Milenkovic. 2004. A fast impulsive contact suite for rigid body simulation. IEEE Transactions on Visualization and Computer Graphics 10, 2 (2004), 189–197.Google ScholarDigital Library
26. Camille Schreck, Damien Rohmer, Stefanie Hahmann, Marie-Paule Cani, Shuo Jin, Charlie C. L. Wang, and Jean-Francis Bloch. 2016. Nonsmooth Developable Geometry for Interactively Animating Paper Crumpling. ACM Trans. Graph. 35, 1, Article 10 (Dec. 2016), 18 pages. Google ScholarDigital Library
27. Russell Smith et al. 2005. Open dynamics engine user manual. (2005).Google Scholar
28. Yun Teng, Mark Meyer, Tony DeRose, and Theodore Kim. 2015. Subspace Condensation: Full Space Adaptivity for Subspace Deformations. ACM Trans. Graph. 34, 4, Article 76 (July 2015), 9 pages. Google ScholarDigital Library
29. D. Terzopoulos and A. Witkin. 1988. Physically based models with rigid and deformable components. IEEE Computer Graphics and Applications (1988).Google Scholar
30. Maxime Tournier, Matthieu Nesme, Francois Faure, and Benjamin Gilles. 2014. Seamless adaptivity of elastic models. In Proceedings of Graphics Interface 2014 (Montréal, Québec, Canada) (GI 2014). 17–24.Google ScholarDigital Library
31. Yin Yang, Guodong Rong, Luis Torres, and Xiaohu Guo. 2010. Real-time hybrid solid simulation: spectral unification of deformable and rigid materials. Computer Animation and Virtual Worlds 21, 3–4 (2010), 151–159. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/cav.373 Google ScholarCross Ref