research-article

Flexible simulation of deformable models using discontinuous Galerkin FEM

Authors:

Peter Kaufmann,

Sebastian Martin,

Markus GrossAuthors Info & Claims

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 105 - 115

Published: 07 July 2008 Publication History

Abstract

We propose a simulation technique for elastically deformable objects based on the discontinuous Galerkin finite element method (DG FEM). In contrast to traditional FEM, it overcomes the restrictions of conforming basis functions by allowing for discontinuous elements with weakly enforced continuity constraints. This added flexibility enables the simulation of arbitrarily shaped, convex and non-convex polyhedral elements, while still using simple polynomial basis functions. For the accurate strain integration over these elements we propose an analytic technique based on the divergence theorem. Being able to handle arbitrary elements eventually allows us to derive simple and efficient techniques for volumetric mesh generation, adaptive mesh refinement, and robust cutting.

References

[1]

{ABCM01} Arnold D. N., Brezzi F., Cockburn B., Marini L. D.: Unified analysis of discontinuous Galerkin methods for elliptic problems. SIAM J. Numer. Anal. 39, 5 (2001), 1749--1779.

Digital Library

[2]

{Bat95} Bathe K.-J.: Finite Element Procedures. Prentice Hall, 1995.

[3]

{BBK05} Botsch M., Bommes D., Kobbelt L.: Efficient linear system solvers for geometry processing. In 11th IMA conference on the Mathematics of Surfaces (2005).

Digital Library

[4]

{BG00} Bielser D., Gross M.: Interactive simulation of surgical cuts. In Proc. of Pacific Graphics (2000), pp. 116--125.

Digital Library

[5]

{BGTG03} Bielser D., Glardon P., Teschner M., Gross M.: A state machine for real-time cutting of tetrahedral meshes. In Proc. of Pacific Graphics (2003), pp. 377--386.

Digital Library

[6]

{BPGK06} Botsch M., Pauly M., Gross M., Kobbelt L.: PriMo: Coupled prisms for intuitive surface modeling. In Proc. of Symp. on Geometry Processing (2006), pp. 11--20.

Digital Library

[7]

{BPWG07} Botsch M., Pauly M., Wicke M., Gross M.: Adaptive space deformations based on rigid cells. Computer Graphics Forum (Proc. Eurographics) 26, 3 (2007), 339--347.

[8]

{BWHT07} Bargteil A. W., Wojtan C., Hodgins J. K., Turk G.: A finite element method for animating large viscoplastic flow. ACM Trans. on Graphics (Proc. SIGGRAPH) 26, 3 (2007), 16.1--16.8.

Digital Library

[9]

{BZ73} Babuška I., Zlámal M.: Nonconforming elements in the finite element method with penalty. SIAM J. Numer. Anal. 10 (1973), 863--875.

Digital Library

[10]

{CGC*02} Capell S., Green S., Curless B., Duchamp T., Popović Z.: A multiresolution framework for dynamic deformations. In Proc. of Symp. on Computer Animation (2002), pp. 41--47.

Digital Library

[11]

{Coc03} Cockburn B.: Discontinuous Galerkin methods. Z. Angew. Math. Mech. 80, 11 (2003), 731--754.

[12]

{DD76} Douglas J., Dupont T.: Interior penalty procedures for elliptic and parabolic Galerkin methods. Computing Methods in Applied Science, Lecture Notes in Physics 58 (1976).

[13]

{DDCB01} Debunne G., Desbrun M., Cani M.-P., Barr A. H.: Dynamic real-time deformations using space and time adaptive sampling. In Proc. of ACM SIGGRAPH (2001), pp. 31--36.

Digital Library

[14]

{FKR05} Floater M. S., Kos G., Reimers M.: Mean value coordinates in 3D. Computer Aided Geometric Design 22, 7 (2005), 623--631.

Digital Library

[15]

{FM04} Fries T. P., Matthies H. G.: Classification and overview of meshfree methods. Informatikbericht 2003-03, revised 2004, Institute of Scientific Computing, Technical University Braunschweig, 2004.

[16]

{FvdPT97} Faloutsos P., van de Panne M., Terzopoulos D.: Dynamic free-form deformations for animation synthesis. IEEE Transactions on Visualization and Computer Graphics 3, 3 (1997), 201--214.

Digital Library

[17]

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

Digital Library

[18]

{HL02} Hansbo P., Larson M.: Discontinuous Galerkin methods for incompressible and nearly incompressible elasticity by Nitsche's method. Comput. Methods Appl. Mech. Eng. 191, 17 (2002), 1895--1908.

[19]

{HS04} Hauth M., Strasser W.: Corotational simulation of deformable solids. In Proc. of WSCG (2004), pp. 137--145.

[20]

{Hug00} Hughes T. J. R.: The Finite Element Method. Linear Static and Dynamic Finite Element Analysis. Dover Publications, 2000.

[21]

{JBT04} James D., Barbič J., Twigg C.: Squashing cubes: Automating deformable model construction for graphics. In Proc. of SIGGRAPH '04 Sketches and Applications (2004).

Digital Library

[22]

{JMD*07} Joshi P., Meyer M., DeRose T., Green B., Sanocki T.: Harmonic coordinates for character articulation. ACM Trans. on Graphics (Proc. SIGGRAPH) 26, 3 (2007).

Digital Library

[23]

{JSW05} Ju T., Schaefer S., Warren J.: Mean value coordinates for closed triangular meshes. ACM Trans. on Graphics (Proc. SIGGRAPH) 24, 3 (2005), 561--566.

Digital Library

[24]

{LNSO04} Lew A., Neff P., Sulsky D., Ortiz M.: Optimal BV estimates for a discontinuous Galerkin method in linear elasticity. Applied Mathematics Research Express, 3 (2004), 73--106.

[25]

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

Digital Library

[26]

{MDM*02} Müller M., Dorsey J., McMillan L., Jagnow R., Cutler B.: Stable real-time deformations. In Proc. of Symp. on Computer Animation (2002), pp. 163--170.

Digital Library

[27]

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

Digital Library

[28]

{Mir96} Mirtich B.: Fast and accurate computation of polyhedral mass properties. Journal of Graphics Tools 1, 2 (1996), 31--50.

Digital Library

[29]

{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 Symp. on Computer Animation (2004), pp. 141--151.

Digital Library

[30]

{MTG04} Müller M., Teschner M., Gross M.: Physically based simulation of objects represented by surface meshes. In Proc. of Computer Graphics International (2004), pp. 26--33.

Digital Library

[31]

{NMK*06} Nealen A., Müller M., Keiser R., Boxerman E., Carlson M.: Physically based deformable models in computer graphics. Computer Graphics Forum 25, 4 (2006), 809--836.

[32]

{OBH02} O'Brien J. F., Bargteil A. W., Hodgins J. K.: Graphical modeling and animation of ductile fracture. ACM Trans. on Graphics (Proc. SIGGRAPH) 21, 3 (2002), 291--294.

Digital Library

[33]

{OGRG07} Otaduy M. A., Germann D., Redon S., Gross M.: Adaptive deformations with fast tight bounds. In Proc. of Symp. on Computer Animation (2007), pp. 181--190.

Digital Library

[34]

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

Digital Library

[35]

{PKA*05} Pauly M., Keiser R., Adams B., Dutre P., Gross M., Guibas L. J.: Meshless animation of fracturing solids. ACM Trans. on Graphics (Proc. SIGGRAPH) 24, 3 (2005), 957--964.

Digital Library

[36]

{SDF07} Sifakis E., Der K. G., Fedkiw R.: Arbitrary cutting of deformable tetrahedralized objects. In Proc. of Symp. on Computer Animation (2007), pp. 73--80.

Digital Library

[37]

{SHGS06} Steinemann D., Harders M., Gross M., Szekely G.: Hybrid cutting of deformable solids. In Proc. of IEEE VR (2006), pp. 35--42.

Digital Library

[38]

{SOG06} Steinemann D., Otaduy M. A., Gross M.: Fast arbitrary splitting of deforming objects. In Proc. of Symp. on Computer Animation (2006), pp. 63--72.

Digital Library

[39]

{SSIF07} Sifakis E., Shinar T., Irving G., Fedkiw R.: Hybrid simulation of deformable solids. In Proc. of Symp. on Computer Animation (2007), pp. 81--90.

Digital Library

[40]

{SvdV00} Saad Y., van der Vorst H. A.: Iterative solution of linear systems in the 20th century. J. Comput. Appl. Math. 123, 1--2 (2000), 1--33.

Digital Library

[41]

{TCR} Toledo S., Chen D., Rotkin V.: Taucs: A library of sparse linear solvers. http://www.tau.ac.il/~stoledo/taucs.

[42]

{TEL06} Ten Eyck A., Lew A.: Discontinuous Galerkin methods for non-linear elasticity. International Journal for Numerical Methods in Engineering 67, 9 (2006), 1204--1243.

[43]

{TPBF87} Terzopoulos D., Platt J., Barr A., Fleischer K.: Elastically deformable models. In Proc. of ACM SIGGRAPH (1987), pp. 205--214.

Digital Library

[44]

{WBG07} Wicke M., Botsch M., Gross M.: A finite element method on convex polyhedra. Computer Graphics Forum (Proc. Eurographics) 26, 3 (2007), 355--364.

[45]

{Wih06} Wihler T. P.: Locking-free adaptive discontinuous Galerkin FEM for linear elasticity problems. Mathematics of Computation 75, 255 (2006), 1087--1102.

Cited By

Wolper JChen YLi MFang YQu ZLu JCheng MJiang C(2020)AnisoMPMACM Transactions on Graphics10.1145/3386569.339242839:4(37:1-37:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392428
Wang SDing MGast TZhu LGagniere SJiang CTeran J(2019)Simulation and Visualization of Ductile Fracture with the Material Point MethodProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402592:2(1-20)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340259
Wolper JFang YLi MLu JGao MJiang C(2019)CD-MPMACM Transactions on Graphics10.1145/3306346.332294938:4(1-15)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322949
Show More Cited By

Index Terms

Flexible simulation of deformable models using discontinuous Galerkin FEM

Recommendations

Flexible simulation of deformable models using discontinuous Galerkin FEM

We propose a simulation technique for elastically deformable objects based on the discontinuous Galerkin finite element method (DG FEM). In contrast to traditional FEM, it overcomes the restrictions of conforming basis functions by allowing for ...
A low-order discontinuous Petrov---Galerkin method for the Stokes equations

This paper introduces a low-order discontinuous Petrov-Galerkin (dPG) finite element method (FEM) for the Stokes equations. The ultra-weak formulation utilizes piecewise constant and affine ansatz functions and piecewise affine and discontinuous lowest-...
Adaptive Finite Element Simulation of Incompressible Flows by Hybrid Continuous-Discontinuous Galerkin Formulations

In this work we design hybrid continuous-discontinuous finite element spaces that permit discontinuities on nonmatching element interfaces of nonconforming meshes. Then we develop an equal-order stabilized finite element formulation for incompressible ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '08: Proceedings of the 2008 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

July 2008

230 pages

ISBN:9783905674101

Conference Chairs:
Eugene Fiume,
Jerry Tessendorf,
Program Chairs:
Markus Gross,
Doug James

Sponsors

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

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 07 July 2008

Check for updates

Qualifiers

Research-article

Conference

SCA08

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA08: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

July 7 - 9, 2008

Dublin, Ireland

Acceptance Rates

SCA '08 Paper Acceptance Rate 24 of 60 submissions, 40%;

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
271
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wolper JChen YLi MFang YQu ZLu JCheng MJiang C(2020)AnisoMPMACM Transactions on Graphics10.1145/3386569.339242839:4(37:1-37:16)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392428
Wang SDing MGast TZhu LGagniere SJiang CTeran J(2019)Simulation and Visualization of Ductile Fracture with the Material Point MethodProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402592:2(1-20)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340259
Wolper JFang YLi MLu JGao MJiang C(2019)CD-MPMACM Transactions on Graphics10.1145/3306346.332294938:4(1-15)Online publication date: 12-Jul-2019
https://dl.acm.org/doi/10.1145/3306346.3322949
Pan ZBao HHuang J(2015)Subspace dynamic simulation using rotation-strain coordinatesACM Transactions on Graphics10.1145/2816795.281809034:6(1-12)Online publication date: 2-Nov-2015
https://dl.acm.org/doi/10.1145/2816795.2818090
Wu JWestermann RDick C(2015)A Survey of Physically Based Simulation of Cuts in Deformable BodiesComputer Graphics Forum10.1111/cgf.1252834:6(161-187)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1111/cgf.12528
Gao KFu SGibson RChung EEfendiev Y(2015)Generalized Multiscale Finite-Element Method (GMsFEM) for elastic wave propagation in heterogeneous, anisotropic mediaJournal of Computational Physics10.1016/j.jcp.2015.03.068295:C(161-188)Online publication date: 15-Aug-2015
https://dl.acm.org/doi/10.1016/j.jcp.2015.03.068
Weber DMueller-Roemer JAltenhofen CStork AFellner D(2015)Deformation simulation using cubic finite elements and efficient p-multigrid methodsComputers and Graphics10.1016/j.cag.2015.06.01053:PB(185-195)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.cag.2015.06.010
Kim TJames DLiu KBridson RBargteil Avan de Panne M(2011)Physics-based character skinning using multi-domain subspace deformationsProceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1145/2019406.2019415(63-72)Online publication date: 5-Aug-2011
https://dl.acm.org/doi/10.1145/2019406.2019415
Faure FGilles BBousquet GPai D(2011)Sparse meshless models of complex deformable solidsACM Transactions on Graphics10.1145/2010324.196496830:4(1-10)Online publication date: 25-Jul-2011
https://dl.acm.org/doi/10.1145/2010324.1964968
Faure FGilles BBousquet GPai D(2011)Sparse meshless models of complex deformable solidsACM SIGGRAPH 2011 papers10.1145/1964921.1964968(1-10)Online publication date: 7-Aug-2011
https://dl.acm.org/doi/10.1145/1964921.1964968
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