A multiresolution framework for dynamic deformations

ABSTRACT

We present a novel framework for the dynamic simulation of elastic deformable solids. Our approach combines classical finite element methodology with a multiresolution subdivision framework in order to produce fast, easy to use, and realistic animations. We represent deformations using a hierarchical basis constructed using volumetric subdivision. The subdivision framework provides topological flexibility and the hierarchical basis allows the simulation to add detail where it is needed. Since volumetric parameterization is difficult for complex models, we support the embedding of objects in domains that are easier to parameterize.

REFERENCES

• 1: Chandrajit Bajaj, Scott Schaefer, Joe Warren, and Guoliang Xu. A subdivision scheme for hexahedral meshes, draft, 2001.
• 2: R. E. Bank. Hierarchical bases and the finite element method, volume 5 of Acta Numerica, pages 1-43. Cambridge University Press, Cambridge, 1996.
• 3: David Baraff , Andrew Witkin, Dynamic simulation of non-penetrating flexible bodies, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.303-308, July 1992
• 4: 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]
• 5: Christoph Bögers , Olof B. Widlund, On finite element domain imbedding methods, SIAM Journal on Numerical Analysis, v.27 n.4, p.963-978, August 1990 [doi>10.1137/0727055]
• 6: Morten Bro-Nielsen and Stephane Cotin. Real-time volumetric deformable models for surgery simulation using finite elements and condensation. Computer Graphics Forum, 15(3):57-66, August 1996.
• 7: 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
• 8: E. Catmull and J. Clark. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design, 10:350-355, September 1978.
• 9: George Celniker , Dave Gossard, Deformable curve and surface finite-elements for free-form shape design, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.257-266, July 1991
• 10: Fehmi Cirak, Michael Ortiz, and Peter Peter Schröder. Subdivision surfaces: a new paradigm for thin-shell finite-element analysis. International Journal for Numerical Methods in Engineering, 47(12):2039-72, April 2000.
• 11: Gilles Debunne, Mathieu Desbrun, Alan Barr, and Marie-Paule Cani. Interactive multiresolution animation of deformable models. Computer Animation and Simulation '99, September 1999.
• 12: 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]
• 13: Tony DeRose , Michael Kass , Tien Truong, Subdivision surfaces in character animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.85-94, July 1998 [doi>10.1145/280814.280826]
• 14: 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
• 15: Petros Faloutsos , Michiel van de Panne , Demetri Terzopoulos, Dynamic Free-Form Deformations for Animation Synthesis, IEEE Transactions on Visualization and Computer Graphics, v.3 n.3, p.201-214, July 1997 [doi>10.1109/2945.620488]
• 16: Steven J. Gortler , Michael F. Cohen, Hierarchical and variational geometric modeling with wavelets, Proceedings of the 1995 symposium on Interactive 3D graphics, p.35-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199410]
• 17: Steven J. Gortler , Peter Schröder , Michael F. Cohen , Pat Hanrahan, Wavelet radiosity, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.221-230, September 1993 [doi>10.1145/166117.166146]
• 18: J.-P. Gourret , N. M. Thalmann , D. Thalmann, Simulation of object and human skin formations in a grasping task, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.21-30, July 1989
• 19: 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
• 20: Michael Hauth and Olaf Etzmuss. A high performance solver for the animation of deformable objects using advanced numerical methods. Computer Graphics Forum (Proceedings of Eurographics 2001), 20(3), 2001.
• 21: 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]
• 22: Rolf M. Koch , Markus H. Gross , Friedrich R. Carls , Daniel F. von Büren , George Fankhauser , Yoav I. H. Parish, Simulating facial surgery using finite element models, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.421-428, August 1996 [doi>10.1145/237170.237281]
• 23: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 24: Ron MacCracken , Kenneth I. Joy, Free-form deformations with lattices of arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.181-188, August 1996 [doi>10.1145/237170.237247]
• 25: G. I. Marchuk, Y. A. Kuznetsov, and A. M. Matsokin. Fictitious domain and domain decomposition methods. Sov. J. Numer. Anal. Math Modeling, 1, 1986.
• 26: Kevin T. McDonnell , Hong Qin, Dynamic Sculpting and Animation of Free-Form Subdivision Solids, Proceedings of the Computer Animation, p.126, May 03-05, 2000
• 27: Kevin T. McDonnell , Hong Qin, FEM-based subdivision solids for dynamic and haptic interaction, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.312-313, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376998]
• 28: Dimitri Metaxas , Demetri Terzopoulos, Dynamic deformation of solid primitives with constraints, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.309-312, July 1992
• 29: 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]
• 30: J. T. Oden and J. N. Reddy. An Introduction to the Mathematical Theory of Finite Elements. John Wiley and Sons, Ltd., New York, London, Sydney, 1982.
• 31: 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
• 32: Guillaume Picinbono , Herve Delingette , Nicholas Ayache, Real-Time Large Displacement Elasticity for Surgery Simulation: Non-linear Tensor-Mass Model, Proceedings of the Third International Conference on Medical Image Computing and Computer-Assisted Intervention, p.643-652, October 11-14, 2000
• 33: John C. Platt , Alan H. Barr, Constraints methods for flexible models, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.279-288, Aug. 1988
• 34: P. M. Prenter. Splines and Variational Methods. John Wiley and Sons, 1975.
• 35: William H. Press, Saul A. Teukolsky, William T. Vetterling, and Brian P. Flannery. Numerical Recipes in C, 2nd. edition. Cambridge University Press, 1992.
• 36: Hong Qin , Chhandomay Mandal , Baba C. Vemuri, Dynamic Catmull-Clark Subdivision Surfaces, IEEE Transactions on Visualization and Computer Graphics, v.4 n.3, p.215-229, July 1998 [doi>10.1109/2945.722296]
• 37: S. H. Martin Roth, Markus H. Gross, Silvio Turello, and Friedrich R. Carls. A bernstein-bézier based approach to soft tissue simulation. Computer Graphics Forum, 17(3):285-294, 1998.
• 38: Thomas W. Sederberg , Scott R. Parry, Free-form deformation of solid geometric models, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.151-160, Aug. 1986
• 39: A. Shabana. Dynamics of Multibody Systems. Cambridge University Press, 1998.
• 40: Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 41: Demetri Terzopoulos , Kurt Fleischer, Modeling inelastic deformation: viscolelasticity, plasticity, fracture, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.269-278, Aug. 1988
• 42: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.205-214, July 1987
• 43: Demetri Terzopoulos , Hong Qin, Dynamic NURBS with geometric constraints for interactive sculpting, ACM Transactions on Graphics (TOG), v.13 n.2, p.103-136, April 1994 [doi>10.1145/176579.176580]
• 44: Demetri Terzopoulos , Andrew Witkin, Physically Based Models with Rigid and Deformable Components, IEEE Computer Graphics and Applications, v.8 n.6, p.41-51, November 1988 [doi>10.1109/38.20317]
• 45: Henrik Weimer , Joe Warren, Subdivision schemes for fluid flow, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.111-120, July 1999 [doi>10.1145/311535.311547]
• 46: 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]

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: Animation

Keywords:
animation, deformation, hierarchical basis, multiresolution, physically-based animation, physically-based modeling