We examine a variety of numerical methods that arise when considering dynamical systems in the context of physics-based simulations of deformable objects. Such problems arise in various applications, including animation, robotics, control and fabrication. The goals and merits of suitable numerical algorithms for these applications are different from those of typical numerical analysis research in dynamical systems. Here the mathematical model is not fixed a priori but must be adjusted as necessary to capture the desired behaviour, with an emphasis on effectively producing lively animations of objects with complex geometries. Results are often judged by how realistic they appear to observers (by the "eye-norm") as well as by the efficacy of the numerical procedures employed. And yet, we show that with an adjusted view numerical analysis and applied mathematics can contribute significantly to the development of appropriate methods and their analysis in a variety of areas including finite element methods, stiff and highly oscillatory ODEs, model reduction, and constrained optimization.
Citation: |
Figure 1. Deformable articulated objects: a swaying tree and a constrained jelly brick; cf. [13]
Figure 4. Computational costs for a swinging armadillo simulation [13]. The cost of exponential integrators including ERE becomes prohibitive as the stiffness parameter increases. By contrast, the cost of SIERE does not grow significantly with stiffness
Figure 6. Potential energy plots for different integrators applied to a soft object: BE (thick solid line), SIERE with $ s = 10 $ (thin solid line), STR-SBDF2ERE with $ s = 10 $ (dash-dot), TR-BDF2 (dotted), and SDIRK (dashed). A soft beam is fixed at its ends and is subjected to gravity. Notice that the TR-BDF2 and SDIRK energies do not decay by much, whereas BE dissipates energy quickly. SIERE is less damping than BE but still much more damping than STR-SBDF2ERE, which in turn is still more damping than the two DIRK methods
Figure 7. With large enough time steps, velocity based contact constraints may reject plausible steps. If a vertex in blue is constrained to have a strictly positive velocity with respect to the convex gray contact surface, then plausibly valid next-step configurations (right) may be erroneously rejected
[1] | A. H. Al-Mohy and N. J. Higham, Computing the action of the matrix exponential, with an application to exponential integrators, SIAM J. Sci. Comput., 33 (2011,488–511. doi: 10.1137/100788860. |
[2] | R. Alexander, Diagonally implicit runge-kutta methods for stiff ode's, SIAM J. Numer. Anal., 14 (1977), 1006-1021. doi: 10.1137/0714068. |
[3] | U. Ascher, Numerical Methods for Evolutionary Differential Equations, Computational Science & Engineering, 5. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. doi: 10.1137/1.9780898718911. |
[4] | U. Ascher and L. Petzold, Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. |
[5] | J. Awrejcewicz, D. Grzelczyk and Y. Pyryev, A novel dry friction modeling and its impact on differential equations computation and lyapunov exponents estimation, Journal of Vibroengineering, 10 (2008). |
[6] | D. Baraff and A. Witkin, Large steps in cloth simulation, Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, (1998), 43–54. doi: 10.1145/280814.280821. |
[7] | J. Barbic and D. James, Real-time subspace integration for st. venant-kirchhoff deformable models, ACM Trans. Graphics, 24 (2005), 982-990. doi: 10.1145/1186822.1073300. |
[8] | E. Boxerman and U. Ascher, Decomposing cloth, Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Eurographics Association, (2004), 153–161. doi: 10.1145/1028523.1028543. |
[9] | J. C. Butcher and D. J. L. Chen, A new type of singly-implicit runge-kutta method, Appl. Numer. Math., 34 (2000), 179-188. doi: 10.1016/S0168-9274(99)00126-9. |
[10] | D. Chen, D. I. W. Levin, W. Matusik and D. M. Kaufman, Dynamics-aware numerical coarsening for fabrication design, ACM Trans. Graph., 36 (2017), 1-15. doi: 10.1145/3072959.3073669. |
[11] | Y. J. Chen, U. Ascher and D. K. Pai, Exponential rosenbrock-euler integrators for elastodynamic simulation, IEEE Transactions on Visualization and Computer Graphics, 24 (2018), 2702-2713. doi: 10.1109/TVCG.2017.2768532. |
[12] | Y. J. (Edwin) Chen, D. I. W. Levin, D. M. Kaufman, U. M. Ascher and D. K. Pai, Eigenfit for consistent elastodynamic simulation across mesh resolution, Proceedings SCA, (2019), Article No. 5, 1–13. doi: 10.1145/3309486.3340248. |
[13] | Y. J. (Edwin) Chen, S. H. Sheen, U. M. Ascher and D. K. Pai, Siere: A hybrid semi-implicit exponential integrator for efficiently simulating stiff deformable objects, ACM Transactions on Graphics (TOG), 40 (2020), 1–12. doi: 10.1145/3410527. |
[14] | J. Chung and G. M. Hulbert, A time integration algorithm for structural dynamics with improved numerical dissipation: The generalized-$\alpha$ method, J. Applied Mech., 60 (1993), 371-375. doi: 10.1115/1.2900803. |
[15] | P. G. Ciarlet, Three-Dimensional Elasticity, Recherches en Mathématiques Appliquées [Research in Applied Mathematics], 1. Masson, Paris, 1986. |
[16] | G. Daviet, F. Bertails-Descoubes and L. Boissieux, A hybrid iterative solver for robustly capturing coulomb friction in hair dynamics, ACM Trans. Graph., 30 (2011), 1-12. doi: 10.1145/2024156.2024173. |
[17] | G. De Saxcé and Z. Q. Feng, The bipotential method: A constructive approach to design the complete contact law with friction and improved numerical algorithms, Math. Comput. Modelling, 28 (1998), 225-245. doi: 10.1016/S0895-7177(98)00119-8. |
[18] | K. Erleben, Rigid body contact problems using proximal operators, Proceedings of the ACM SIGGRAPH / Eurographics Symposium on Computer Animation, (2017), Article No. 13, 1–12. doi: 10.1145/3099564.3099575. |
[19] | Z. Ferguson, M. Li, T. Schneider, F. Gil-Ureta, T. Langlois, C. Jiang, D. Zorin, D. M. Kaufman and D. Panozzo, Intersection-free rigid body dynamics, ACM Transactions on Graphics (SIGGRAPH), 40 (2021). |
[20] | T. F. Gast, C. Schroeder, A. Stomakhin, C. Jiang and J. M. Teran, Optimization integrator for large time steps, IEEE Trans Visualization and Computer Graphics, 21 (2015), 1103-1115. doi: 10.1109/TVCG.2015.2459687. |
[21] | M. Geilinger, D. Hahn, J. Zehnder, M. Bacher, B. Thomaszewski and S. Coros, Add: Analytically differentiable dynamics for multi-body systems with frictional contact, ACM Transactions on Graphics (TOG), 39 (2020), 1-15. doi: 10.1145/3414685.3417766. |
[22] | E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration, Springer Series in Computational Mathematics, 31. Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-662-05018-7. |
[23] | E. Hairer and G. Wanner, Solving Ordinary Differential Equations Ⅱ: Stiff and Differential-Algebraic Problems, 2$^nd$ edition, Springer Series in Computational Mathematics, 14. Springer-Verlag, Berlin, 1996. doi: 10.1007/978-3-642-05221-7. |
[24] | C. Kane, J. Marsden, M. Ortiz and M. West, Variational integrators and the Newmark algorithm for conservative and dissipative mechanical systems, Internat. J. Numer. Methods Engrg., 49 (2000), 1295-1325. doi: 3.0.CO;2-W">10.1002/1097-0207(20001210)49:10<1295::AID-NME993>3.0.CO;2-W. |
[25] | D. M. Kaufman, S. Sueda, D. L. James and D. K. Pai, Staggered projections for frictional contact in multibody systems, ACM Transactions on Graphics (SIGGRAPH Asia 2008), 27 (2008), 1-11. doi: 10.1145/1457515.1409117. |
[26] | R. Kikuuwe, N. Takesue, A. Sano, H. Mochiyama and H. Fujimoto, Fixed-step friction simulation: From classical Coulomb model to modern continuous models, 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, (2005), 1009–1016. doi: 10.1109/IROS.2005.1545579. |
[27] | E. Larionov, Y. Fan and D. K Pai, Frictional Contact on Smooth Elastic Solids, ACM Transactions on Graphics, (2021), 1–17. doi: 10.1145/3446663. |
[28] | R. J. LeVeque, Finite Difference Methods for Ordinary and Partial Differential Equations, SIAM, 2007. doi: 10.1137/1.9780898717839. |
[29] | M. Li, Z. Ferguson, T. Schneider, T. Langlois, D. Zorin, D. Panozzo, C. Jiang and D. M. Kaufman, Incremental potential contact: Intersection- and inversion-free, large-deformation dynamics, ACM Transactions on Graphics (TOG), 39 (2020), 1-20. doi: 10.1145/3386569.3392425. |
[30] | M. Li, D. M. Kaufman and C. Jiang, Codimensional Incremental Potential Contact, arXiv: 2012.04457, [cs], 2021. |
[31] | A. Longva, F. Löschner, T. Kugelstadt, J. A. Fernández-Fernández and J. Bender, Higher-order finite elements for embedded simulation, ACM Transactions on Graphics, 39 (2020), Article No. 181, 1–14. doi: 10.1145/3414685.3417853. |
[32] | F. Loschner, A. Longva, S. Jeske, T. Kugelstadt and J. Bender, Higher order time integration for deformable solids, Computer Graphics Forum, 39 (2020), 157-169. doi: 10.1111/cgf.14110. |
[33] | P. Lotstedt, Mechanical systems of rigid bodies subject to unilateral constraints, SIAM J. Appl. Math., 42 (1982), 281-296. doi: 10.1137/0142022. |
[34] | P. Lotstedt and L. Petzold, Numerical solution of nonlinear differential equations with algebraic constraints i: Convergence results for backward differentiation formulas, Math. Comp., 46 (1986), 491-516. doi: 10.2307/2007989. |
[35] | D. L. Michels, V. T. Luan and M. Tokman, A stiffly accurate integrator for elastodynamic problems, ACM Transactions on Graphics (TOG), 36 (2017), Article No.: 116, 1–14. doi: 10.1145/3072959.3073706. |
[36] | D. L. Michels and J. P. T. Mueller, Discrete computational mechanics for stiff phenomena, SIGGRAPH ASIA 2016 Courses, (2016), Article No.: 13, 1–13. doi: 10.1145/2988458.2988464. |
[37] | C. Moler and C. Van Loan, Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later, SIAM Rev., 45 (2003), 3-49. doi: 10.1137/S00361445024180. |
[38] | J. Niesen and W. M. Wright, Algorithm 919: A Krylov subspace algorithm for evaluating the $\phi$-functions appearing in exponential integrators, ACM Trans. Math. Software (TOMS), 38 (2012), Art. 22, 19pp. doi: 10.1145/2168773.2168781. |
[39] | J. Nocedal and S. Wright, Numerical Optimization, Springer Series in Operations Research. Springer-Verlag, New York, 1999. doi: 10.1007/b98874. |
[40] | D. K. Pai, K. van den Doel, D. L. James, J. Lang, J. E. Lloyd, J. L. Richmond and S. H. Yau, Scanning physical interaction behavior of 3D objects, Computer Graphics (ACM SIGGRAPH 2001 Conference Proceedings), (2001), 87–96. |
[41] | D. K. Pai, A. Rothwell, P. Wyder-Hodge, A. Wick, Y. Fan, E. Larionov, D. Harrison, D. R. Neog and C. Shing, The human touch: Measuring contact with real human soft tissues, ACM Transactions on Graphics (TOG), 37 (2018), Article No.: 58, 1–12. doi: 10.1145/3197517.3201296. |
[42] | E. Sifakis and J. Barbic, FEM simulation of 3D deformable solids: A practitioner's guide to theory, discretization and model reduction, ACM SIGGRAPH 2012 Courses, (2012), Article No.: 20, 1–50 doi: 10.1145/2343483.2343501. |
[43] | B. Smith, F. de Goes and T. Kim, Stable neo-hookean flesh simulation, ACM Trans. Graph., 37 (2018), Article No.: 12, 1–15. doi: 10.1145/3180491. |
[44] | O. Sorkine and M. Alexa, As-rigid-as-possible surface modeling, Eurographics Symposium on Geometry Processing, 4 (2007), 109-116. |
[45] | M. Verschoor and A. C. Jalba, Efficient and accurate collision response for elastically deformable models, ACM Trans. Graph., 38 (2019), Article No.: 17, 1–20. doi: 10.1145/3209887. |
[46] | B. Wang, L. Wu, K. Yin, U. Ascher, L. Liu and H. Huang, Deformation capture and modelling of soft objects, ACM trans. on Graphics (SIGGRAPH), 34 (2015). |
[47] | J. Wojewoda, A. Stefański, M. Wiercigroch and T. Kapitaniak, Hysteretic effects of dry friction: Modelling and experimental studies, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 336 (2008), 747-765. doi: 10.1098/rsta.2007.2125. |
[48] | H. Xu and J. Barbic, Example-based damping design, ACM Trans. Graphics, 36 (2017), Article No.: 53, 1–14. doi: 10.1145/3072959.3073631. |
Deformable articulated objects: a swaying tree and a constrained jelly brick; cf. [13]
Moving tetrahedral FEM mesh for position coordinates
Damping curves for the SDIRK method (solid line), TR-BDF2 (dashed) and BDF2 (dash-dot). The two DIRK methods behave similarly, and they differ significantly from BDF2
Computational costs for a swinging armadillo simulation [13]. The cost of exponential integrators including ERE becomes prohibitive as the stiffness parameter increases. By contrast, the cost of SIERE does not grow significantly with stiffness
Plot of of the first 1000 eigenvalues of a soft body problem
Potential energy plots for different integrators applied to a soft object: BE (thick solid line), SIERE with
With large enough time steps, velocity based contact constraints may reject plausible steps. If a vertex in blue is constrained to have a strictly positive velocity with respect to the convex gray contact surface, then plausibly valid next-step configurations (right) may be erroneously rejected
Barrier function
Plot of the smoothing function