Meshless deformations based on shape matching

ABSTRACT

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 compute, and provides unconditionally stable dynamic simulations.The main idea of our deformable model is to replace energies by geometric constraints and forces by distances of current positions to goal positions. These goal positions are determined via a generalized shape matching of an undeformed rest state with the current deformed state of the point cloud. Since points are always drawn towards well-defined locations, the overshooting problem of explicit integration schemes is eliminated. The versatility of the approach in terms of object representations that can be handled, the efficiency in terms of memory and computational complexity, and the unconditional stability of the dynamic simulation make the approach particularly interesting for games.

REFERENCES

• 1: Marc Alexa , Daniel Cohen-Or , David Levin, As-rigid-as-possible shape interpolation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.157-164, July 2000 [doi>10.1145/344779.344859]
• 2: David Baraff , Andrew Witkin, Large steps in cloth simulation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.43-54, July 1998 [doi>10.1145/280814.280821]
• 3: Ronen Barzel , John F. Hughes , Daniel N. Wood, Plausible motion simulation for computer graphics animation, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.183-197, December 1996, Poitiers, France
• 4: Ronen Barzel, Faking Dynamics of Ropes and Springs, IEEE Computer Graphics and Applications, v.17 n.3, p.31-39, May 1997 [doi>10.1109/38.586016]
• 5: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• 6: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 7: Gilles Debunne , Mathieu Desbrun , Marie-Paule Cani , Alan H. Barr, Dynamic real-time deformations using space & time adaptive sampling, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.31-36, August 2001 [doi>10.1145/383259.383262]
• 8: Mathieu Desbrun , Marie-Paule Gascuel, Animating soft substances with implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.287-290, September 1995 [doi>10.1145/218380.218456]
• 9: Mathieu Desbrun , Marie-Paule Gascuel, Smoothed particles: a new paradigm for animating highly deformable bodies, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.61-76, December 1996, Poitiers, France
• 10: Mathieu Desbrun , Peter Schröder , Alan Barr, Interactive animation of structured deformable objects, Proceedings of the 1999 conference on Graphics interface '99, p.1-8, September 1999, Kingston, Ontario, Canada
• 11: Dave H. Eberly, Game Physics, Elsevier Science Inc., New York, NY, 2003
• 12: Faugeras, O. D., and Hebert, M. 1983. A 3-d recognition and positioning algorithm using geometric matching between primitive surfaces. In Int. Joint Conference on Artificial Intelligence, 996--1002.
• 13: Eitan Grinspun , Petr Krysl , Peter Schröder, CHARMS: a simple framework for adaptive simulation, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 14: Hauser, K. K., Shen, C., and O'Brien, J. F. 2003. Interactive deformation using modal analysis with constraints. In Graphics Interface, A K Peters, CIPS, Canadian Human-Computer Communication Society, 247-256.
• 15: Heidelberger, B., Teschner, M., Keiser, R., Müller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. In Proceedings of Vision, Modeling, Visualization VMV'04, Stanford, USA, 339--346.
• 16: Horn, B. K. P. 1987. Closed-form solution of absolute orientation using unit quaternions. Journal of the Optical Society of America A 4, 4, 629-642.
• 17: G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028541]
• 18: Doug L. James , Dinesh K. Pai, ArtDefo: accurate real time deformable objects, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.65-72, July 1999 [doi>10.1145/311535.311542]
• 19: Doug L. James , Dinesh K. Pai, DyRT: dynamic response textures for real time deformation simulation with graphics hardware, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 20: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 21: K. Kanatani, Analysis of 3-D Rotation Fitting, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.543-549, May 1994 [doi>10.1109/34.291441]
• 22: Michael Kazhdan , Thomas Funkhouser , Szymon Rusinkiewicz, Shape matching and anisotropy, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 23: James R. Kent , Wayne E. Carlson , Richard E. Parent, Shape transformation for polyhedral objects, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.47-54, July 1992
• 24: A. Lorusso , D. W. Eggert , R. B. Fisher, A comparison of four algorithms for estimating 3-D rigid transformations, Proceedings of the 1995 British conference on Machine vision (Vol. 1), p.237-246, July 1995, Birmingham, United Kingdom
• 25: Dimitri Metaxas , Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.309-312, July 1992
• 26: Matthias Müller , Markus Gross, Interactive virtual materials, Proceedings of the 2004 conference on Graphics interface, p.239-246, May 17-19, 2004, London, Ontario, Canada
• 27: Matthias Müller , Julie Dorsey , Leonard McMillan , Robert Jagnow , Barbara Cutler, Stable real-time deformations, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545269]
• 28: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 29: James F. O'Brien , Adam W. Bargteil , Jessica K. Hodgins, Graphical modeling and animation of ductile fracture, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 30: A. Pentland , J. Williams, Good vibrations: model dynamics for graphics and animation, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.215-222, July 1989
• 31: Shen, C., Hauser, K., Gatchalian, C., and O'Brien, J. 2002. Modal analysis for real-time viscoelastic deformation. ACM SIGGRAPH 2002 Conference Abstracts and Applications (july).
• 32: Ken Shoemake , Tom Duff, Matrix animation and polar decomposition, Proceedings of the conference on Graphics interface '92, p.258-264, September 1992, Vancouver, British Columbia, Canada
• 33: J. Teran , S. Blemker , V. Ng Thow Hing , R. Fedkiw, Finite volume methods for the simulation of skeletal muscle, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 34: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 35: Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of Vision, Modeling, Visualization VMV'03, 47--54.
• 36: Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 24, 1 (March), 61--81.
• 37: David Love Tonnesen , Demetri Terzopoulos, Dynamically coupled particle systems for geometric modeling, reconstruction, and animation, 1998
• 38: Shinji Umeyama, Least-Squares Estimation of Transformation Parameters Between Two Point Patterns, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.4, p.376-380, April 1991 [doi>10.1109/34.88573]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality; Animation

General Terms:
Design

Keywords:
deformable modeling, geometric deformation, real-time simulation, shape matching