Dynamic real-time deformations using space & time adaptive sampling

ABSTRACT

This paper presents a robust, adaptive method for animating dynamic visco-elastic deformable objects that provides a guaranteed frame rate. Our approach uses a novel automatic space and time adaptive level of detail technique, in combination with a large-displacement (Green) strain tensor formulation. The body is partitioned in a non-nested multiresolution hierarchy of tetrahedral meshes. The local resolution is determined by a quality condition that indicates where and when the resolution is too coarse. As the object moves and deforms, the sampling is refined to concentrate the computational load into the regions that deform the most. Our model consists of a continuous differential equation that is solved using a local explicit finite element method. We demonstrate that our adaptive Green strain tensor formulation suppresses unwanted artifacts in the dynamic behavior, compared to adaptive mass-spring and other adaptive approaches. In particular, damped elastic vibration modes are shown to be nearly unchanged for several levels of refinement. Results are presented in the context of a virtual reality system. The user interacts in real-time with the dynamic object through the control of a rigid tool, attached to a haptic device driven with forces derived from the method.

REFERENCES

• 1: 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]
• 2: R. Berka. Reduction of computations in physics-based animation using level of detail. In Proceedings of the 1997 Spring Conference on Computer Graphics, pages 69-76, 1997.
• 3: M. Bro-Nielsen and S. Cotin. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. In Eurographics, pages 21-30, 1996.
• 4: Deborah A. Carlson , Jessica K. Hodgins, Simulation levels of detail for real-time animation, Proceedings of the conference on Graphics interface '97, p.1-8, May 1997, Kelowna, British Columbia, Canada
• 5: Stephen Chenney , David Forsyth, View-dependent culling of dynamic systems in virtual environments, Proceedings of the 1997 symposium on Interactive 3D graphics, p.55-58, April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253307]
• 6: Stéphane Cotin , Hervé Delingette , Nicholas Ayache, Real-Time Elastic Deformations of Soft Tissues for Surgery Simulation, IEEE Transactions on Visualization and Computer Graphics, v.5 n.1, p.62-73, January 1999 [doi>10.1109/2945.764872]
• 7: G. Debunne, M. Desbrun, A. Barr, and M.-P. Cani. Interactive multiresolution animation of deformable models. In 10th Eurographics Workshop on Computer Animation and Simulation, Milano, 1999.
• 8: Gilles Debunne , Marie-Paule Cani , Mathieu Desbrun , Alan Barr, Adaptive Simulation of Soft Bodies in Real-Time, Proceedings of the Computer Animation, p.15, May 03-05, 2000
• 9: Hervé Delingette , Stéphane Cotin , Nicholas Ayache, A Hybrid Elastic Model allowing Real-Time Cutting, Deformations and Force-Feedback for Surgery Training and Simulation, Proceedings of the Computer Animation, p.70, May 26-28, 1999
• 10: M. Desbrun, M. Meyer, P. Schroder, and A. Barr. Discrete differentialgeometry operators in 2d and 3d. http://www-grail.usc.edu/pubs/. Submitted, 2000.
• 11: 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
• 12: Y.C. Fung. Foundations of Solids Mechanics. Prentice-Hall, 1965.
• 13: F. Ganovelli, P. Cignoni, C. Montani, and R. Scopigno. A multiresolution model for soft objects supporting interactive cuts and lacerations. In Proceedings of Eurographics, 2000.
• 14: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 15: J.-D. Gascuel, M.-P. Cani, M. Desbrun, E. Leroi, and C. Mirgon. Simulating landslides for natural disaster prevention. In Proceedings of the 8th Eurographics Workshop on Animation and Simulation, 1998.
• 16: Allen Van Gelder, Approximate simulation of elastic membranes by triangulated spring meshes, Journal of Graphics Tools, v.3 n.2, p.21-42, 1 February 1998
• 17: S. F. Gibson and B. Mirtich. A survey of deformable modeling in computer graphics. Technical report, MERL, November 1997. TR-97- 19, http://www.merl.com.
• 18: J.-P. Gourret , N. M. Thalmann , D. Thalmann, Simulation of object and human skin formations in a grasping task, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.21-30, July 1989
• 19: Dave Hutchinson , Martin Preston , Terry Hewitt, Adaptive refinement for mass/spring simulations, Proceedings of the Eurographics workshop on Computer animation and simulation '96, p.31-45, December 1996, Poitiers, France
• 20: 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]
• 21: Jean-Christophe Lombardo , Marie-Paule Cani , Fabrice Neyret, Real-time Collision Detection for Virtual Surgery, Proceedings of the Computer Animation, p.82, May 26-28, 1999
• 22: James F. O'Brien , Jessica K. Hodgins, Graphical modeling and animation of brittle fracture, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.137-146, July 1999 [doi>10.1145/311535.311550]
• 23: A. Pentland , J. Williams, Good vibrations: model dynamics for graphics and animation, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.207-214, July 1989
• 24: Barry F. Smith , Petter E. Bjørstad , William D. Gropp, Domain decomposition: parallel multilevel methods for elliptic partial differential equations, Cambridge University Press, New York, NY, 1996
• 25: 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
• 26: Andrew Witkin , William Welch, Fast animation and control of nonrigid structures, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.243-252, September 1990, Dallas, TX, USA [doi>10.1145/97879.565650]
• 27: Yan Zhuang and John Canny. Real-time and physically realistic global deformation. In SIGGRAPH'99 Sketches and Apllication Proceedings, aug 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Animation

General Terms:
Performance, Reliability