research-article

Enhanced physically-based animation of deformable bodies using shape-matching

Authors:

Yalmar Ponce Atencio,

Guina Sotomayor Alzamora,

Claudio EsperançaAuthors Info & Claims

Computers in Entertainment (CIE), Volume 7, Issue 4

Article No.: 52, Pages 1 - 19

https://doi.org/10.1145/1658866.1658871

Published: 01 January 2010 Publication History

Abstract

We present a simplified approach for the animation of geometrically complex deformable objects represented by tetrahedral meshes. Our prototype system detects and responds to collisions of objects that are subject to elastic deformations of variable stiffness. The proposed approach combines several techniques, namely, collision detection using spatial hashing, collision response with consistent penetration depth obtained by propagation, estimated displacement vectors for the deformation region, and binary search to separate objects. The dynamics is based on shape-matching and a modal analysis scheme, using an Euler explicit-implicit integrator. Preliminary results show that collisions between objects containing several hundreds tetrahedra can be animated in real time.

References

[1]

Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'00), ACM, New York, 157--164.

Digital Library

[2]

Amanatides, J. and Woo, A. 1987. A fast voxel traversal algorithm for ray tracing. In Eurographics'87, Elsevier, Amsterdam, 3--10.

[3]

Baciu, G., Wong, W., and Sun, H. 1998. Recode: An image based collision detection algorithm. J. Visualization Computer Animation 10, 4, 181--192.

[4]

Baraff, D. and Witkin, A. 1998. Large steps in cloth simulation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'98). ACM, New York, 43--54.

Digital Library

[5]

Bergen, G. V. D. and Bergen, G. J. 2003. Collision Detection. Morgan Kaufmann, San Francisco.

Digital Library

[6]

Bradshaw, G. and O'Sullivan, C. 2004. Adaptive medialaxis approximation for sphere-tree construction. ACM Trans. Graph. 23, 1, 1--26.

Digital Library

[7]

Breen, D., House, D., and Wozny, M. 1994. Predicting the drape of woven cloth using interacting particles. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'94). ACM, New York, 365--372.

Digital Library

[8]

Breen, D., Mauch, S., Whitaker, R., and Mao, J. 2001. 3D metamorphosis between different types of geometric models. In Eurographics 2001 Proceedings, vol. 20, 36--48.

[9]

Chung, K. and Wang, W. 1996. Quick collision detection of polytopes in virtual environments. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology. ACM, New York, 1--4.

[10]

Cohen, J. D., Lin, M. C., Manocha, D., and Ponamgi, M. 1995. I-collide: An interactive and exact collision detection system for large-scale environments. In: Proceedings of the 1995 Symposium on Interactive 3D Graphics (SI3D'95), ACM, New York, 189--ff.

Digital Library

[11]

Desbrun, M., Schr Ö Der, P., and Barr, A. 1999. Interactive animation of structured deformable objects, Graphics Interface, 1--8.

Digital Library

[12]

Eberly, D. 2003. Game Physics. Elsevier, New York.

Digital Library

[13]

Fisher, S. and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Proceedings of the Eurographic Workshop on Computer Animation and Simulation, Springer, New York, 99--111.

Digital Library

[14]

Frisken, S., Perry, R., Rockwood, A., and Jones, T. 2000. Adaptively sampled distance fields: A general representation of shape for computer graphics. In Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'00), ACM, New York, 249--254.

Digital Library

[15]

Ganovelli, F., Dingliana, J., and O'Sullivan, C. 2000. Buckettree: Improving collision detection between deformable objects. Spring Conference in Computer Graphics (SCCG).

[16]

Gottschalk, S., Lin, M. C., and Manocha, D. 1996. Obbtree: A hierarchical structure for rapid interference detection. In Proceedings of the 23rd Annual Conference pn Computer Graphics and Interactive Techniques (SIGGRAPH'96). ACM, New York, 171--180.

Digital Library

[17]

Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. In Proceedings of the International Conference on Computer Graphics and Interactive Techniques. ACM, New York, 871--878.

Digital Library

[18]

Guo, X. 2006. Point-based modeling, animation, and simulation system for computer graphics. PhD dissertation, SUNY at Stony Brook, NY.

Digital Library

[19]

Hauser, K., Shen, C., and O'Brien, J. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface.

[20]

Heidelberger, B., Teschner, M., Keiser, R., and Müller, M. 2004. Consistent penetration depth estimation for deformable collision response. In Proceedings of Vision, Modeling, Visualization (VMV'04), 157--164.

[21]

Heidelberger, B., Teschner, M., and Gross, M. 2003. Real-time volumetric intersections of deforming objects. In Proceeding of Vision, Modeling, Visualization (VMV), 461--468.

[22]

Jakobsen, T. 2001. Advanced character physics. In Proceedings, Game Developer's Conference 2001, GDC Press.

[23]

James, D. L. and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Trans. Graph. 23, 3 (Aug.).

Digital Library

[24]

Kanatani, K. 1994. Analysis of 3-D rotation fitting. IEEE Trans. Pattern Anal. Mach. Intell. 16, 5, 543--549.

Digital Library

[25]

Kaufman, D., Edmunds, T., and Pai, D. 2005. Fast frictional dynamics for rigid bodies. ACM Trans. Graph. 24, 3, 946--956.

Digital Library

[26]

Keiser, R., Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2004. Contact handling for deformable pointbased objects. In Proceedings of Vision, Modeling, Visualization (VMV'04), 339--347.

[27]

Knott, D. and Pai, D. 2003. Cinder: Collision and interference detection in real--time using graphics hardware. In Proceedings of Graphics Interface 2003, 73-80.

[28]

Lancaster, P. and Salkauskas, K. 1981. Surfaces generated by moving least squares methods. In Mathematics of Computation, 141--158.

[29]

Larsson, T. and Akenine-Möller, T. 2001. Collision detection for continuously deforming bodies. In Eurographics 2001, 325--333

[30]

Luque, R. G., Jo, A. L. D. C., and Freitas, C. M. D. S. 2005. Broad-phase collision detection using semi-adjusting bsp-trees. In Proceedings of the 2005 Symposium on Interactive 3D Graphics and Games (I3D'05). ACM, New York, 179--186.

Digital Library

[31]

Moore, M. and Wilhelms, J. 1988. Collision detection and response for computer animationr3. ACM Trans. Comput. Graph. 22, 4, 289--298.

Digital Library

[32]

Müller, M., Dorsey, J., McMillan, L., Jagnow, R., and Cutler, B. 2002. Stable real-time deformations. In Proceedings of the 2002 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'02). ACM, New York, 49--54.

Digital Library

[33]

Müller, M., Keiser, R., Nealen, A., Pauly, M., Gross, M., and Alexa, M. 2004. Point based animation of elastic, plastic and melting objects. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'04), 141--151.

Digital Library

[34]

Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. In Proceedings of SIGGRAPH'05, 471--478.

Digital Library

[35]

Myszkowski, K., Okunev, O. G., and Kunii, T. L. 1995. Fast collision detection between complex solids using rasterizing graphics hardware. In The Visual Computer, vol. 11, Springer, Berlin, 497--512.

[36]

Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2006. Physically based deformable models in computer graphics. In Computer Graphics Forum, Blackwell, 809--836.

[37]

Nedel, L. P. 1993. Simulation of deformable objects based on dynamic analysis. Master's thesis, Curso de Pós-Graduação em Ciência da Computação UFRGS, Porto Alegre, RS, Brasil. nVidia#8482;, 2007. CUDA environment—Compute unified device architecture. http://www.nvidia.com/object/cudahome.html.

[38]

O'Brien, J. F. and Hodgins, J. K. 1999. Graphical modeling and animation of brittle fracture. In Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'99), ACM, New York, 137--146.

Digital Library

[39]

Pauly, M., Pai, D., and Guibas, L. 2004. Quasi-rigid objects in contact. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA'04), 109--119.

Digital Library

[40]

Pentland, A. and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. ACM Trans. Comput. Graph. 23, 3, 207--214.

Digital Library

[41]

Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, San Francisco.

Digital Library

[42]

Sethian, J. A. 1996. A fast marching level set method for monotonically advancing fronts. In Proceedings of the National Academy of Sciences, 1996.

[43]

Shen, C., Hauser, K. K., Gatchalian, C. M., and O'Brien, J. F. 2002. Modal analysis for real-time viscoelastic deformation. In Proceedings of the International Conference on Computer Graphics and Interactive Techniques. ACM, New York, 217.

Digital Library

[44]

Shinya, M. and Forgue, M.-C. 1991. Interference detection through rasterization. J. Visualization Computer Animation 2, 132--134.

[45]

Shoemake, K. and Duff, T. 1992. Matrix animation and polar decomposition. In Proceedings of the Conference on Graphics Interface '92, Morgan Kaufmann, San Francisco, 258--264.

Digital Library

[46]

Sigg, C., Peikert, R., and Gross, M. 2003. Signed distance transform using graphics hardware. In Proceedings of the 14th IEEE Visualization 2003 (VIS'03), IEEE Computer Society, Washington, DC, 12.

Digital Library

[47]

Spillmann, J. and Teschner, M. 2005. Contact surface computation for coarsely sampled deformable objects. In Proceedings of Vision, Modeling, Visualization (VMV'05), 16--18.

[48]

Spillmann, J., Becker, M., and Teschner, M. 2007. Noniterative computation of contact forces for deformable objects. J WSCG 15, 1--3, 33--40.

[49]

Steinemann, D. 2004. Generation and animation of shells. Tech. Rep., Computer Graphics Laboratory, ETH Zürich.

[50]

Sumali, H. 1992. A new adaptive array of vibration sensors. PhD dissertation Virginia Polytechnic Institute and State University.

[51]

Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH'87). ACM, New York, 205--214.

Digital Library

[52]

Teschner, M., Heidelberger, B., Müller, M., and Pomeranets, D. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization (VMV'03).

[53]

Teschner, M., Heidelberger, B., Müller, M., and Gross, M. 2004. A versatile and robust model for geometrically complex deformable solids. In Proceedings of the Computer Graphics International (CGI'04), IEEE Computer Society, Washington, DC, 312--319.

Digital Library

[54]

Turk, G. 1990. Interactive collision detection for molecular graphics. Master's thesis, University of North Carolina at Chapel Hill.

[55]

Umeyama, S. 1991. Least-squares estimation of transformation parameters between two point patterns. IEEE Trans. Pattern Anal. Mach. Intell. 13, 4, 376--380.

Digital Library

[56]

Van Den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graph. Tools 2, 4, 1--13.

Digital Library

[57]

Van Den Bergen, G. 1999. A fast and robust GJK implementation for collision detection of convex objects. J. Graph. Tools 4, 2, 7--25.

Digital Library

[58]

Wu, J. and Kobbelt, L. 2003. Piecewise linear approximation of signed distance fields. In Proceedings of Vision, Modeling and Visualization 03, RWTH, 513--520.

[59]

Zhang, D. and Yuen, M. M. F. 2000. Collision detection for clothed human animation. In Proceedings of the 8th Pacific Conference on Computer Graphics and Applications (PG'00). IEEE Computer Society, Washington, DC, 328.

Digital Library

Cited By

Atencio YIbarra MCerrón JQuispe RCondori RMarín JCarrión M(2021)Particle-Based Physics for Interactive ApplicationsProceedings of Sixth International Congress on Information and Communication Technology10.1007/978-981-16-1781-2_38(411-425)Online publication date: 10-Sep-2021
https://doi.org/10.1007/978-981-16-1781-2_38

Index Terms

Enhanced physically-based animation of deformable bodies using shape-matching
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation types and techniques
      1. Simulation by animation

Recommendations

Efficient collision detection for example-based deformable bodies
MIG '17: Proceedings of the 10th International Conference on Motion in Games

We introduce a new collision proxy for example-based deformable bodies. Specifically, we approximate the deforming geometry as a union of spheres. During pre-computation we perform a sphere packing on the input, undeformed geometry. Then, for each ...
Animation of Deformable Models Using Implicit Surfaces

This paper presents a general approach for designing and animating complex deformable models with implicit surfaces. Implicit surfaces are introduced as an extra layer coating any kind of structure that moves and deforms over time. Offering a compact ...
Physically-based forehead animation including wrinkles

Physically-based animation techniques enable more realistic and accurate animation to be created. We present a fully physically-based approach for efficiently producing realistic-looking animations of facial movement, including animation of expressive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computers in Entertainment

Computers in Entertainment Volume 7, Issue 4

SPECIAL ISSUE: Games

December 2009

245 pages

EISSN:1544-3574

DOI:10.1145/1658866

Issue’s Table of Contents

Copyright © 2010 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2010

Accepted: 01 June 2009

Received: 01 January 2009

Published in CIE Volume 7, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
930
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Atencio YIbarra MCerrón JQuispe RCondori RMarín JCarrión M(2021)Particle-Based Physics for Interactive ApplicationsProceedings of Sixth International Congress on Information and Communication Technology10.1007/978-981-16-1781-2_38(411-425)Online publication date: 10-Sep-2021
https://doi.org/10.1007/978-981-16-1781-2_38

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents