Progressive multiresolution meshes for deforming surfaces

ABSTRACT

Time-varying surfaces are ubiquitous in movies, games, and scientific applications. For reasons of efficiency and simplicity of formulation, these surfaces are often generated and represented as dense polygonal meshes with static connectivity. As a result, such deforming meshes often have a tremendous surplus of detail, with many more vertices and polygons than necessary for any given frame. An extensive amount of work has addressed the issue of simplifying a static mesh: however, these methods are inadequate for time-varying surfaces when there is a high degree of non-rigid deformation. We thus propose a new multiresolution representation for deforming surfaces that, together with our dynamic improvement scheme, provides high quality surface approximations at any level-of-detail, for all frames of an animation. Our algorithm also gives rise to a new progressive representation for time-varying multiresolution hierarchies, consisting of a base hierarchy for the initial frame and a sequence of update operations for subsequent frames. We demonstrate that this provides a very effective means of extracting static or view-dependent approximations for a deforming mesh over all frames of an animation.

REFERENCES

• 1: Minsu Ahn , Seungyong Lee, Mesh Metamorphosis with Topology Transformations, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.481, October 09-11, 2002
• 2: Minsu Ahn , Seungyong Lee , Hans-Peter Seidel, Connectivity transformation for mesh metamorphosis, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057443]
• 3: {AM00} Alexa M., Muller W.: Representing animations by principal components. In Eurographics (2000), The Eurographics Association/Blackwell Publishers.
• 4: {ASCE02} Aspert N., Santa-Cruz D., Ebrahimi T.: Mesh: Measuring errors between surfaces using the hausdorff distance. In Proc. IEEE International Conference on Multimedia and Expo (2002), vol. I, pp. 705 -- 708. http://mesh.berlios.de/.
• 5: 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
• 6: Nathan A. Carr , John C. Hart, Two algorithms for fast reclustering of dynamic meshed surfaces, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France [doi>10.1145/1057432.1057462]
• 7: {CRS98} Cignoni P., Rocchini C., Scopigno R.: Metro: Measuring error on simplified surfaces. Computer Graphics Forum 17, 2 (1998), 167--174.
• 8: {DEGN98} Dey T., Edelsbrunner H., Guha S., Nekhayev D.: Topology preserving edge contraction, 1998. Technical Report RGI-Tech-98-018, Raindrop Geomagic Inc., Research Triangle Park, North Carolina.
• 9: 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]
• 10: {Gar99} Garland M.: Multiresolution modeling: Survey & future opportunities, 1999. In Eurographics '99 - State of the Art Reports, pages 111--131, 1999.
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Hugues Hoppe, New quadric metric for simplifying meshes with appearance attributes, Proceedings of the 10th IEEE Visualization 1999 Conference (VIS '99), October 25-28, 1999
• 15: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 16: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 17: {KL70} Kernighan B. W., Lin S.: An efficient heuristic for partitioning graphs. Bell Systems Tech. J. 49 (Feb. 1970), 291--308.
• 18: Aaron W. F. Lee , David Dobkin , Wim Sweldens , Peter Schröder, Multiresolution mesh morphing, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.343-350, July 1999 [doi>10.1145/311535.311586]
• 19: 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]
• 20: Chao-Hung Lin , Tong-Yee Lee, Metamorphosis of 3D Polyhedral Models Using Progressive Connectivity Transformations, IEEE Transactions on Visualization and Computer Graphics, v.11 n.1, p.2-12, January 2005 [doi>10.1109/TVCG.2005.12]
• 21: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 22: {MG03} Mohr A., Gleicher M.: Deformation Sensitive Decimation. Tech. rep., University of Wisconsin Graphics Group, 2003. http://www.cs.wisc.edu/graphics/Gallery/DSD/.
• 23: 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]
• 24: 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
• 25: P. V. Sander , Z. J. Wood , S. J. Gortler , J. Snyder , H. Hoppe, Multi-chart geometry images, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 26: 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