research-article

Globally coupled collision handling using volume preserving impulses

Authors:

Eftychios Sifakis,

Sebastian Marino,

Joseph TeranAuthors Info & Claims

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

Pages 147 - 153

Published: 07 July 2008 Publication History

Abstract

We present a novel algorithm for collision processing on triangulated meshes. Our method robustly maintains a collision free state on complex geometries while resorting to collision resolution at time intervals often comparable to the frame rate. Our approach is motivated by the behavior of a thin layer of fluid inserted in the empty space between nearly-colliding parts of the simulated surface, acting as a cushioning mechanism. Point-triangle or edge-edge pairs on a collision course are naturally resolved by the incompressible response of this fluid buffer. This response is formulated into a globally coupled nonlinear system which we solve using Newton iteration and symmetric, positive definite solvers. The globally coupled treatment of collisions allows us to resolve up to two orders of magnitude more collisions than traditional greedy algorithms (e.g. Gauss-Seidel collision response) and take substantially larger time steps without compromising the visual quality of the simulation.

References

[1]

{BA04} Boxerman E., Ascher U.: Decomposing cloth. In Proc. ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2004), pp. 153--161.

Digital Library

[2]

{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

[3]

{BHW94} Breen D. E., House D. H., Wozny M. J.: Predicting the drape of woven cloth using interacting particles. Comput. Graph. (SIGGRAPH Proc.) (1994), 365--372.

Digital Library

[4]

{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

[5]

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

Digital Library

[6]

{BWH*06} Bergou M., Wardetzky M., Harmon D., Zorin D., Grinspun E.: A quadratic bending model for inextensible surfaces. In Proc. of Eurographics Symp. on Geometry Processing (2006), pp. 227--230.

Digital Library

[7]

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

Digital Library

[8]

{CYMTT92} Carignan M., Yang Y., Magnenat-Thalmann N., Thalmann D.: Dressing animated synthetic actors with complex deformable clothes. Comput. Graph. (SIGGRAPH Proc.) (1992), 99--104.

Digital Library

[9]

{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

[10]

{GHF*07} Goldenthal R., Harmon D., Fattal R., Bercovier M., Grinspun E.: Efficient simulation of inextensible cloth. ACM Trans. Graph. (SIGGRAPH Proc.) 26, 3 (2007).

Digital Library

[11]

{GKJ*05} Govindaraju N., Knott D., Jain N., Kabul I., Tamstorf R., Gayle R., Lin M., Manocha D.: Interactive collision detection between deformable models using chromatic decomposition. ACM Trans. Graph. (SIGGRAPH Proc.) (2005), 991--999.

Digital Library

[12]

{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

[13]

{HB00} House D. H., Breen D. E. (Eds.): Cloth modeling and animation. A. K. Peters, 2000.

Digital Library

[14]

{ISF07} Irving G., Schroeder C., Fedkiw R.: Volume conserving finite element simulations of deformable models. ACM Trans. Graph. (SIGGRAPH Proc.) (in press) 26, 3 (2007).

Digital Library

[15]

{MDDB01} Meyer M., Debunne G., Desbrun M., Barr A. H.: Interactive animation of cloth-like objects in virtual reality. The Journal of Visualization and Computer Animation 12, 1 (2001), 1--12.

[16]

{OAW06} Oh S., Ahn J., Wohn K.: Low damped cloth simulation. Visual Computer 22, 2 (Feb. 2006).

Digital Library

[17]

{OITN92} Okabe H., Imaoka H., Tomiha T., Niwaya H.: Three dimensional apparel CAD system. Comput. Graph. (SIGGRAPH Proc.) (1992), 105--110.

Digital Library

[18]

{Pes02} Peskin C.: The immersed boundary method. Acta Numerica 11 (2002), 479--517.

[19]

{PF02} Parks D., Forsyth D.: Improved integration for cloth simulation. In Proc. of Eurographics (2002), Comput. Graph. Forum, Eurographics Assoc.

[20]

{SGG*06} Sud A., Govindaraju N., Gayle R., Kabul I., Manocha D.: Fast proximity computation among deformable models using discrete Voronoi diagrams. ACM Trans. Graph. (SIGGRAPH Proc.) (2006), 1144--1153.

Digital Library

[21]

{TC92} Thingvold J. A., Cohen E.: Physical modeling with B-spline surfaces for interactive design and animation. Comput. Graph. (SIGGRAPH Proc.) (1992), 129--137.

Digital Library

[22]

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

Digital Library

[23]

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

Digital Library

[24]

{TWS06} Thomaszewski B., Wacker M., Strasser W.: A consistent bending model for cloth simulation with corotational subdivision finite elements. In Proc. ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2006).

Digital Library

[25]

{VCMT95} Volino P., Courchesne M., Magnenat-Thalmann N.: Versatile and efficient techniques for simulating cloth and other deformable objects. Comput. Graph. (SIGGRAPH Proc.) (1995), 137--144.

Digital Library

[26]

{VMT94} Volino P., Magnenat-Thalmann N.: Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. In Proc. of Eurographics (1994), vol. 13 of Comput. Graph. Forum, Eurographics Assoc., pp. C-155--166.

[27]

{VMT05} Volino P., Magnenat-Thalmann N.: Implicit midpoint integration and adaptive damping for efficient cloth simulation. Computer Animation and Virtual Worlds 16 (2005), 163--175.

Digital Library

[28]

{VMT06} Volino P., Magnenat-Thalmann N.: Simple linear bending stiffness in particle systems. In Proc. of the ACM SIGGRAPH/Eurographics Symp. on Comput. Anim. (2006), pp. 101--105.

Digital Library

[29]

{Wei86} Weil J.: The synthesis of cloth objects. Comput. Graph. (SIGGRAPH Proc.) (1986), 49--54.

Digital Library

Cited By

Li CTang MTong RCai MZhao JManocha D(2020)P-clothACM Transactions on Graphics10.1145/3414685.341776339:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417763
Li MFerguson ZSchneider TLanglois TZorin DPanozzo DJiang CKaufman D(2020)Incremental potential contactACM Transactions on Graphics10.1145/3386569.339242539:4(49:1-49:20)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392425
Han XGast TGuo QWang SJiang CTeran J(2019)A Hybrid Material Point Method for Frictional Contact with Diverse MaterialsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402582:2(1-24)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340258
Show More Cited By

Index Terms

Globally coupled collision handling using volume preserving impulses
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

Muscle Fatigue Assessment in Manual Handling of Loads Using Motion Analysis and Accelerometers
A coupled level-set and volume-of-fluid method for simulating axi-symmetric incompressible two-phase flows

A coupled level-set and volume-of-fluid (CLSVOF) method, combining the advantages of LS method and VOF method, is presented for simulating axi-symmetric incompressible liquid-gas flow problems. In this method, the interface is implicitly captured by the ...
Globally convergent Jacobian smoothing inexact Newton methods for NCP

A new smoothing algorithm for the solution of nonlinear complementarity problems (NCP) is introduced in this paper. It is based on semismooth equation reformulation of NCP by Fischer---Burmeister function and its related smooth approximation. In each ...

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

15
Total Citations
View Citations
186
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li CTang MTong RCai MZhao JManocha D(2020)P-clothACM Transactions on Graphics10.1145/3414685.341776339:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417763
Li MFerguson ZSchneider TLanglois TZorin DPanozzo DJiang CKaufman D(2020)Incremental potential contactACM Transactions on Graphics10.1145/3386569.339242539:4(49:1-49:20)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.1145/3386569.3392425
Han XGast TGuo QWang SJiang CTeran J(2019)A Hybrid Material Point Method for Frictional Contact with Diverse MaterialsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/33402582:2(1-24)Online publication date: 26-Jul-2019
https://dl.acm.org/doi/10.1145/3340258
Tang Mwang tLiu ZTong RManocha D(2018)I-clothACM Transactions on Graphics10.1145/3272127.327500537:6(1-10)Online publication date: 4-Dec-2018
https://dl.acm.org/doi/10.1145/3272127.3275005
Guo QHan XFu CGast TTamstorf RTeran J(2018)A material point method for thin shells with frictional contactACM Transactions on Graphics10.1145/3197517.320134637:4(1-15)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201346
Weidner NPiddington KLevin DSueda S(2018)Eulerian-on-lagrangian cloth simulationACM Transactions on Graphics10.1145/3197517.320128137:4(1-11)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201281
Jiang CGast TTeran J(2017)Anisotropic elastoplasticity for cloth, knit and hair frictional contactACM Transactions on Graphics10.1145/3072959.307362336:4(1-14)Online publication date: 20-Jul-2017
https://dl.acm.org/doi/10.1145/3072959.3073623
Teng YLevin DKim T(2016)Eulerian solid-fluid couplingACM Transactions on Graphics10.1145/2980179.298022935:6(1-8)Online publication date: 5-Dec-2016
https://dl.acm.org/doi/10.1145/2980179.2980229
Wu KYuksel CWyman CYuksel C(2016)Real-time hair mesh simulationProceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games10.1145/2856400.2856412(59-64)Online publication date: 27-Feb-2016
https://dl.acm.org/doi/10.1145/2856400.2856412
Müller MChentanez NKim TMacklin M(2015)Air meshes for robust collision handlingACM Transactions on Graphics10.1145/276690734:4(1-9)Online publication date: 27-Jul-2015
https://dl.acm.org/doi/10.1145/2766907
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