A survey on fast simulation of elastic objects
Jin HUANG, Jiong CHEN, Weiwei XU, Hujun BAO
A survey on fast simulation of elastic objects
Elastic simulation plays an important role in computer graphics and has been widely applied to film and game industries. It also has a tight relationship to virtual reality and computational fabrication applications. The balance between accuracy and performance are the most important challenge in the design of an elastic simulation algorithm. This survey will begin with the basic knowledge of elastic simulation, and then investigate two major acceleration techniques for it. From the viewpoint of deformation energy, we introduce typical linearization and reduction ideas for accelerating. We also introduce some recent progress in projective and position-based dynamics, which mainly rely on special numerical methods. Besides, optimal control for elastic objects and typical collision resolving techniques are discussed. Finally, we discuss several possible future works on integrating elastic simulation into virtual reality and 3D printing applications.
computer graphics / elastic simulation / reduction / linearization
[1] |
Brenner S, Scott R. TheMathematical Theory of Finite Element Methods. Springer Science & Business Media, 2007
|
[2] |
Hauth M, Etzmuss O, Strasser W. Analysis of numerical methods for the simulation of deformable models. The Visual Computer, 2003, 19(7): 581–600
CrossRef
Google scholar
|
[3] |
Baraff D, Witkin A. Large steps in cloth simulation. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniqtdes. 1998, 43–54
CrossRef
Google scholar
|
[4] |
Sifakis E, Barbic J. FEM simulation of 3D deformable solids: a practitioner’s guide to theory, discretization and model reduction. In: Proceedings of ACM SIGGRAPH 2012 Courses. 2012, 20
CrossRef
Google scholar
|
[5] |
Müller M, Gross M. Interactive virtual materials. In: Proceedings of the Conference on Graphics Interface. 2004, 239–246
|
[6] |
Terzopoulos D, Witkin A. Physically based models with rigid and deformable components. IEEE Computer Graphics and Applications, 1988, 8(6): 41–51
CrossRef
Google scholar
|
[7] |
Metaxas D, Terzopoulos D. Dynamic deformation of solid primitives with constraints. ACM SIGGRAPH Computer Graphics, 1992, 26(2): 309–312
CrossRef
Google scholar
|
[8] |
Hauser K K, Shen C, O’Brien J F. Interactive deformation using modal analysis with constraints. In: Proceedings of the Conference on Graphics Interface. 2003, 16–17
|
[9] |
Kaufman D M, Sueda S, James D L, Pai D K. Staggered projections for frictional contact in multibody systems. ACM Transactions on Graphics, 2008, 27(5): 164
CrossRef
Google scholar
|
[10] |
Kim T, James D L. Physics-based character skinning using multidomain subspace deformations. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(8): 1228–1240
CrossRef
Google scholar
|
[11] |
Capell S, Green S, Curless B, Duchamp T, Popović Z. Interactive skeleton-driven dynamic deformations. ACM Transactions on Graphics, 2002, 21(3): 586–593
CrossRef
Google scholar
|
[12] |
Huang J, Liu X, Bao H, Guo B, Shum H Y. An efficient large deformation method using domain decomposition. Computers & Graphics, 2006, 30(6): 927–935
CrossRef
Google scholar
|
[13] |
Barbič J, Zhao Y. Real-time large-deformation substructuring. ACM Transactions on Graphics, 2011, 30(4): 91
|
[14] |
Müller M, Dorsey J, McMillan L, Jagnow R, Cutler B. Stable real-time deformations. In: Proceedings of the 2002 ACM SIGGRAPH/ Eurographics Symposium on Computer Animation. 2002, 49–54
CrossRef
Google scholar
|
[15] |
Etzmuß O, Keckeisen M, Straßer W. A fast finite element solution for cloth modelling. In: Proceedings of the 11th Pacific Conference on Computer Graphics and Applications. 2003, 244–251
CrossRef
Google scholar
|
[16] |
Chao I, Pinkall U, Sanan P, Schröder P. A simple geometric model for elastic deformations. ACM Transactions on Graphics, 2010, 29(4): 38
CrossRef
Google scholar
|
[17] |
McAdams A, Zhu Y, Selle A, Empey M, Tamstorf R, Teran J, Sifakis E. Efficient elasticity for character skinning with contact and collisions. ACM Transactions on Graphics, 2011, 30(4): 37
CrossRef
Google scholar
|
[18] |
Martin S, Kaufmann P, Botsch M, Wicke M, Gross M. Polyhedral finite elements using harmonic basis functions. Computer Graphics Forum, 2008, 27(5): 1521–1529
CrossRef
Google scholar
|
[19] |
Fu Z F, He J. Modal Analysis. Oxford: Butterworth-Heinemann, 2001
|
[20] |
Barbič J, James D. Time-critical distributed contact for 6-DoF haptic rendering of adaptively sampled reduced deformable models. In: Proceedings of the 2007 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2007, 171–180
|
[21] |
Pentland A, Williams J. Good vibrations: modal dynamics for graphics and animation. ACMSIGGRAPH Computer Graphics, 1989, 23(3): 207–214
CrossRef
Google scholar
|
[22] |
Silva M, Maia N M. Modal Analysis and Testing. Springer-Verlag, 1989
|
[23] |
Barbič J, James D L. Real-time subspace integration for St. Venant- Kirchhoff deformable models. ACM Transactions on Graphics, 2005, 24(3): 982–990
CrossRef
Google scholar
|
[24] |
Von Tycowicz C, Schulz C, Seidel H P, Hildebrandt K. An efficient construction of reduced deformable objects. ACM Transactions on Graphics, 2013, 32(6): 213
CrossRef
Google scholar
|
[25] |
Yang Y, Li D, Xu W, Tian Y, Zheng C. Expediting precomputation for reduced deformable simulation. ACM Transactions on Graphics, 2015, 34(6): 243
CrossRef
Google scholar
|
[26] |
Langlois T R, An S S, Jin K K, James D L. Eigenmode compression for modal sound models. ACM Transactions on Graphics, 2014, 33(4): 40
CrossRef
Google scholar
|
[27] |
Zheng C, James D L. Toward high-quality modal contact sound. ACM Transactions on Graphics, 2011, 30(4): 38
CrossRef
Google scholar
|
[28] |
Kry P G, James D L, Pai D K. Eigenskin: real time large deformation character skinning in hardware. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2002, 153–159
CrossRef
Google scholar
|
[29] |
Kim T, James D L. Skipping steps in deformable simulation with online model reduction. ACM Transactions on Graphics, 2009, 28(5): 123
CrossRef
Google scholar
|
[30] |
Martin S, Thomaszewski B, Grinspun E, Gross M. Example-based elastic materials. ACM Transactions on Graphics, 2011, 30(4):72
CrossRef
Google scholar
|
[31] |
Zhang W, Zheng J, Thalmann N M. Real-time subspace integration for example-based elastic material. Computer Graphics Forum, 2015, 34(2): 395–404
CrossRef
Google scholar
|
[32] |
Xu H, Li Y, Chen Y, Barbič J. Interactive material design using model reduction. ACM Transactions on Graphics, 2015, 34(2): 18
CrossRef
Google scholar
|
[33] |
Chen X, Zheng C, Zhou K. Example-based subspace stress analysis for interactive shape design. IEEE Transactions on Visualization and Computer Graphics, 2017, 23(10): 2314–2327
CrossRef
Google scholar
|
[34] |
Hahn F, Martin S, Thomaszewski B, Sumner R, Coros S, Gross M. Rig-space physics. ACM Transactions on Graphics, 2012, 31(4): 72
CrossRef
Google scholar
|
[35] |
Hahn F, Thomaszewski B, Coros S, Sumner R W, Gross M. Efficient simulation of secondary motion in rig-space. In: Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2013, 165–171
CrossRef
Google scholar
|
[36] |
Bailey S W, Otte D, Dilorenzo P, O’Brien J F. Fast and deep deformation approximations. ACM Transactions on Graphics, 2018, 37(4): 119
CrossRef
Google scholar
|
[37] |
Gilles B, Bousquet G, Faure F, Pai D K. Frame-based elastic models. ACM Transactions on Graphics, 2011, 30(2): 15
CrossRef
Google scholar
|
[38] |
Joshi P, Meyer M, DeRose T, Green B, Sanocki T. Harmonic coordinates for character articulation. ACM Transactions on Graphics, 2007, 26(3): 71
CrossRef
Google scholar
|
[39] |
Teng Y, Meyer M, DeRose T, Kim T. Subspace condensation: full space adaptivity for subspace deformations. ACM Transactions on Graphics, 2015, 34(4): 76
CrossRef
Google scholar
|
[40] |
Yang Y, Xu W, Guo X, Zhou K, Guo B. Boundary-aware multidomain subspace deformation. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(10): 1633–1645
CrossRef
Google scholar
|
[41] |
Lu W, Jin N, Fedkiw R. Two-way coupling of fluids to reduced deformable bodies. In: Proceedings of the ACM SIGGRAPH/ Eurographics Symposium on Computer Animation. 2016, 67–76
|
[42] |
Yang C, Li S, Lan Y, Wang L, Hao A, Qin H. Coupling time-varying modal analysis and FEM for real-time cutting simulation of objects with multi-material sub-domains. Computer Aided Geometric Design, 2016, 43: 53–67
CrossRef
Google scholar
|
[43] |
Harmon D, Zorin D. Subspace integration with local deformations. ACM Transactions on Graphics, 2013, 32(4): 107
CrossRef
Google scholar
|
[44] |
Wang Y, Jacobson A, Barbič J, Kavan L. Linear subspace design for real-time shape deformation. ACM Transactions on Graphics, 2015, 34(4): 57
CrossRef
Google scholar
|
[45] |
Yang C, Li S, Lan Y, Wang L, Hao A, Qin H. Coupling time-varying modal analysis and fem for real-time cutting simulation of objects with multi-material sub-domains. Computer Aided Geometric Design, 2016, 43: 53–67
CrossRef
Google scholar
|
[46] |
An S S, Kim T, James D L. Optimizing cubature for efficient integration of subspace deformations. ACM Transactions on Graphics, 2008, 27(5): 165
CrossRef
Google scholar
|
[47] |
Choi M G, Ko H S. Modal warping: real-time simulation of large rotational deformation and manipulation. IEEE Transactions on Visualization and Computer Graphics, 2005, 11(1): 91–101
CrossRef
Google scholar
|
[48] |
Huang J, Tong Y, Zhou K, Bao H, Desbrun M. Interactive shape interpolation through controllable dynamic deformation. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(7): 983–992
CrossRef
Google scholar
|
[49] |
Li S, Huang J, Goes de F, Jin X, Bao H, Desbrun M. Space-time editing of elastic motion through material optimization and reduction. ACMTransactions on Graphics, 2014, 33(4): 108
CrossRef
Google scholar
|
[50] |
Pan Z, Bao H, Huang J. Subspace dynamic simulation using rotationstrain coordinates. ACM Transactions on Graphics, 2015, 34(6): 242
CrossRef
Google scholar
|
[51] |
Müller M, Heidelberger B, Teschner M, Gross M. Meshless deformations based on shape matching. ACM Transactions on Graphics, 2005, 24(3): 471–478
CrossRef
Google scholar
|
[52] |
Müller M, Bruno H, Marcus H, John R. Position based dynamics. Journal of Visual Communication and Image Representation, 2007, 18(2): 109–118
CrossRef
Google scholar
|
[53] |
Rivers A R, James D L. Fastlsm: fast lattice shape matching for robust real-time deformation. ACM Transactions on Graphics, 2007, 26(3): 82
CrossRef
Google scholar
|
[54] |
Müller M, Chentanez N. Solid simulation with oriented particles. ACM Transactions on Graphics, 2011, 30(4): 92
CrossRef
Google scholar
|
[55] |
Bender J, Müller M, Otaduy M A, Teschner M. Position-based methods for the simulation of solid objects in computer graphics. In: Proceedings of Eurographics 2013-State of the Art Reports. 2013, 1–22
|
[56] |
Fratarcangeli M, Tibaldo V, Pellacini F. Vivace: a practical gauss-seidel method for stable soft body dynamics. ACM Transactions on Graphics, 2016, 35(6): 214
CrossRef
Google scholar
|
[57] |
Deul C, Kugelstadt T, Weiler M, Bender J. Direct position-based solver for stiff rods. In: Proceedings of Computer Graphics Forum. 2018
CrossRef
Google scholar
|
[58] |
Huang J, Shi X, Liu X, Zhou K, Guo B, Bao H. Geometrically based potential energy for simulating deformable objects. The Visual Computer, 2006, 22(9): 740–748
CrossRef
Google scholar
|
[59] |
Huang J, Zhang H, Shi X, Liu X, Bao H. Interactive mesh deformation with pseudo material effects. Computer Animation and Virtual Worlds, 2006, 17(3-4): 383–392
CrossRef
Google scholar
|
[60] |
Liu T, Bargteil A W, OBrien J F, Kavan L. Fast simulation of massspring systems. ACM Transactions on Graphics, 2013, 32(6): 214
CrossRef
Google scholar
|
[61] |
Bouaziz S, Martin S, Liu T, Kavan L, Pauly M. Projective dynamics: fusing constraint projections for fast simulation. ACM Transactions on Graphics, 2014, 33(4): 154
CrossRef
Google scholar
|
[62] |
Brant C, Eisemann E, Hilbebrant K. Hyper-reduced projective dynamics. ACM Transactions on Graphics, 2018, 37(4): 154
CrossRef
Google scholar
|
[63] |
Narain R, Overby M, Brown G E. Admm ⊇ projective dynamics: fast simulation of general constitutive models. In: Proceedings of the ACMSIGGRAPH/Eurographics Symposium on Computer Animation. 2016, 21–28
|
[64] |
Wang H. A chebyshev semi-iterative approach for accelerating projective and position-based dynamics. ACM Transactions on Graphics, 2015, 34(6): 246
CrossRef
Google scholar
|
[65] |
Liu T, Bouaziz S, Kavan L. Quasi-newton methods for real-time simulation of hyperelastic materials. ACM Transactions on Graphics, 2017, 36(3): 23
CrossRef
Google scholar
|
[66] |
Wang H, Yang Y. Descent methods for elastic body simulation on the GPU. ACM Transactions on Graphics, 2016, 35(6): 212
CrossRef
Google scholar
|
[67] |
Peng Y, Deng B, Zhang J, Geng F, Qin W, Liu L. Anderson acceleration for geometry optimization and physics simulation. 2018, arXiv preprint arXiv: 1805.05715
|
[68] |
Witkin A, Kass M. Spacetime constraints. ACM Siggraph Computer Graphics, 1988, 22(4): 159–168
CrossRef
Google scholar
|
[69] |
Barbič J, Silva da M, Popovíc J. Deformable object animation using reduced optimal control. ACM Transactions on Graphics, 2009, 28(3): 53
|
[70] |
Hildebrandt K, Schulz C, Tycowicz von C, Polthier K. Interactive spacetime control of deformable objects. ACM Transactions on Graphics, 2012, 31(4): 71
CrossRef
Google scholar
|
[71] |
Kass M, Anderson J. Animating oscillatory motion with overlap: wiggly splines. ACM Transactions on Graphics, 2008, 27(3): 28
CrossRef
Google scholar
|
[72] |
Barbič J, Sin F, Grinspun E. Interactive editing of deformable simulations. ACM Transactions on Graphics, 2012, 31(4): 70
|
[73] |
Li S, Huang J, Desbrun M, Jin X. Interactive elastic motion editing through space–time position constraints. Computer Animation and Virtual Worlds, 2013, 24(3-4): 409–417
CrossRef
Google scholar
|
[74] |
Barbič J, Popovíc J. Real-time control of physically based simulations using gentle forces. ACM Transactions on Graphics, 2008, 27(5): 163
|
[75] |
Schulz C, Tycowicz von C, Seidel H P, Hildebrandt K. Animating deformable objects using sparse spacetime constraints. ACM Transactions on Graphics, 2014, 33(4): 109
CrossRef
Google scholar
|
[76] |
Teschner M, Kimmerle S, Heidelberger B, Zachmann G, Raghupathi L, Fuhrmann A, Cani M P, Faure F, Magnenat-Thalmann N, Strasser W, Volino P. Collision detection for deformable objects. Computer Graphics Forum, 2005, 24(1): 61–81
CrossRef
Google scholar
|
[77] |
Redon S, Kheddar A, Coquillart S. Fast continuous collision detection between rigid bodies. Computer Graphics Forum, 2002, 21(3): 279–287
CrossRef
Google scholar
|
[78] |
Zhang X, Redon S, Lee M, Kim Y J. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Transactions on Graphics, 2007, 26(3): 15
CrossRef
Google scholar
|
[79] |
Provot X. Collision and Self-collision Handling in Cloth Model Dedicated to Design Garments. Computer Animation and Simulation, Springer, Vienna, 1997, 177–189
|
[80] |
Bridson R, Fedkiw R, Anderson J. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics (ToG), 2002, 21(3): 594–603
CrossRef
Google scholar
|
[81] |
Harmon D, Vouga E, Tamstorf R, Grinspun E. Robust treatment of simultaneous collisions. ACM Transactions on Graphics, 2008, 27(3): 23
CrossRef
Google scholar
|
[82] |
Brochu T, Edwards E, Bridson R. Efficient geometrically exact continuous collision detection. ACM Transactions on Graphics, 2012, 31(4): 96
CrossRef
Google scholar
|
[83] |
Tang M, Manocha D, Yoon S E, Du P, Heo J P, Tong R F. Volccd: fast continuous collision culling between deforming volume meshes. ACM Transactions on Graphics, 2011, 30(5): 111
CrossRef
Google scholar
|
[84] |
Tang M, Tong R, Wang Z, Manocha D. Fast and exact continuous collision detection with bernstein sign classification. ACM Transactions on Graphics, 2014, 33(6): 186
CrossRef
Google scholar
|
[85] |
Wang H. Defending continuous collision detection against errors. ACM Transactions on Graphics, 2014, 33(4): 122
CrossRef
Google scholar
|
[86] |
Wang Z, Tang M, Tong R, Manocha D. Tightccd: efficient and robust continuous collision detection using tight error bounds. Computer Graphics Forum, 2015, 34(7): 289–298
CrossRef
Google scholar
|
[87] |
Choi K J, Ko H S. Stable but responsive cloth. In: Proceedings of ACM SIGGRAPH 2005 Courses. 2005
CrossRef
Google scholar
|
[88] |
Fisher S, Lin M C. Deformed Distance Fields for Simulation of Non-penetrating Flexible Bodies. Computer Animation and Simulation 2001, Springer, Vienna, 2001, 99–111
|
[89] |
Keiser M, Heidelberger B, Gross M. Consistent Penetration Depth Estimation for Deformable Collision Response. Vision, Modeling, and Visualization, IOS Press, 2004, 339–346
|
[90] |
Harmon D, Vouga E, Smith B, Tamstorf R, Grinspun E. Asynchronous contact mechanics. ACM Transactions on Graphics, 2009, 28(3): 87
CrossRef
Google scholar
|
[91] |
Tang M, Manocha D, Otaduy M A, Tong R. Continuous penalty forces. ACM Transactions on Graphics, 2012, 31(4): 107
CrossRef
Google scholar
|
[92] |
Otaduy M A, Tamstorf R, Steinemann D, Gross M. Implicit contact handling for deformable objects. Computer Graphics Forum, 2009, 28(2): 559–568
CrossRef
Google scholar
|
[93] |
Li S, Pan Z, Huang J, Bao H, Jin X. Deformable objects collision handling with fast convergence. Computer Graphics Forum, 2015, 34(7): 269–278
CrossRef
Google scholar
|
[94] |
Barbič J, James D L. Subspace self-collision culling. ACM Transactions on Graphics, 2010, 29(4): 81
|
[95] |
Schvartzman S C, Gascón J, Otaduy M A. Bounded normal trees for reduced deformations of triangulated surfaces. In: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 2009, 75–82
CrossRef
Google scholar
|
[96] |
Teng Y, Otaduy M A, Kim T. Simulating articulated subspace selfcontact. ACM Transactions on Graphics, 2014, 33(4): 106
CrossRef
Google scholar
|
[97] |
Harmon D, Zorin D. Subspace integration with local deformations. ACM Transactions on Graphics, 2013, 32(4): 107
CrossRef
Google scholar
|
[98] |
Barbič J, James D L. Six-DoF haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics, 2008, 1(1): 39–52
CrossRef
Google scholar
|
[99] |
Lipeng Y, Shuai L, Aimin H, Hong Q. Realtime two-way coupling of meshless fluids and nonlinear fem. Computer Graphics Forum, 2012, 31(7): 2037–2046
CrossRef
Google scholar
|
[100] |
Chen X, Zheng C, Xu W, Zhou K. An asymptotic numerical method for inverse elastic shape design. ACM Transactions on Graphics, 2014, 33(4): 95
CrossRef
Google scholar
|
/
〈 | 〉 |