[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Primal residual reduction with extended position based dynamics and hyperelasticity

Published: 18 July 2024 Publication History

Abstract

The Extended Position Based Dynamics (XPBD) approach of Macklin et al. (2016) addresses issues with iteration-dependent behavior in the original Position Based Dynamics (Müller et al., 2007) (PBD). PBD itself is a powerful method for the real-time simulation of elastic objects, however, it is limited in its application to hyperelastic solids. It can only treat models with a strain energy density that is quadratic in some notion of constraint. Furthermore, we show that even when applicable the formulation does not always lead to convergent behaviors with hyperelasticity. We isolate the root cause to be the approximate linearization of the nonlinear backward Euler systems utilized by XPBD. We provide two fixes to these terms that allow for convergent behavior. The first (B-PXPBD) is a small modification to an existing XPBD code, but can only be used with models addressable by the original XPBD. The second (FP-PXPBD) is a more general formulation that extends XPBD (and our residual correction) to arbitrary hyperelasticity. We show that our modifications allow for convergent behavior that rivals accurate techniques like Newton’s method when the computational budget is large without sacrificing the stable and robust behavior exhibited by the original PBD and XPBD when the computational budget is limited.

Graphical abstract

Display Omitted

Highlights

B-PXPBD: A modification to the XPBD position update that improves residual reduction.
FP-PXPBD: A first Piola–Kirchhoff formulation of the XPBD auxiliary variables.
Explicit expressions for the incorporated anisotropic hyperelastic models.
Extensive illustrations for coloring strategies related to parallelism structures.

References

[1]
Bonet J., Wood R., Nonlinear continuum mechanics for finite element analysis, Cambridge University Press, 2008.
[2]
Sifakis E., Barbic J., FEM simulation of 3D deformable solids: a practitioner’s guide to theory, discretization and model reduction, in: ACM SIGGRApH 2012 courses, ACM, 2012, pp. 20:1–20:50.
[3]
Baraff D, Witkin A. Large Steps in Cloth Simulation. In: Proc ACM SIGGRApH. 1998, p. 43–54.
[4]
Teran J, Sifakis E, Irving G, Fedkiw R. Robust quasistatic finite elements and flesh simulation. In: Proc 2005 ACM SIGGRApH/Eurograph symp comp anim. 2005, p. 181–90.
[5]
Zhu Y., Bridson R., Kaufman D., Blended cured quasi-Newton for distortion optimization, ACM Trans Graph 37 (4) (2018) 14. Article 40.
[6]
Rabinovich M., Poranne R., Panozzo D., Sorkine-Hornung O., Scalable locally injective mappings, ACM Trans Graph 36 (2) (2017) 16. Article 16.
[7]
Sorkine O, Alexa M. As-Rigid-As-Possible Surface Modeling. In: Eurographics symposium on geometry processing. 2007.
[8]
McAdams A., Zhu Y., Selle A., Empey M., Tamstorf R., Teran J., Sifakis E., Efficient elasticity for character skinning with contact and collisions, ACM Trans Graph 30 (4) (2011) 37:1–37:12.
[9]
Wang B., Zheng M., Barbič J., Adjustable constrained soft-tissue dynamics, Pac Graph 2020 Comp Graph Forum 39 (7) (2020).
[10]
Smith B., De Goes F., Kim T., Stable neo-hookean flesh simulation, ACM Trans Grap (TOG) 37 (2) (2018) 1–15.
[11]
Fan Y., Litven J., Pai D., Active volumetric musculoskeletal systems, ACM Trans Graph 33 (4) (2014) 152:1–152:9.
[12]
Modi V., Fulton L., Jacobson A., Sueda S., Levin D., Emu: Efficient muscle simulation in deformation space, Comp graph forum, vol. 40, Wiley Online Library, 2021, pp. 234–248.
[13]
Teran J., Sifakis E., Blemker S., Ng-Thow-Hing V., Lau C., Fedkiw R., Creating and simulating skeletal muscle from the visible human data set, IEEE Trans Vis Comp Graph 11 (3) (2005) 317–328.
[14]
Li M., Gao M., Langlois T., Jiang C., Kaufman D., Decomposed optimization time integrator for large-step elastodynamics, ACM Trans Graph 38 (4) (2019) 10,.
[15]
Narain R., Overby M., Brown G., ADMM projective dynamics: Fast simulation of general constitutive models, in: Proc ACM SIGGRApH/eurograph symp comp anim, Eurograph Assoc, ISBN 9783905674613, 2016, p. 21?28.
[16]
Bouaziz S., Martin S., Liu T., Kavan L., Pauly M., Projective dynamics: Fusing constraint projections for fast simulation, ACM Trans Graph 33 (4) (2014) 154:1–154:11.
[17]
Gast T., Schroeder C., Stomakhin A., Jiang C., Teran J., Optimization integrator for large time steps, IEEE Trans Vis Comp Graph 21 (10) (2015) 1103–1115.
[18]
Macklin M., Müller M., Chentanez N., XPBD: Position-based simulation of compliant constrained dynamics, in: Proc 9th int conf motion games, ACM, 2016, pp. 49–54.
[19]
Kharevych L., Yang W., Tong Y., Kanso E., Marsden J.E., Schröder P., Desbrun M., Geometric, variational integrators for computer animation, in: Proc 2006 ACM SIGGRApH/eurograph symp comp anim, Eurographics Association, ISBN 3905673347, 2006, pp. 43–51.
[20]
Zhao D., Li Y., Barbič J., Asynchronous implicit backward Euler integration, 2016.
[21]
Nocedal J., Wright S., Conjugate gradient methods, Num Opt 2006 (2006) 101–134.
[22]
Liu T., Bargteil A., O’Brien J., Kavan L., Fast simulation of mass-spring systems, ACM Trans Graph 32 (6) (2013) 1–7. 209.
[23]
Boyd S., Parikh N., Chu E., Peleato B., Eckstein J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found Trends Mach Learn 3 (1) (2011) 1–122.
[24]
Bertsekas D., Nonlinear programming, J Op Res Soc 48 (3) (1997) 334.
[25]
Liu T., Bouaziz S., Kavan L., Quasi-Newton methods for real-time simulation of hyperelastic materials, ACM Trans Graph 36 (4) (2017) 16. Article 116a.
[26]
Witemeyer B., Weidner N., Davis T., Kim T., Sueda S., QLB: Collision-aware quasi-Newton solver with cholesky and L-BFGS for nonlinear time integration, in: Proc 14th ACM SIGGRApH conf mot int games, ACM, 2021, p. 7. Article 14.
[27]
Neuberger J., Steepest descent and differential equations, J Math Soc Japan 37 (2) (1985) 187–195.
[28]
Wang H., A Chebyshev semi-iterative approach for accelerating projective and position-based dynamics, ACM Trans Graph 34 (6) (2015) 9. Article 246.
[29]
Müller M., Heidelberger B., Hennix M., Ratcliff J., Position based dynamics, J Vis Comm Im Rep 18 (2) (2007) 109–118.
[30]
Provot X., Deformation constraints in a mass-spring model to describe rigid cloth behaviour, in: Graph int, Canadian Information Processing Society, 1995, pp. 147–155.
[31]
Müller M., Heidelberger B., Teschner M., Gross M., Meshless deformations based on shape matching, ACM transactions on graphics (TOG), vol. 24, ACM, 2005, pp. 471–478.
[32]
Batty C., Bertails F., Bridson R., A fast variational framework for accurate solid-fluid coupling, ACM Trans Graph 26 (3) (2007).
[33]
Stomakhin A., Schroeder C., Jiang C., Chai L., Teran J., Selle A., Augmented MPM for phase-change and varied materials, ACM Trans Graph 33 (4) (2014) 138:1–138:11.
[34]
Kwatra N., Su J., Grétarsson J., Fedkiw R., A method for avoiding the acoustic time step restriction in compressible flow, J Comput Phys 228 (11) (2009) 4146–4161.
[35]
Macklin M., Muller M., A constraint-based formulation of stable neo-hookean materials, in: Motion, interaction and games, ACM, ISBN 9781450391313, 2021, pp. 1–7. https://dl.acm.org/doi/10.1145/3487983.3488289.
[36]
Jiang C., Schroeder C., Selle A., Teran J., Stomakhin A., The affine particle-in-cell method, ACM Trans Graph 34 (4) (2015) 51:1–51:10.
[37]
Chen Y., Han Y., Chen J., Ma S., Fedkiw R., Teran J., Primal extended position based dynamics for hyperelasticity, in: MIG ’23: proceedings of the 16th ACM SIGGRApH conference on motion, interaction and games, 2023, pp. 1–10.
[38]
O’Brien J., Hodgins J., Graphical modeling and animation of brittle fracture, in: Proc 26th conf comp graph int tech, ACM Press/Addison-Wesley Publishing Co., 1999, pp. 137–146,.
[39]
O’Brien J, Bargteil A, Hodgins J. Graphical modeling and animation of ductile fracture. In: Proc ACM SIGGRApH 2002. 2002, p. 291–4.
[40]
Barbič J., James D., Real-time subspace integration for St. Venant-Kirchhoff deformable models, ACM Trans Graph 24 (3) (2005) 982–990.
[41]
Irving G, Teran J, Fedkiw R. Invertible Finite Elements for Robust Simulation of Large Deformation. In: Proc ACM SIGGRApH/eurograph symp comp anim. 2004, p. 131–40.
[42]
Müller M., Gross M., Interactive virtual materials, in: Proc graph int, Canadian Human-Computer Communications Society, 2004, pp. 239–246.
[43]
Chao I., Pinkall U., Sanan P., Schröder P., A simple geometric model for elastic deformations, ACM Trans Graph 29 (4) (2010) 6. Article 38.
[44]
Stomakhin A., Howes R., Schroeder C., Teran J., Energetically consistent invertible elasticity, in: Proc symp comp anim, 2012, pp. 25–32.
[45]
Kim T., De Goes F., Iben H., Anisotropic elasticity for inversion-safety and element rehabilitation, ACM Trans Graph 38 (4) (2019) 15.
[46]
Martin S., Thomaszewski B., Grinspun E., Gross M., Example-based elastic materials, in: ACM SIGGRApH 2011, ACM, 2011, p. 8. Article 72.
[47]
Teran J., Blemker S., Hing V., Fedkiw R., Finite volume methods for the simulation of skeletal muscle, in: Proc 2003 ACM SIGGRApH/Eurograph symp comp anim, Eurographics Association, 2003, pp. 68–74.
[48]
Xu H., Sin F., Zhu Y., Barbič J., Nonlinear material design using principal stretches, ACM Trans Graph 34 (4) (2015) 1–11.
[49]
Tournier M., Nesme M., Gilles B., Faure F., Stable constrained dynamics, ACM Trans Graph 2015 (2015) 1–10.
[50]
Wang H., Yang Y., Descent methods for elastic body simulation on the GPU, ACM Trans Graph 35 (6) (2016) 1–10,.
[51]
Stern A., Desbrun M., Discrete geometric mechanics for variational time integrators, in: ACM SIGGRApH 2006 courses, ACM, 2006, p. 75?80.
[52]
Liu L., Zhang L., Xu Y., Gotsman C., Gortler S., A local/global approach to mesh parameterization, in: Proc symp geom proc, Eurograph Assoc, 2008, pp. 1495–1504.
[53]
Kovalsky S., Galun M., Lipman Y., Accelerated quadratic proxy for geometric optimization, ACM Trans Graph 35 (4) (2016) 11. Article 134.
[54]
Smith B., Goes F., Kim T., Analytic eigensystems for isotropic distortion energies, ACM Trans Graph (TOG) 38 (1) (2019) 1–15.
[55]
Hecht F., Lee Y., Shewchuk J., O’Brien J., Updated sparse cholesky factors for corotational elastodynamics, ACM Trans Graph 31 (5) (2012) 13. Article 123.
[56]
Gast T., Fu C., Jiang C., Teran J., Implicit-shifted symmetric QR singular value decomposition of 3 × 3 matrices, University of California Los Angeles, 2016.
[57]
Blemker S., Pinsky P., Delp S., A 3D model of muscle reveals the causes of nonuniform strains in the biceps brachii, J Biomech 38 (4) (2005) 657–665.
[58]
Goldenthal R., Harmon D., Fattal R., Bercovier M., Grinspun E., Efficient simulation of inextensible cloth, ACM Trans Graph 26 (3) (2007) Article 49.
[59]
Kwatra N, Gretarsson J, Fedkiw R. Practical Animation of Compressible Flow for ShockWaves and Related Phenomena. In: Symp comp anim. 2010, p. 207–15.
[60]
Hager W., Updating the inverse of a matrix, SIAM Rev 31 (2) (1989) 221–239.
[61]
Fratarcangeli M., Valentina T., Pellacini F., Vivace: a practical gauss-seidel method for stable soft body dynamics, ACM Trans Graph 35 (6) (2016) 1–9,.
[62]
Chen Y., Han Y., Chen J., Ma S., Fedkiw R., Teran J., Supplementary technical document, 2023.
[63]
Turk G., Levoy M., Stanford bunny, 1994, http://graphics.stanford.edu/data/3Dscanrep/. Stanford University Computer Graphics Laboratory.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers and Graphics
Computers and Graphics  Volume 119, Issue C
Apr 2024
407 pages

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 18 July 2024

Author Tags

  1. Position-based dynamics
  2. Physics simulation
  3. Constrained dynamics

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media