research-article

Fast adaptive shape matching deformations

Authors:

Denis Steinemann,

Miguel A. Otaduy,

Markus GrossAuthors Info & Claims

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

Pages 87 - 94

Published: 07 July 2008 Publication History

Abstract

We present a new shape-matching deformation model that allows for efficient handling of topological changes and dynamic adaptive selection of levels of detail. Similar to the recently presented Fast Lattice Shape Matching (FLSM), we compute the position of simulation nodes by convolution of rigid shape matching operators on many overlapping regions, but we rely instead on octree-based hierarchical sampling and an interval-based region definition. Our approach enjoys the efficiency and robustness of shape-matching deformation models, and the same algorithmic simplicity and linear cost as FLSM, but it eliminates its dense sampling requirements. Our method can handle adaptive spatial discretizations, allowing the simulation of more degrees of freedom in arbitrary regions of interest at little additional cost. The method is also versatile, as it can simulate elastic and plastic deformation, it can handle cuts interactively, and it reuses the underlying data structures for efficient handling of (self-)collisions. All this makes it especially useful for interactive applications such as videogames.

References

[1]

{BJ05} Barbič J., James D. L.: Real-time subspace integration for St. Venant-Kirchhoff deformable models. Proc. of ACM SIGGRAPH (2005).

Digital Library

[2]

{BLG94} Belytschko T., Lu Y. Y., Gu L.: Element-free Galerkin methods. International Journal of Numerical Methods in Engineering 37 (1994).

[3]

{BNC96} Bro-Nielsen M., Cotin S.: Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum 15, 3 (1996).

[4]

{BPGK06} Botsch M., Pauly M., Gross M., Kobbelt L.: PriMo: Coupled prisms for intuitive surface modeling. Proc. of Eurographics Symposium on Geometry Processing (2006).

Digital Library

[5]

{BPWG07} Botsch M., Pauly M., Wicke M., Gross M.: Adaptive space deformations based on rigid cells. Proc. of Eurographics (2007).

[6]

{CGC*02a} Capell S., Green S., Curless B., Duchamp T., Popovic Z.: Interactive skeleton-driven dynamic deformations. Proc. of ACM SIGGRAPH (2002).

Digital Library

[7]

{CGC*02b} Capell S., Green S., Curless B., Duchamp T., Popovic Z.: A multiresolution framework for dynamic deformations. Proc. of ACM SIGGRAPH SCA (2002).

Digital Library

[8]

{CLR90} Cormen T., Leiserson C., Rivest R.: Introduction to Algorithms, 2nd Ed. MIT Press, 1990.

Digital Library

[9]

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

Digital Library

[10]

{GGN06} Gao J., Guibas L. J., Nguyen A.: Deformable spanners and its applications. Computational Geometry: Theory and Applications 35, 1 (2006).

Digital Library

[11]

{GKS02} Grinspun E., Krysl P., Schröder P.: CHARMS: A simple framework for adaptive simulation. Proc. of ACM SIGGRAPH (2002).

Digital Library

[12]

{GM97} Gibson S. F., Mirtich B. V.: A Survey of Deformable Modeling in Computer Graphics. Tech. rep., Mitsubishi Electric Research Laboratory, 1997.

[13]

{JP99} James D. L., Pai D. K.: ArtDefo: Accurate real-time deformable objects. Proc. of ACM SIGGRAPH (1999).

Digital Library

[14]

{JP02} James D. L., Pai D. K.: DyRT: Dynamic response textures for real-time deformation simulation with graphics hardware. Proc. of ACM SIGGRAPH (2002).

Digital Library

[15]

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

Digital Library

[16]

{MHHR06} Müller M., Heidelberger B., Hennix M., Ratcliff J.: Position based dynamics. Proc. of VRIPhys (2006).

[17]

{MHTG05} Müller M., Heidelberger B., Teschner M., Gross M.: Meshless deformations based on shape matching. Proc. of ACM SIGGRAPH (2005).

Digital Library

[18]

{MKN*04} Müller M., Keiser R., Nealen A., Pauly M., Gross M., Alexa M.: Point-based animation of elastic, plastic, and melting objects. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation (2004).

Digital Library

[19]

{Moo59} Moore E. F.: The shortest path through a maze. Annals of the Harvard Computation Laboratory 30 (1959), 285--292.

[20]

{NMK*05} Nealen A., Müller M., Keiser R., Boxermann E., Carlson M.: Physically based deformable models in computer graphics. Eurographics STAR (2005).

[21]

{OGRG06} Otaduy M. A., Germann D., Redon S., Gross M.: Adaptive deformations with fast tight bounds. In Proc. of SCA (2006).

Digital Library

[22]

{PKA*05} Pauly M., Keiser R., Adams B., Dutre P., Gross M., Guibas L. J.: Meshless animation of fracturing solids. Proc. of ACM SIGGRAPH (2005).

Digital Library

[23]

{PW89} Pentland A., Williams J.: Good vibrations: Modal dynamics for graphics and animation. Proc. of ACM SIGGRAPH (1989).

Digital Library

[24]

{RJ07} Rivers A. R., James D. L.: FastLSM: Fast lattice shape matching for robust real-time deformation. Proc. of ACM SIGGRAPH (2007).

Digital Library

[25]

{SOG06} Steinemann D., Otaduy M. A., Gross M.: Fast arbitrary splitting of deforming objects. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2006).

Digital Library

[26]

{THM*03} Teschner M., Heidelberger B., Müller M., Pomeranets D., Gross M.: Optimized spatial hashing for collision detection of deformable objects. Proc. of VMV (2003).

[27]

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

Digital Library

[28]

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

Digital Library

Cited By

Ton‐That QKry PAndrews S(2024)Generalized eXtended Finite Element Method for Deformable Cutting via Boolean OperationsComputer Graphics Forum10.1111/cgf.15184Online publication date: 17-Oct-2024
https://doi.org/10.1111/cgf.15184
Kaliappan ABargteil A(2020)Multi-resolution Clustering for Enhanced Elastic Behavior in Clustered Shape MatchingProceedings of the 13th ACM SIGGRAPH Conference on Motion, Interaction and Games10.1145/3424636.3426902(1-10)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3424636.3426902
Bender JMüller MMacklin MBousseau AGutierrez D(2017)A survey on position based dynamics, 2017Proceedings of the European Association for Computer Graphics: Tutorials10.2312/egt.20171034(1-31)Online publication date: 24-Apr-2017
https://dl.acm.org/doi/10.2312/egt.20171034
Show More Cited By

Index Terms

Fast adaptive shape matching deformations
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Animation

Recommendations

Meshless deformations based on shape matching

We present a new approach for simulating deformable objects. The underlying model is geometrically motivated. It handles pointbased objects and does not need connectivity information. The approach does not require any pre-processing, is simple to ...
Shape Metrics Based on Elastic Deformations

Deformations of shapes and distances between shapes are an active research topic in computer vision. We propose an energy of infinitesimal deformations of continuous 1- and 2-dimensional shapes that is based on the elastic energy of deformed objects. ...
Multi-Level Shape Representation Using Global Deformations andLocally Adaptive Finite Elements

We present a model-based method for the multi-level shape, pose estimation and abstraction of an object‘s surface from range data. The surface shape is estimated based on the parameters of a superquadric that is subjected to global deformations (...

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

17
Total Citations
View Citations
450
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ton‐That QKry PAndrews S(2024)Generalized eXtended Finite Element Method for Deformable Cutting via Boolean OperationsComputer Graphics Forum10.1111/cgf.15184Online publication date: 17-Oct-2024
https://doi.org/10.1111/cgf.15184
Kaliappan ABargteil A(2020)Multi-resolution Clustering for Enhanced Elastic Behavior in Clustered Shape MatchingProceedings of the 13th ACM SIGGRAPH Conference on Motion, Interaction and Games10.1145/3424636.3426902(1-10)Online publication date: 16-Oct-2020
https://dl.acm.org/doi/10.1145/3424636.3426902
Bender JMüller MMacklin MBousseau AGutierrez D(2017)A survey on position based dynamics, 2017Proceedings of the European Association for Computer Graphics: Tutorials10.2312/egt.20171034(1-31)Online publication date: 24-Apr-2017
https://dl.acm.org/doi/10.2312/egt.20171034
Gao MTampubolon AJiang CSifakis E(2017)An adaptive generalized interpolation material point method for simulating elastoplastic materialsACM Transactions on Graphics10.1145/3130800.313087936:6(1-12)Online publication date: 20-Nov-2017
https://dl.acm.org/doi/10.1145/3130800.3130879
Zou YLiu P(2017)A new deformation simulation algorithm for elastic-plastic objects based on splat primitivesComputers in Biology and Medicine10.1016/j.compbiomed.2017.02.00783:C(84-93)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.compbiomed.2017.02.007
Nakashima KKoyama YIgarashi TIjiri TInada SNakazawa KSantos LBashford-Rogers T(2016)Interactive deformation of structurally complex heart models constructed from medical imagesProceedings of the 37th Annual Conference of the European Association for Computer Graphics: Short Papers10.5555/3059107.3059124(49-52)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059107.3059124
Chentanez NMüller MMacklin MSolenthaler BTeschner MKavan LWojtan C(2016)Real-time simulation of large elasto-plastic deformation with shape matchingProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2982818.2982841(159-167)Online publication date: 11-Jul-2016
https://dl.acm.org/doi/10.5555/2982818.2982841
Iwamoto NShum HYang LMorishima S(2015)Multi-layer Lattice Model for Real-Time Dynamic Character DeformationComputer Graphics Forum10.1111/cgf.1274934:7(99-109)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1111/cgf.12749
Tournier MNesme MFaure FGilles BKry PBunt A(2014)Seamless adaptivity of elastic modelsProceedings of Graphics Interface 201410.5555/2619648.2619653(17-24)Online publication date: 7-May-2014
https://dl.acm.org/doi/10.5555/2619648.2619653
Sidorov KMarshall ALai YMartin R(2014)Learnt real-time meshless simulationProceedings of the Symposium on Geometry Processing10.1111/cgf.12440(147-156)Online publication date: 9-Jul-2014
https://dl.acm.org/doi/10.1111/cgf.12440
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