Invertible finite elements for robust simulation of large deformation

ABSTRACT

We present an algorithm for the finite element simulation of elastoplastic solids which is capable of robustly and efficiently handling arbitrarily large deformation. In fact, our model remains valid even when large parts of the mesh are inverted. The algorithm is straightforward to implement and can be used with any material constitutive model, and for both volumetric solids and thin shells such as cloth. We also provide a mechanism for controlling plastic deformation, which allows a deformable object to be guided towards a desired final shape without sacrificing realistic behavior. Finally, we present an improved method for rigid body collision handling in the context of mixed explicit/implicit time-stepping.

REFERENCES

• 1: {AL03} Armero F., Love E.: An arbitrary lagrangian-eulerian finite element method for finite strain plasticity. Int. J. Num. Meth. Eng. 57 (2003), 471--508. 6
• 2: {BBTL03} Bessette G., Becker E., Taylor L., Littlefield D.: Modeling of impact problems using an h-adaptive, explicit lagrangian finite element method in three dimensions. Comput. Meth. in Appl. Mech. and Eng. 192 (2003), 1649--1679. 1
• 3: {BC00} Bourguignon D., Cani M. P.: Controlling anisotropy in mass-spring systems. In Eurographics (2000), Eurographics Assoc., pp. 113--123. 2
• 4: Robert Bridson , Ronald Fedkiw , John Anderson, Robust treatment of collisions, contact and friction for cloth animation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 5: R. Bridson , S. Marino , R. Fedkiw, Simulation of clothing with folds and wrinkles, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 6: {BW97} Bonet J., Wood R.: Nonlinear continuum mechanics for finite element analysis. Cambridge University Press, Cambridge, 1997. 3, 5, 6
• 7: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 8: David Baraff , Andrew Witkin , Michael Kass, Untangling cloth, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 9: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 10: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, A multiresolution framework for dynamic deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545268]
• 11: Kwang-Jin Choi , Hyeong-Seok Ko, Stable but responsive cloth, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 12: {CM97} Cooper L., Maddock S.: Preventing collapse within mass-spring-damper models of deformable objects. In The 5th Int. Conf. in Central Europe on Comput. Graphics and Vis. (1997). 2
• 13: {CO97} Camacho G., Ortiz M.: Adaptive Lagrangian modelling of ballistic penetration of metallic targets. Comput. Meth. in Appl. Mech. and Eng. 142 (1997), 269--301. 1
• 14: David T. Chen , David Zeltzer, Pump it up: computer animation of a biomechanically based model of muscle using the finite element method, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.89-98, July 1992
• 15: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 16: Olaf Etzmuβ , Michael Keckeisen , Wolfgang Straβer, A Fast Finite Element Solution for Cloth Modelling, Proceedings of the 11th Pacific Conference on Computer Graphics and Applications, p.244, October 08-10, 2003
• 17: {ERM*03} Escobar J., Rodríguez E., Montenegro R., Montero G., González-Yuste J.: Simultanous untangling and smoothing of tetrahedral meshes. Comput. Meth. in Appl. Mech. and Eng. 192 (2003), 2775--2787. 1
• 18: {EZE98} Espinosa H., Zavattieri P., Emore G.: Adaptive FEM computation of geometric and material nonlinearities with application to brittle failure. Mech. Materials 29 (1998), 275--305. 1
• 19: Nick Foster , Dimitris Metaxas, Controlling Fluid Animation, Proceedings of the 1997 Conference on Computer Graphics International, p.178, June 23-27, 1997
• 20: Eitan Grinspun , Anil N. Hirani , Mathieu Desbrun , Peter Schröder, Discrete shells, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 21: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 22: J.-P. Gourret , N. M. Thalmann , D. Thalmann, Simulation of object and human skin formations in a grasping task, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.21-30, July 1989
• 23: {HAC74} Hirt C., Amsden A., Cook J.: An arbitrary Lagrangian-Eulerian computing method for all flow speeds. J. Comput. Phys. 135 (1974), 227--253. 1
• 24: {HFS*01} Hirota G., Fisher S., State A., Lee C., Fuchs H.: An implicit finite element method for elastic solids in contact. In Comput. Anim. (2001). 2
• 25: Doug L. James , Kayvon Fatahalian, Precomputing interactive dynamic deformable scenes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 26: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 27: Neil Molino , Zhaosheng Bao , Ron Fedkiw, A virtual node algorithm for changing mesh topology during simulation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 28: {MBTF03} Molino N., Bridson R., Teran J., Fedkiw R.: A crystalline, red green strategy for meshing highly deformable objects with tetrahedra. In 12th Int. Meshing Roundtable (2003), pp. 103--114. 2, 7, 8
• 29: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 30: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of the 2004 conference on Graphics interface, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 31: Matthias Müller , Leonard McMillan , Julie Dorsey , Robert Jagnow, Real-time simulation of deformation and fracture of stiff materials, Proceedings of the Eurographic workshop on Computer animation and simulation, p.113-124, September 02-03, 2001, Manchester, UK
• 32: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 33: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 34: {Pal94} Palmerio B.: An attraction-repulsion mesh adaption model for flow solution on unstructured grids. Comput. and Fluids 23, 3 (1994), 487--506. 2
• 35: {PDA01} Picinbono G., Delingette H., Ayache N.: Non-linear and anisotropic elastic soft tissue models for medical simulation. In IEEE Int. Conf. Robot. and Automation (2001). 2, 5
• 36: Jovan Popović , Steven M. Seitz , Michael Erdmann , Zoran Popović , Andrew Witkin, Interactive manipulation of rigid body simulations, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.209-217, July 2000 [doi>10.1145/344779.344880]
• 37: {TBC03} Taylor G., Bailey C., Cross M.: A vertex-based finite volume method applied to non-linear material problems in computational solid mechanics. Int. J. Num. Meth. Eng. 56 (2003), 507--529. 3
• 38: {TF88a} Terzopoulos D., Fleischer K.: Deformable models. The Visual Computer, 4 (1988), 306--331. 2
• 39: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.269-278, Aug. 1988
• 40: Matthias Teschner , Bruno Heidelberger , Matthias Muller , Markus Gross, A Versatile and Robust Model for Geometrically Complex Deformable Solids, Proceedings of the Computer Graphics International (CGI'04), p.312-319, June 16-19, 2004 [doi>10.1109/CGI.2004.6]
• 41: Adrien Treuille , Antoine McNamara , Zoran Popović , Jos Stam, Keyframe control of smoke simulations, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 42: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 43: J. Teran , S. Blemker , V. Ng Thow Hing , R. Fedkiw, Finite volume methods for the simulation of skeletal muscle, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 44: {TSBNTH*04} Teran J., Salinas-Blemker S., Ng Thow-Hing V., Lau C., Fedkiw R.: Robust simulation of muscle and connective tissues in the upper limb (in review). IEEE Trans. on Vis. and Comput. Graph. (2004). 6
• 45: Pavel Vachal , Rao V. Garimella , Mikhail J. Shashkov, Untangling of 2D meshes in ALE simulations, Journal of Computational Physics, v.196 n.2, p.627-644, 20 May 2004 [doi>10.1016/j.jcp.2003.11.011]
• 46: Gary D. Yngve , James F. O'Brien , Jessica K. Hodgins, Animating explosions, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.29-36, July 2000 [doi>10.1145/344779.344801]
• 47: {ZCK98} Zhu Q., Chen Y., Kaufman A.: Real-time biomechanically-based muscle volume deformation using FEM. Comput. Graph. Forum 190, 3 (1998), 275--284. 2

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation