“A general two-stage initialization for sag-free deformable simulations” by Hsu, Truong, Yuksel and Wu

Initializing simulations of deformable objects involves setting the rest state of all internal forces at the rest shape of the object. However, often times the rest shape is not explicitly provided. In its absence, it is common to initialize by treating the given initial shape as the rest shape. This leads to sagging, the undesirable deformation under gravity as soon as the simulation begins. Prior solutions to sagging are limited to specific simulation systems and material models, most of them cannot handle frictional contact, and they require solving expensive global nonlinear optimization problems.We introduce a novel solution to the sagging problem that can be applied to a variety of simulation systems and materials. The key feature of our approach is that we avoid solving a global nonlinear optimization problem by performing the initialization in two stages. First, we use a global linear optimization for static equilibrium. Any nonlinearity of the material definition is handled in the local stage, which solves many small local problems efficiently and in parallel. Notably, our method can properly handle frictional contact orders of magnitude faster than prior work. We show that our approach can be applied to various simulation systems by presenting examples with mass-spring systems, cloth simulations, the finite element method, the material point method, and position-based dynamics.

1. 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 ’98). ACM, New York, NY, USA, 43–54.Google ScholarDigital Library
2. Aric Bartle, Alla Sheffer, Vladimir G. Kim, Danny M. Kaufman, Nicholas Vining, and Floraine Berthouzoz. 2016. Physics-Driven Pattern Adjustment for Direct 3D Garment Editing. ACM Trans. Graph. 35, 4, Article 50 (July 2016), 11 pages.Google ScholarDigital Library
3. Jan Bender, Matthias Müller, Miguel A. Otaduy, Matthias Teschner, and Miles Macklin. 2014. A Survey on Position-Based Simulation Methods in Computer Graphics. Comput. Graph. Forum 33, 6 (sep 2014), 228–251.Google ScholarDigital Library
4. Florence Bertails, Basile Audoly, Marie-Paule Cani, Bernard Querleux, Frédéric Leroy, and Jean-Luc Lévundefinedque. 2006. Super-Helices for Predicting the Dynamics of Natural Hair. ACM Trans. Graph. 25, 3 (July 2006), 1180–1187.Google ScholarDigital Library
5. Xiang Chen, Changxi Zheng, Weiwei Xu, and Kun Zhou. 2014. An Asymptotic Numerical Method for Inverse Elastic Shape Design. ACM Trans. Graph. 33, 4, Article 95 (July 2014), 11 pages.Google ScholarDigital Library
6. Y. Chen, Q. Zhu, A. Kaufman, and S. Muraki. 1998. Physically-Based Animation of Volumetric Objects. In Proceedings of the Computer Animation (CA ’98). IEEE Computer Society, USA, 154.Google Scholar
7. Kwang-Jin Choi and Hyeong-Seok Ko. 2002. Stable but Responsive Cloth. ACM Trans. Graph. 21, 3 (July 2002), 604–611.Google ScholarDigital Library
8. 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
9. Alexandre Derouet-Jourdan, Florence Bertails-Descoubes, Gilles Daviet, and Joëlle Thollot. 2013. Inverse Dynamic Hair Modeling with Frictional Contact. ACM Trans. Graph. 32, 6, Article 159 (Nov. 2013), 10 pages.Google ScholarDigital Library
10. Alexandre Derouet-Jourdan, Florence Bertails-Descoubes, and Joëlle Thollot. 2010. Stable Inverse Dynamic Curves. ACM Trans. Graph. 29, 6, Article 137 (Dec. 2010), 10 pages.Google ScholarDigital Library
11. Mario Deuss, Daniele Panozzo, Emily Whiting, Yang Liu, Philippe Block, Olga Sorkine-Hornung, and Mark Pauly. 2014. Assembling Self-Supporting Structures. ACM Trans. Graph. 33, 6, Article 214 (nov 2014), 10 pages.Google ScholarDigital Library
12. Yu Fang, Minchen Li, Ming Gao, and Chenfanfu Jiang. 2019. Silly Rubber: An Implicit Material Point Method for Simulating Non-Equilibrated Viscoelastic and Elastoplastic Solids. ACM Trans. Graph. 38, 4, Article 118 (July 2019), 13 pages.Google ScholarDigital Library
13. Ming Gao, Xinlei Wang, Kui Wu, Andre Pradhana, Eftychios Sifakis, Cem Yuksel, and Chenfanfu Jiang. 2018. GPU Optimization of Material Point Methods. ACM Trans. Graph. 37, 6, Article 254 (Dec. 2018), 12 pages.Google ScholarDigital Library
14. Sunil Hadap. 2006. Oriented Strands: Dynamics of Stiff Multi-Body System. In Proceedings of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Vienna, Austria) (SCA ’06). Eurographics Association, Goslar, DEU, 91–100.Google Scholar
15. Yuanming Hu, Yu Fang, Ziheng Ge, Ziyin Qu, Yixin Zhu, Andre Pradhana, and Chenfanfu Jiang. 2018. A Moving Least Squares Material Point Method with Displacement Discontinuity and Two-Way Rigid Body Coupling. ACM Trans. Graph. (TOG) 37, 4 (2018), 150.Google ScholarDigital Library
16. Hayley Iben, Jacob Brooks, and Christopher Bolwyn. 2019. Holding the Shape in Hair Simulation. In ACM SIGGRAPH 2019 Talks (Los Angeles, California) (SIGGRAPH ’19). ACM, New York, NY, USA, Article 59, 2 pages.Google Scholar
17. Chenfanfu Jiang, Theodore Gast, and Joseph Teran. 2017. Anisotropic Elastoplasticity for Cloth, Knit and Hair Frictional Contact. ACM Trans. Graph. 36, 4, Article 152 (July 2017), 14 pages.Google ScholarDigital Library
18. Chenfanfu Jiang, Craig Schroeder, Andrew Selle, Joseph Teran, and Alexey Stomakhin. 2015. The Affine Particle-in-Cell Method. ACM Trans. Graph. 34, 4, Article 51 (July 2015), 10 pages.Google ScholarDigital Library
19. Danny M. Kaufman, Shinjiro Sueda, Doug L. James, and Dinesh K. Pai. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Trans. Graph. 27, 5, Article 164 (dec 2008), 11 pages.Google ScholarDigital Library
20. Doo-Won Lee and Hyeong-Seok Ko. 2001. Natural Hairstyle Modeling and Animation. Graph. Models 63, 2 (March 2001), 67–85.Google ScholarDigital Library
21. Minchen Li, Zachary Ferguson, Teseo Schneider, Timothy Langlois, Denis Zorin, Daniele Panozzo, Chenfanfu Jiang, and Danny M. Kaufman. 2020. Incremental Potential Contact: Intersection-and Inversion-Free, Large-Deformation Dynamics. ACM Trans. Graph. 39, 4, Article 49 (jul 2020), 20 pages.Google Scholar
22. Mickaël Ly, Romain Casati, Florence Bertails-Descoubes, Mélina Skouras, and Laurence Boissieux. 2018. Inverse Elastic Shell Design with Contact and Friction. ACM Trans. Graph. 37, 6, Article 201 (dec 2018), 16 pages.Google ScholarDigital Library
23. Miles Macklin and Matthias Muller. 2021. A Constraint-Based Formulation of Stable Neo-Hookean Materials. In Motion, Interaction and Games (Virtual Event, Switzerland) (MIG ’21). ACM, New York, NY, USA, Article 12, 7 pages.Google Scholar
24. Miles Macklin, Matthias Müller, and Nuttapong Chentanez. 2016. XPBD: Position-Based Simulation of Compliant Constrained Dynamics. In Proceedings of the 9th International Conference on Motion in Games (Burlingame, California) (MIG ’16). ACM, New York, NY, USA, 49–54.Google ScholarDigital Library
25. Sebastian Martin, Bernhard Thomaszewski, Eitan Grinspun, and Markus Gross. 2011. Example-Based Elastic Materials. In ACM SIGGRAPH 2011 Papers (Vancouver, British Columbia, Canada) (SIGGRAPH ’11). ACM, New York, NY, USA, Article 72, 8 pages.Google Scholar
26. Eder Miguel, Mathias Lepoutre, and Bernd Bickel. 2016. Computational Design of Stable Planar-rod Structures. ACM Trans. Graph. 35, 4, Article 86 (July 2016), 11 pages.Google ScholarDigital Library
27. Rajaditya Mukherjee, Longhua Wu, and Huamin Wang. 2018. Interactive Two-Way Shape Design of Elastic Bodies. Proc. ACM Comput. Graph. Interact. Tech. 1, 1, Article 11 (July 2018), 17 pages.Google ScholarDigital Library
28. Matthias Müller, Julie Dorsey, Leonard McMillan, Robert Jagnow, and Barbara Cutler. 2002. Stable Real-Time Deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (San Antonio, Texas) (SCA ’02). ACM, New York, NY, USA, 49–54.Google ScholarDigital Library
29. Jesús Pérez, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, José A. Canabal, Robert Sumner, and Miguel A. Otaduy. 2015. Design and Fabrication of Flexible Rod Meshes. ACM Trans. Graph. 34, 4, Article 138 (July 2015), 12 pages.Google ScholarDigital Library
30. Christian Schumacher, Bernhard Thomaszewski, Stelian Coros, Sebastian Martin, Robert Sumner, and Markus Gross. 2012. Efficient Simulation of Example-Based Materials. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Lausanne, Switzerland) (SCA ’12). Eurographics Association, Goslar, DEU, 1–8.Google ScholarDigital Library
31. Andrew Selle, Michael Lentine, and Ronald Fedkiw. 2008. A Mass Spring Model for Hair Simulation. ACM Trans. Graph. 27, 3 (aug 2008), 1–11.Google ScholarDigital Library
32. Hijung V. Shin, Christopher F. Porst, Etienne Vouga, John Ochsendorf, and Frédo Durand. 2016. Reconciling Elastic and Equilibrium Methods for Static Analysis. ACM Trans. Graph. 35, 2, Article 13 (feb 2016), 16 pages.Google ScholarDigital Library
33. Eftychios Sifakis and Jernej Barbic. 2012. FEM Simulation of 3D Deformable Solids: A Practitioner’s Guide to Theory, Discretization and Model Reduction. In ACM SIGGRAPH 2012 Courses (Los Angeles, California) (SIGGRAPH ’12). ACM, New York, NY, USA, Article 20, 50 pages.Google ScholarDigital Library
34. Mélina Skouras, Bernhard Thomaszewski, Bernd Bickel, and Markus Gross. 2012. Computational Design of Rubber Balloons. Comput. Graph. Forum 31, 2pt4 (May 2012), 835–844.Google ScholarDigital Library
35. Mélina Skouras, Bernhard Thomaszewski, Stelian Coros, Bernd Bickel, and Markus Gross. 2013. Computational Design of Actuated Deformable Characters. ACM Trans. Graph. 32, 4, Article 82 (July 2013), 10 pages.Google ScholarDigital Library
36. Alexey Stomakhin, Craig Schroeder, Lawrence Chai, Joseph Teran, and Andrew Selle. 2013. A Material Point Method for Snow Simulation. ACM Trans. Graph. 32, 4, Article 102 (July 2013), 10 pages.Google ScholarDigital Library
37. Andre Pradhana Tampubolon, Theodore Gast, Gergely Klár, Chuyuan Fu, Joseph Teran, Chenfanfu Jiang, and Ken Museth. 2017. Multi-species simulation of porous sand and water mixtures. ACM Trans. Graph. (TOG) 36, 4 (2017), 1–11.Google ScholarDigital Library
38. Demetri Terzopoulos. 1995. Heating and melting deformable models (from goop to glop). In Graphics interface, Vol. 89. Canadian Information Processing Society, Toronto, Ontario, Canada, 219–226.Google Scholar
39. Demetri Terzopoulos, John Platt, Alan Barr, and Kurt Fleischer. 1987. Elastically Deformable Models. SIGGRAPH Comput. Graph. 21, 4 (Aug. 1987), 205–214.Google ScholarDigital Library
40. Christopher D. Twigg and Doug L. James. 2008. Backward Steps in Rigid Body Simulation. ACM Trans. Graph. 27, 3, Article 25 (Aug. 2008), 10 pages.Google ScholarDigital Library
41. Christopher D. Twigg and Zoran Kačić-Alesić. 2011. Optimization for Sag-Free Simulations. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (Vancouver, British Columbia, Canada) (SCA ’11). ACM, New York, NY, USA, 225–236.Google Scholar
42. Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. 2020. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17 (2020), 261–272.Google ScholarCross Ref
43. Edwin A. H. Vollebregt. 2014. The Bound-Constrained Conjugate Gradient Method for Non-negative Matrices. Journal of Optimization Theory and Applications 162, 3 (01 Sep 2014), 931–953.Google ScholarDigital Library
44. Andreas Wächter and Lorenz T. Biegler. 2006. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106 (2006), 25–57.Google ScholarCross Ref
45. Bin Wang, Longhua Wu, KangKang Yin, Uri Ascher, Libin Liu, and Hui Huang. 2015. Deformation Capture and Modeling of Soft Objects. ACM Trans. Graph. 34, 4, Article 94 (July 2015), 12 pages.Google ScholarDigital Library
46. Huamin Wang. 2015. A Chebyshev Semi-Iterative Approach for Accelerating Projective and Position-Based Dynamics. ACM Trans. Graph. 34, 6, Article 246 (Oct. 2015), 9 pages.Google ScholarDigital Library
47. Emily Whiting, John Ochsendorf, and Frédo Durand. 2009. Procedural Modeling of Structurally-Sound Masonry Buildings. ACM Trans. Graph. 28, 5 (dec 2009), 1–9.Google ScholarDigital Library
48. Kui Wu and Cem Yuksel. 2016. Real-Time Hair Mesh Simulation. In Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (Redmond, Washington) (I3D ’16). ACM, New York, NY, USA, 59–64.Google ScholarDigital Library
49. Jiaxian Yao, Danny M. Kaufman, Yotam Gingold, and Maneesh Agrawala. 2017. Interactive Design and Stability Analysis of Decorative Joinery for Furniture. ACM Trans. Graph. 36, 2, Article 20 (mar 2017), 16 pages.Google ScholarDigital Library