Progressive deforming meshes based on deformation oriented decimation and dynamic connectivity updating

ABSTRACT

We present a method for progressive deforming meshes. Most existing mesh decimation methods focus on static meshes. However, there are more and more animation data today, and it is important to address the problem of simplifying deforming meshes. Our method is based on deformation oriented decimation (DOD) error metric and dynamic connectivity updating (DCU) algorithm. Deformation oriented decimation extends the deformation sensitivity decimation (DSD) error metric by augmenting an additional term to model the distortion introduced by deformation. This new metric preserves not only geometric features but also areas with large deformation. Using this metric, a static reference connectivity is extracted for the whole animation. Dynamic connectivity updating algorithm utilizes vertex trees to further reduce geometric distortion by allowing the connectivity to change. Temporal coherence in the dynamic connectivity between frames is achieved by penalizing large deviations from the reference connectivity. The combination of DOD and DCU demonstrates better simplification and triangulation performance than previous methods for deforming mesh simplification.

REFERENCES

• 1: {AM00} Alexa M., Müller W.: Representing animations by principal components. Computer Graphics Forum (Eurographics 2000 Conference Proceedings) 19, 3 (2000), 411--418.
• 2: Hector M. Briceño , Pedro V. Sander , Leonard McMillan , Steven Gortler , Hugues Hoppe, Geometry videos: a new representation for 3D animations, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 3: {CRS98} Cignoni P., Rocchini C., Scopigno R.: Metro: measuring error on simplified surfaces. Computer Graphics Forum 17, 2 (1998), 167--174.
• 4: David Cohen-Steiner , Pierre Alliez , Mathieu Desbrun, Variational shape approximation, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 5: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 6: Christopher DeCoro , Szymon Rusinkiewicz, Pose-independent simplification of articulated meshes, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053430]
• 7: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 8: Michael Garland , Paul Heckbert, Quadric-based polygonal surface simplification, 1999
• 9: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 10: 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]
• 11: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 12: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• 13: Lawrence Ibarria , Jarek Rossignac, Dynapack: space-time compression of the 3D animations of triangle meshes with fixed connectivity, Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 26-27, 2003, San Diego, California
• 14: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 15: Scott Kircher , Michael Garland, Progressive multiresolution meshes for deforming surfaces, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073395]
• 16: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 17: Jerome Edward Lengyel, Compression of time-dependent geometry, Proceedings of the 1999 symposium on Interactive 3D graphics, p.89-95, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300533]
• 18: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 19: {MG03} Mohr A., Gleicher M.: Deformation sensitive decimation. Tech. rep., University of Wisconsin, 2003.
• 20: Ariel Shamir , Chandrajit Bajaj , Valerio Pascucci, Multi-resolution dynamic meshes with arbitrary deformations, Proceedings of the conference on Visualization '00, p.423-430, October 2000, Salt Lake City, Utah, United States
• 21: Ariel Shamir , Valerio Pascucci, Temporal and spatial level of details for dynamic meshes, Proceedings of the ACM symposium on Virtual reality software and technology, November 15-17, 2001, Baniff, Alberta, Canada [doi>10.1145/505008.505023]
• 22: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.65-70, July 1992
• 23: Julie C. Xia , Amitabh Varshney, Dynamic view-dependent simplification for polygonal models, Proceedings of the 7th conference on Visualization '96, p.327-ff., October 28-29, 1996, San Francisco, California, United States

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Design