Robust quasistatic finite elements and flesh simulation

ABSTRACT

Quasistatic and implicit time integration schemes are typically employed to alleviate the stringent time step restrictions imposed by their explicit counterparts. However, both quasistatic and implicit methods are subject to hidden time step restrictions associated with both the prevention of element inversion and the effects of discontinuous contact forces. Furthermore, although fast iterative solvers typically require a symmetric positive definite global stiffness matrix, a number of factors can lead to indefiniteness such as large jumps in boundary conditions, heavy compression, etc. We present a novel quasistatic algorithm that alleviates geometric and material indefiniteness allowing one to use fast conjugate gradient solvers during Newton-Raphson iteration. Additionally, we robustly compute smooth elastic forces in the presence of highly deformed, inverted elements alleviating artificial time step restrictions typically required to prevent such states. Finally, we propose a novel strategy for treating both collision and self-collision in this context.

REFERENCES

• 1: Brett Allen , Brian Curless , Zoran Popović, Articulated body deformation from range scan data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 2: Irene Albrecht , Jörg Haber , Hans-Peter Seidel, Construction and animation of anatomically based human hand models, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 3: {AS96} Ambrosio L., Soner H. M.: Level set approach to mean curvature flow in arbitrary codimension. J. of Differential Geometry 43 (1996), 693--737.
• 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: 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]
• 7: David Baraff , Andrew Witkin , Michael Kass, Untangling cloth, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 8: 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
• 9: 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]
• 10: Kwang-Jin Choi , Hyeong-Seok Ko, Stable but responsive cloth, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 11: Min Gyu Choi , Hyeong-Seok Ko, Modal Warping: Real-Time Simulation of Large Rotational Deformation and Manipulation, IEEE Transactions on Visualization and Computer Graphics, v.11 n.1, p.91-101, January 2005 [doi>10.1109/TVCG.2005.13]
• 12: 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
• 13: F. Dong , G. J. Clapworthy , M. A. Krokos , J. Yao, An Anatomy-Based Approach to Human Muscle Modeling and Deformation, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.154-170, April 2002 [doi>10.1109/2945.998668]
• 14: 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]
• 15: Susan Fisher , Ming C. Lin, Deformed distance fields for simulation of non-penetrating flexible bodies, Proceedings of the Eurographic workshop on Computer animation and simulation, p.99-111, September 02-03, 2001, Manchester, UK
• 16: Eran Guendelman , Robert Bridson , Ronald Fedkiw, Nonconvex rigid bodies with stacking, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 17: 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
• 18: 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
• 19: 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
• 20: {GMW81} Gill P. E., Murray W., Wright M. H.: Practical Optimization. Academic Press, San Diego, USA, 1981.
• 21: {GW03} Guilkey J., Weiss J.: Implicit time integration for the material point method: Quantitative and algorithmics comparison with the finite element method. Int. J. Numer, Meth. Engng 57 (2003), 1323--1338.
• 22: {HFS*01} Hirota G., Fisher S., State A., Lee C., Fuchs H.: An implicit finite element method for elastic solids in contact. In Proc. of Computer Animation (2001), pp. 136--146.
• 23: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 24: Doug L. James , Kayvon Fatahalian, Precomputing interactive dynamic deformable scenes, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 25: 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
• 26: Paul G. Kry , Doug L. James , Dinesh K. Pai, EigenSkin: real time large deformation character skinning in hardware, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545286]
• 27: Tsuneya Kurihara , Natsuki Miyata, Modeling deformable human hands from medical images, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028571]
• 28: {KMGB04} Kautzman R., Maiolo A., Griffin D., Bueker A.: Jiggly bits and motion retargetting: Bringing the motion of Hyde to life in Van Helsing with dynamics. In SIGGRAPH 2004 Sketches & Applications (2004), ACM Press.
• 29: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 30: D. Marchal , F. Aubert , C. Chaillou, Collision between deformable objects using fast-marching on tetrahedral models, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028540]
• 31: 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
• 32: {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.
• 33: 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]
• 34: Alex Mohr , Michael Gleicher, Building efficient, accurate character skins from examples, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 35: 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
• 36: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 37: 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
• 38: {NTHF02} Ng-Thow-Hing V., Fiume E.: Application-specific muscle representations. In Proc. of Gr. Inter, 2002 (2002), Sturzlinger W., McCool M., (Eds.), Canadian Information Processing Society, pp. 107--115.
• 39: 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
• 40: {OF02} Osher S., Fedkiw R.: Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, 2002. New York, NY.
• 41: 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]
• 42: {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).
• 43: Eftychios Sifakis , Igor Neverov , Ronald Fedkiw, Automatic determination of facial muscle activations from sparse motion capture marker data, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 44: Ferdi Scheepers , Richard E. Parent , Wayne E. Carlson , Stephen F. May, Anatomy-based modeling of the human musculature, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.163-172, August 1997 [doi>10.1145/258734.258827]
• 45: Peter-Pike J. Sloan , Charles F. Rose, III , Michael F. Cohen, Shape by example, Proceedings of the 2001 symposium on Interactive 3D graphics, p.135-143, March 2001 [doi>10.1145/364338.364382]
• 46: {ST04} Stinson W., Thuriot P.: Bulging muscle and sliding skin: Deformation systems for Hellboy. In SIGGRAPH 2004 Sketches & Applications (2004), ACM Press.
• 47: 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
• 48: {TF88a} Terzopoulos D., Fleischer K.: Deformable models. The Visual Computer, 4 (1988), 306--331.
• 49: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.269-278, Aug. 1988
• 50: 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]
• 51: 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
• 52: Joseph Teran , Eftychios Sifakis , Silvia S. Blemker , Victor Ng-Thow-Hing , Cynthia Lau , Ronald Fedkiw, Creating and Simulating Skeletal Muscle from the Visible Human Data Set, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.317-328, May 2005 [doi>10.1109/TVCG.2005.42]
• 53: D. Terzopoulos , A. Witkin, Physically-based models with rigid and deformable components, Proceedings on Graphics interface '88, p.146-154, December 1989, Edmonton, Alberta, Canada
• 54: {TWS80} Taylor R., Wilson E., Sacket S.: Direct solution of equations by frontal and variable band active column methods. In Europe-U.S. Workshop: Nonlinear Finite Element Analysis in Structural Mechanics (1980), Springer-Verlag.
• 55: Pascal Volino , Nadia Magnenat Thalmann, Implementing Fast Cloth Simulation with Collision Response, Proceedings of the International Conference on Computer Graphics, p.257, June 19-24, 2000
• 56: Xiaohuan Corina Wang , Cary Phillips, Multi-weight enveloping: least-squares approximation techniques for skin animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545283]
• 57: Jane Wilhelms , Allen Van Gelder, Anatomically based modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.173-180, August 1997 [doi>10.1145/258734.258833]
• 58: {ZCK98} Zhu Q., Chen Y., Kaufman A.: Real-time biomechanically-based muscle volume deformation using FEM. Comput. Graph. Forum 190, 3 (1998), 275--284.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

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