research-article

Element-wise mixed implicit-explicit integration for stable dynamic simulation of deformable objects

Authors:

M. HardersAuthors Info & Claims

SCA '11: Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 257 - 266

https://doi.org/10.1145/2019406.2019440

Published: 05 August 2011 Publication History

Abstract

In order to evolve a deformable object in time, the underlying equations of motion have to be numerically integrated. This is commonly done by employing either an explicit or an implicit integration scheme. While explicit methods are only stable for small time steps, implicit methods are unconditionally stable. In this paper, we present a novel methodology to combine explicit and implicit linear integration approaches, based on element-wise stability considerations. First, we detect the ill-shaped simulation elements which hinder the stable explicit integration of the element nodes as a pre-computation step. These nodes are then simulated implicitly, while the remaining parts of the mesh are explicitly integrated. As a consequence, larger integration time steps than in purely explicit methods are possible, while the computation time per step is smaller than in purely implicit integration. During modifications such as cutting or fracturing, only newly created or modified elements need to be reevaluated, thus making the technique usable in real-time simulations. In addition, our method reduces problems due to numerical dissipation.

Supplementary Material

JPG File (p257-fierz.jpg)

Download
15.63 KB

MOV File (p257-fierz.mov)

Download
40.15 MB

References

[1]

{ACSYD05} Alliez P., Cohen-Steiner D., Yvinec M., Desbrun M.: Variational Tetrahedral Meshing. ACM Transactions on Graphics 24, 3 (2005), 617--625. 2

Digital Library

[2]

{AFSH10} Aguinaga I., Fierz B., Spillmann J., Harders M.: Filtering of High Modal Frequencies for Stable Real-time Explicit Integration of Deformable Objects using the Finite ElementMethod. Progress in biophysics and molecular biology 103, 2--3 (2010), 225--235. 3

[3]

{BA04} Boxerman E., Ascher U.: Decomposing Cloth. In Proc. Symposium on Computer Animation (2004), pp. 153--161. 3

Digital Library

[4]

{BG00} Bielser D., Gross M. H.: Interactive Simulation of Surgical Cuts. In Proc. Pacific Conference on Computer Graphics and Applications (2000), pp. 116--125. 2

Digital Library

[5]

{BJ05} Barbic J., James D. L.: Real-Time Subspace Integration for St. Venant-Kirchhoff Deformable Models. ACM Transactions on Graphics 24, 3 (2005), 982. 2

Digital Library

[6]

{BM78} Belytschko T., Mullen R.: Stability of Explicit-Implicit Mesh Partitions in Time Integration. International Journal for Numerical Methods in Engineering 12, 10 (1978), 1575--1586. 2, 3, 5

[7]

{BMF03} Bridson R., Marino S., Fedkiw R.: Simulation of Clothing with Folds and Wrinkles. In Proc. Symposium on Computer Animation (2003), pp. 28--36. 3

Digital Library

[8]

{BYM79} Belytschko T., Yen H., Mullen R.: Mixed Methods for Time Integration. Computer Methods in Applied Mechanics and Engineering 17--18 (1979), 259--275. 5

[9]

{CPSS10} Chao I., Pinkall U., Sanan P., Schröder P.: A Simple Geometric Model for Elastic Deformations. ACM Transactions on Graphics 29, 4 (2010), 1--6. 3

Digital Library

[10]

{DDCB01} Debunne G., Desbrun M., Cani M.-P., Barr A. H.: Dynamic Real-Time Deformations using Space & Time Adaptive Sampling. In ACM SIGGRAPH Computer Graphics (2001), pp. 31--36. 3

Digital Library

[11]

{DSB99} Desbrún M., Schröder P., Barr A.: Interactive Animation of Structured Deformable Objects. In Proc. Graphics Interface (1999), pp. 1--8. 4

Digital Library

[12]

{EEH00} Eberhardt B., Etzmusso., Hauth M.: Implicit-Explicit Schemes for Fast Animation with Particle Systems. In Eurographics Computer Animation and Simulation Workshop (2000), pp. 137--151. 2, 3

[13]

{FSAH11} Fierz B., Spillmann J., Aguinaga I., Harders M.: Maintaining Large Time Steps in Explicit Finite Element Simulations using Shape Matching. IEEE Transactions on Visualization and Computer Graphics (2011). 2, 3, 4, 5

Digital Library

[14]

{FSH10} Fierz B., Spillmann J., Harders M.: Stable Explicit Integration of Deformable Objects by Filtering High Modal Frequencies. Journal of WSCG 18, 1--3 (2010), 81--88. 3

[15]

{HL06} Hauret P., Le Tallec P.: Energy-controlling Time Integration Methods for Nonlinear Elastodynamics and Low-velocity Impact. Computer Methods in Applied Mechanics and Engineering 195, 37--40 (2006), 4890--4916. 4

[16]

{HLW83} Hughes T. J. R., Levit I., Winget J.: Element-by-Element Implicit Algorithms for Heat Conduction. Journal of Engineering Mechanics 109, 2 (1983), 576--585. 3

[17]

{HLW06} Hairer E., Lubich C., Wanner G.: Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. Springer, 2006. 3

[18]

{HSO03} Hauser K. K., Shen C., O'Brien J. F.: Interactive Deformation Using Modal Analysis with Constraints. In Proc. Graphics Interface (2003), pp. 247--256. 2

[19]

{KB04} Keckeisen M., Blochinger W.: Parallel Implicit Integration for Cloth Animations on Distributed Memory Architectures. In Eurographics Symposium on Parallel Graphics and Visualization (2004). 3

Digital Library

[20]

{KYT*06} Kharevych L., Yang W., Tong Y., Kanso E., Marsden J. E., Schröder P., Desbrun M.: Geometric, Variational Integrators for Computer Animation. In Proc. Symposium on Computer Animation (2006), pp. 43--51. 3

Digital Library

[21]

{LS07} Labelle F., Shewchuk J. R.: Isosurface Stuffing: Fast Tetrahedral Meshes with Good Dihedral Angles. ACM Transactions on Graphics 26, 3 (2007), 57. 2

Digital Library

[22]

{MCP*09} Mullen P., Crane K., Pavlov D., Tong Y., Desbrun M.: Energy-preserving Integrators for Fluid Animation. ACM Transactions on Graphics 28, 3 (2009), 1. 4

Digital Library

[23]

{MG04} Müller M., Gross M.: Interactive Virtual Materials. In Proc. Graphics Interface (2004), pp. 239--246. 3, 6

Digital Library

[24]

{MHTG05} Müller M., Heidelberger B., Teschner M., Gross M.: Meshless Deformations Based on Shape Matching. ACM Transactions on Graphics 24, 3 (2005), 471--478. 4

Digital Library

[25]

{PW89} Pentland A., Williams J.: Good Vibrations: Modal Dynamics for Graphics and Animation. ACM SIGGRAPH Computer Graphics 23, 3 (1989), 207--214. 2

Digital Library

[26]

{Ram02} Rama Mohan Rao A.: A Parallel Mixed Time Integration Algorithm for Nonlinear Dynamic Analysis. Advances in Engineering Software 33, 5 (May 2002), 261--271. 3

Digital Library

[27]

{Sch97} Schöberl J.: NETGEN An Advancing Front 2D/3DMesh Generator Based on Abstract Rules. Computing and Visualization in Science 1, 1 (July 1997), 41--52. 2

[28]

{She94} Shewchuk J. R.: An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Tech. rep., 1994. 6

Digital Library

[29]

{She98} Shewchuk J. R.: Tetrahedral Mesh Generation by Delaunay Refinement. In Proc. Symposium on Computational Geometry (1998), pp. 86--95. 2

Digital Library

[30]

{She02} Shewchuk J. R.: What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. In Proc. International Meshing Roundtable (2002), pp. 115--126. 2, 4, 5

[31]

{SN10} Schafer N., Negrut D.: A Quantitative Assessment of the Potential of Implicit Integration Methods for Molecular Dynamics Simulation. Journal of Computational and Nonlinear Dynamics 5, 3 (2010). 4

[32]

{TL88} Tezduyar T. E., Liou J.: Element-by-element and Implicit-explicit Finite Element Formulations for Computational Fluid Dynamics. In International Symposium on Domain Decomposition Methods for Partial Differential Equations (1988), pp. 281--300. 3

[33]

{VB05} Vanzuijlen A., Bijl H.: Implicit and Explicit Higher Order Time Integration Schemes for Structural Dynamics and Fluid-Structure Interaction Computations. Computers Structures 83, 2--3 (2005), 93--105. 3

Digital Library

Cited By

Lee DKang HLee I(2023)ClothCombo: Modeling Inter-Cloth Interaction for Draping Multi-Layered ClothesACM Transactions on Graphics10.1145/361837642:6(1-13)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618376
Wu NChao QChen YXu WLiu CManocha DSun WHan YYao XJin X(2021)AgentDress: Realtime Clothing Synthesis for Virtual Agents using Plausible DeformationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.310642927:11(4107-4118)Online publication date: Nov-2021
https://doi.org/10.1109/TVCG.2021.3106429
Luna Laija VGizem Ozdil PHashtrudi-Zaad K(2020)Effect of Direct Velocity Measurement on the Stability of Haptic Simulation Systems2020 IEEE Haptics Symposium (HAPTICS)10.1109/HAPTICS45997.2020.ras.HAP20.27.fb93aa04(712-717)Online publication date: Mar-2020
https://doi.org/10.1109/HAPTICS45997.2020.ras.HAP20.27.fb93aa04
Show More Cited By

Index Terms

Element-wise mixed implicit-explicit integration for stable dynamic simulation of deformable objects
1. Computing methodologies
  1. Computer graphics
    1. Animation

Recommendations

Stable Simulations of Deformable Objects Using Explicit Integration
CW '13: Proceedings of the 2013 International Conference on Cyberworlds

We present a new approach that deals with the stability limit of explicit integration schemes in simulations of deformable objects based on the finite element method. The underlying idea consists of using a large time step of a coarse tetrahedral mesh ...
Parallelizable stable explicit numerical integration for efficient circuit simulation
DAC '09: Proceedings of the 46th Annual Design Automation Conference

This work exploits the recently developed telescopic projective numerical integration method for efficient parallel circuit simulation. Stable explicit numerical integration is achieved by adopting an explicit inner integrator (e.g. forward Euler) in a ...
Implicit-explicit second derivative general linear methods with strong stability preserving explicit part
Abstract
In this paper, we discuss the class of implicit–explicit (IMEX) methods for systems of ordinary differential equations where the explicit part has strong stability preserving (SSP) property, while the implicit part of the method has ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '11: Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

August 2011

297 pages

ISBN:9781450309233

DOI:10.1145/2019406

Conference Chairs:
Karen Liu
Georgia Institute of Technology
,
Robert Bridson
University of British Columbia
,
Editor:
Stephen N. Spencer
University of Washington
,
Program Chairs:
Adam Bargteil
University of Utah
,
Michiel van de Panne
University of British Columbia

Copyright © 2011 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: 05 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Seventh Framework Programme

Conference

SCA '11

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA '11: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation 2011

August 5 - 7, 2011

British Columbia, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
428
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)3

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee DKang HLee I(2023)ClothCombo: Modeling Inter-Cloth Interaction for Draping Multi-Layered ClothesACM Transactions on Graphics10.1145/361837642:6(1-13)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618376
Wu NChao QChen YXu WLiu CManocha DSun WHan YYao XJin X(2021)AgentDress: Realtime Clothing Synthesis for Virtual Agents using Plausible DeformationsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.310642927:11(4107-4118)Online publication date: Nov-2021
https://doi.org/10.1109/TVCG.2021.3106429
Luna Laija VGizem Ozdil PHashtrudi-Zaad K(2020)Effect of Direct Velocity Measurement on the Stability of Haptic Simulation Systems2020 IEEE Haptics Symposium (HAPTICS)10.1109/HAPTICS45997.2020.ras.HAP20.27.fb93aa04(712-717)Online publication date: Mar-2020
https://doi.org/10.1109/HAPTICS45997.2020.ras.HAP20.27.fb93aa04
Byeon SLee D(2020)Method for real-time simulation of haptic interaction with deformable objects using GPU-based parallel computing and homogeneous hexahedral elementsComputational Mechanics10.1007/s00466-020-01815-3Online publication date: 16-Jan-2020
https://doi.org/10.1007/s00466-020-01815-3
Macklin MStorey KLu MTerdiman PChentanez NJeschke SMüller MLee SSchroeder CBatty CHuang J(2019)Small steps in physics simulationProceedings of the 18th annual ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.1145/3309486.3340247(1-7)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3309486.3340247
Luna Laija VCleveland DHashtrudi-Zaad K(2019)Uncoupled Stability of a Haptic System with Position-Velocity Sampling2019 IEEE World Haptics Conference (WHC)10.1109/WHC.2019.8816076(473-478)Online publication date: Jul-2019
https://doi.org/10.1109/WHC.2019.8816076
Rojas JLiu TKavan L(2019)Average Vector Field Integration for St. Venant-Kirchhoff Deformable ModelsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2018.285123325:8(2529-2539)Online publication date: 1-Aug-2019
https://doi.org/10.1109/TVCG.2018.2851233
Dinev DLiu TLi JThomaszewski BKavan L(2018)FEPRACM Transactions on Graphics10.1145/3197517.320127737:4(1-12)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201277
Fang YHu YHu SJiang C(2018)A Temporally Adaptive Material Point Method with Regional Time SteppingComputer Graphics Forum10.1111/cgf.1352437:8(195-204)Online publication date: 12-Sep-2018
https://doi.org/10.1111/cgf.13524
Manteaux PWojtan CNarain RRedon SFaure FCani M(2017)Adaptive Physically Based Models in Computer GraphicsComputer Graphics Forum10.1111/cgf.1294136:6(312-337)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1111/cgf.12941
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.

Media

Figures

Other

Tables

View Table of Contents