Article

Robust quasistatic finite elements and flesh simulation

Authors:

Eftychios Sifakis,

Geoffrey Irving,

Ronald FedkiwAuthors Info & Claims

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

Pages 181 - 190

https://doi.org/10.1145/1073368.1073394

Published: 29 July 2005 Publication History

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]

{ACP02} Allen B., Curless B., Popovic Z.: Articulated body deformation from range scan data. In Proc. of ACM SIGGRAPH 2002 (2002), pp. 612--619.

Digital Library

[2]

{AHS03} Albrecht I., Haber J., Seidel H. P.: Construction and animation of anatomically based human hand models. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2003), pp. 98--109.

Digital Library

[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]

{BFA02} Bridson R., Fedkiw R., Anderson J.: Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002), 594--603.

Digital Library

[5]

{BMF03} Bridson R., Marino S., Fedkiw R.: Simulation of clothing with folds and wrinkles. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2003), pp. 28--36.

Digital Library

[6]

{BW98} Baraff D., Witkin A.: Large steps in cloth simulation. In Proc. SIGGRAPH 98 (1998), pp. 1---12.

Digital Library

[7]

{BWK03} Baraff D., Witkin A., Kass M.: Untangling cloth. ACM Trans. Graph. (SIGGRAPH Proc.) 22 (2003), 862--870.

Digital Library

[8]

{CGC*02a} Capell S., Green S., Curless B., Duchamp T., Popovićz.: Interactive skeleton-driven dynamic deformations. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002), 586--593.

Digital Library

[9]

{CGC*02b} Capell S., Green S., Curless B., Duchamp T., Popovićz.: A multiresolution framework for dynamic deformations. In ACM SIGGRAPH Symp. on Comput. Anim. (2002), ACM Press, pp. 41--48.

Digital Library

[10]

{CK02} Choi K.-J. Ko H.-S.: Stable but responsive cloth. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002). 604--611.

Digital Library

[11]

{CK05} Choi M. G., Ko H.-S.: Modal warping: Realtime simulation of large rotational deformation and manipulation. IEEE Trans. Viz. Comput. Graph. 11 (2005), 91--101.

Digital Library

[12]

{CZ92} Chen D., Zeltzer D.: Pump it up: Computer animation of a biomechanically based model of muscle using the finite element method. Comput. Graph. (SIGGRAPH Proc.) (1992), 89--98.

Digital Library

[13]

{DCKY02} Dong F., Clapworthy G., Krokos M., Yao J.: An anatomy-based approach to human muscle modeling and deformation. IEEE Trans. Vis. Comput. Graph. 8, 2 (2002).

Digital Library

[14]

{DDCB01} Debunne G., Desbrun M., Cani M., Barr A.: Dynamic real-time deformations using space & time adaptive sampling. In Proc. SIGGRAPH 2001 (2001), vol. 20, pp. 31--36.

Digital Library

[15]

{FL01} Fisher S., Lin M. C.: Deformed distance fields for simulation of non-penetrating flexible bodies. In Comput. Anim. and Sim. '01 (2001), Proc. Eurographics Work-shop, pp. 99--111.

Digital Library

[16]

{GBF03} Guendelman E., Bridson R., Fedkiw R.: Nonconvex rigid bodies with stacking. ACM Trans. Graph. (SIGGRAPH Proc.) 22, 3 (2003). 871--878.

Digital Library

[17]

{GHDS03} Grinspun E., Hirani A., Desbrun M., Schröder P.: Discrete shells. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2003), pp. 62--67.

Digital Library

[18]

{GKS02} Grinspun E., Krysl P., Schröder P.: Charms: A simple framework for adaptive simulation. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002), 281--290.

Digital Library

[19]

{GMTT89} Gourret J.-P., Magnenat-Thalmann N., Thalmann D.: Simulation of object and human skin deformations in a grasping task. Comput. Graph. (SIGGRAPH Proc.) (1989), 21--30.

Digital Library

[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]

{ITF04} Irving G., Teran J., Fedkiw R.: Invertible finite elements for robust simulation of large deformation. In Proc. of the ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2004), pp. 131--140.

Digital Library

[24]

{JF03} James D., Fatahalian K.: Precomputing interactive dynamic deformable scenes. ACM Trans. Graph. (SIGGRAPH Proc.) 22 (2003). 879--887.

Digital Library

[25]

{JP02} James D., Pai D.: DyRT: Dynamic response textures for real time deformation simulation with graphics hardware. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002). 582--585.

Digital Library

[26]

{KJP02} Kry P. G., James D. L., Pai D. K.: Eigenskin: real time large deformation character skinning in hardware. In Proceedings of the ACM SIGGRAPH symposium on Computer animation (2002), ACM Press, pp. 153--159.

Digital Library

[27]

{KM04} Kurihara T., Miyata N.: Modeling deformable human hands from medical images. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2004), pp. 365--373.

Digital Library

[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.

Digital Library

[29]

{LCF00} Lewis J., Cordner M., Fong N.: Pose space deformations: A unified approach to shape interpolation a nd skeleton-driven deformation. Comput. Graph. (SIGGRAPH Proc.) (2000), 165--172.

Digital Library

[30]

{MAC04} Marchal D., Aubert F., Chaillou C.: Collision between deformable objects using fast-marching on tetrahedral models. In Proceedings of the ACM SIGGRAPH symposium on Computer animation (2004), ACM Press.

Digital Library

[31]

{MBF04} Molino N., Bao Z., Fedkiw R.: A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. (SIGGRAPH Proc.) 23 (2004), 385--392.

Digital Library

[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]

{MDM*02} Müller M., Dorsey J., McMillan L., Jagnow R., Cutler B.: Stable real-time deformations. In ACM SIGGRAPH Symp. on Comput. Anim. (2002), pp. 49--54.

Digital Library

[34]

{MG03} Mohr A., Gleicher M.: Building efficient, accurate character skins from examples. ACM Transactions on Graphics 22, 3 (2003), 562--568.

Digital Library

[35]

{MG04} Müller M., Gross M.: Interactive virtual materials. In Graph. Interface (May 2004). pp. 239--246.

Digital Library

[36]

{MKN*04} Müller M., Keiser R., Nealen A., Pauly M., Gross M., Alexa M.: Point based animation of elastic, plastic and melting objects. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2004), pp. 141--151.

Digital Library

[37]

{MMDJ01} Müller M., McMilan L., Dorsey J., Jagnow R.: Real-time simulation of deformation and fracture of stiff materials. In Comput. Anim. and Sim. '01 (2001), Proc. Eurographics Workshop, Eurographics Assoc., pp. 99--111.

Digital Library

[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]

{OBH02} O'Brien J., Bargteil A., Hodgins J.: Graphical modeling of ductile fracture. ACM Trans. Graph. (SIGGRAPH Proc.) 21 (2002), 291--294.

Digital Library

[40]

{OF02} Osher S., Fedkiw R.: Level Set Methods and Dynamic Implicit Surfaces. Springer-Verlag, 2002. New York, NY.

[41]

{OH99} O'Brien J., Hodgins J.: Graphical modeling and animation of brittle fracture. In Proc. SIGGRAPH 99 (1999), vol. 18, pp. 137--146.

Digital Library

[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]

{SNF05} Sifakis E., Neverov I., Fedkiw R.: Automatic determination of facial muscle activations from sparse motion capture marker data. to appear in ACM Trans. Graph. (SIGGRAPH Proc.) (2005).

Digital Library

[44]

{SPCM97} Scheepers F., Parent R., Carlson W., MAY S.: Anatomy-based modeling of the human musculature. Comput. Graph. (SIGGRAPH Proc.) (1997), 163--172.

Digital Library

[45]

{SRC01} Sloan P., Rose C., Cohen M.: Shape by example. In Proc. of 2001 Symp. Int. 3D Graph. (2001), pp. 135--143.

Digital Library

[46]

{ST04} Stinson W., Thuriot P.: Bulging muscle and sliding skin: Deformation systems for Hellboy. In SIGGRAPH 2004 Sketches & Applications (2004), ACM Press.

Digital Library

[47]

{TBNF03} Teran J., Blemker S., Ng V., Fedkiw R.: Finite volume methods for the simulation of skeletal muscle. In Proc. of the 2003 ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2003), pp. 68--74.

Digital Library

[48]

{TF88a} Terzopoulos D., Fleischer K.: Deformable models. The Visual Computer, 4 (1988), 306--331.

[49]

{TF88b} Terzopoulos D., Fleischer K.: Modeling inelastic deformation: viscoelasticity, plasticity, fracture. Comput. Graph. (SIGGRAPH Proc.) (1988). 269--278.

Digital Library

[50]

{THMG04} Teschner M., Heidelberger B., Müller M., Gross M.: A versatile and robust model for geometrically complex deformable solids. In Proc. Computer Graphics International (2004), pp. 312--319.

Digital Library

[51]

{TPBF87} Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models. Comput. Graph. (Proc. SIGGRAPH 87) 21, 4 (1987), 205--214.

Digital Library

[52]

{TSSB*05} Teran J., Sifakis E., Salinas-Blemker S., Ng-Thow-Hing V., Lau C., Fedkiw R.: Creating and simulating skeletal muscle from the visible human data set. IEEE Trans. on Vis. and Comput. Graph. 11, 3 (2005), 317--328.

Digital Library

[53]

{TW88} Terzopoulos D., Witkin A.: Physically based models with rigid and deformable components. In Graphics Interface (1988), pp. 146--154.

Digital Library

[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]

{VT00} Volino P., Thalman N.: Implementing fast cloth simulation with collision response. In Proceedings of the International Conference on Computer Graphics (2000), IEEE Computer Society, p. 257.

Digital Library

[56]

{WP02} Wang X. C., Phillips C.: Multi-weight enveloping: Least-squares approximation techniques for skin animation. In Proc. ACM SIGGRAPH Symposium on Computer Animation (2002), pp. 129--138.

Digital Library

[57]

{WV97} Wilhelms J., Van Gelder A.: Anatomically based modeling. Comput. Graph. (SIGGRAPH Proc.) (1997), 173--180.

Digital Library

[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.

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Herholz PStuyck TKavan L(2024)A Mesh-based Simulation Framework using Automatic Code GenerationACM Transactions on Graphics10.1145/368798643:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687986
Rist FWang ZPellis DPalma MLiu DGrinspun EMichels D(2024)A Flexible Mold for Facade Panel FabricationACM Transactions on Graphics10.1145/368790643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687906
Show More Cited By

Index Terms

Robust quasistatic finite elements and flesh simulation
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A Robust Time-Stepping Scheme for Quasistatic Rigid Multibody Systems
2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
An effective scheme to simulate low-speed, contact-rich manipulation tasks is to assume quasistatic physics and advance system states by solving linear complementarity problems (LCPs). However, the existing LCP-based quasistatic time-stepping scheme fails ...
Robust hybrid/mixed finite elements for rubber-like materials under severe compression
Abstract
A new family of hybrid/mixed finite elements optimized for numerical stability is introduced. It comprises a linear hexahedral and quadratic hexahedral and tetrahedral elements. The element formulation is derived from a consistent linearization of ...
Normal contact with high order finite elements and a fictitious contact material

Contact problems in solid mechanics are traditionally solved using the h -version of the finite element method. The constraints are enforced along the surfaces of e.g. elastic bodies under consideration. Standard constraint algorithms include penalty ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

July 2005

366 pages

ISBN:1595931988

DOI:10.1145/1073368

Conference Chairs:
Demetri Terzopoulos
New York University, USA
,
Victor Brian Zordan
University of California at Riverside, USA
,
Program Chairs:
Ken Anjyo
OLM Digital, Inc., Japan
,
Petros Faloutsos
University of California at Los Angeles, USA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCA05

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA05: Symposium on Computer Animation

July 29 - 31, 2005

California, Los Angeles

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

243
Total Citations
View Citations
1,449
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)18

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Guo DLi MYang YLi SWang G(2024)Barrier-Augmented Lagrangian for GPU-based Elastodynamic ContactACM Transactions on Graphics10.1145/368798843:6(1-17)Online publication date: 19-Nov-2024
https://doi.org/10.1145/3687988
Herholz PStuyck TKavan L(2024)A Mesh-based Simulation Framework using Automatic Code GenerationACM Transactions on Graphics10.1145/368798643:6(1-17)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687986
Rist FWang ZPellis DPalma MLiu DGrinspun EMichels D(2024)A Flexible Mold for Facade Panel FabricationACM Transactions on Graphics10.1145/368790643:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687906
Chen HLiu HJacobson ALevin DZheng C(2024)Trust-Region Eigenvalue Filtering for Projected NewtonSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687650(1-10)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687650
Park HGrama Srinivasan SCong MKim DKim BSwartz JMuseth KSifakis E(2024)Near-realtime Facial Animation by Deep 3D Simulation Super-ResolutionACM Transactions on Graphics10.1145/367068743:5(1-20)Online publication date: 9-Aug-2024
https://dl.acm.org/doi/10.1145/3670687
Darke AOlander IKim TBurbano AWest R(2024)More Than Killmonger Locs: A Style Guide for Black Hair (in Computer Graphics)ACM SIGGRAPH 2024 Courses10.1145/3664475.3664535(1-251)Online publication date: 27-Jul-2024
https://dl.acm.org/doi/10.1145/3664475.3664535
Li YKamil SCrane KJacobson AGingold Y(2024)IMESH: A DSL for Mesh ProcessingACM Transactions on Graphics10.1145/366218143:5(1-17)Online publication date: 25-Jun-2024
https://dl.acm.org/doi/10.1145/3662181
Chen ALiu ZYang YYuksel C(2024)Vertex Block DescentACM Transactions on Graphics10.1145/365817943:4(1-16)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658179
Shen XCai RBi MLv T(2024)Preconditioned Nonlinear Conjugate Gradient Method for Real-time Interior-point HyperelasticityACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657490(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657490
Li XLi MHan XWang HYang YJiang C(2024)A Dynamic Duo of Finite Elements and Material PointsACM SIGGRAPH 2024 Conference Papers10.1145/3641519.3657449(1-11)Online publication date: 13-Jul-2024
https://dl.acm.org/doi/10.1145/3641519.3657449
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten