Article

Progressive multiresolution meshes for deforming surfaces

Authors:

Michael GarlandAuthors Info & Claims

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

Pages 191 - 200

https://doi.org/10.1145/1073368.1073395

Published: 29 July 2005 Publication History

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]

{AL02} Ahn M., Lee S.: Mesh metamorphosis with topology transformations. In Proc. 10th Pacific Conference on Computer Graphics and Applications (2002), IEEE Computer Society, p. 481.

Digital Library

[2]

{ALS04} Ahn M., Lee S., Seidel H.-P.: Connectivity transformations for mesh metamorphosis. In Eurographics Symposium on Geometry Processing 2004 (2004). The Eurographics Association, pp. 77--83.

Digital Library

[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]

{BSM*03} Briceno H. M., Sander P. V., McMillan L., Gortler S., Hoppe H.: Geometry videos: a new representation for 3d animations. In Proc. 2003 ACM SIGGRAPH/Eurographics Symposium on Computer animation (2003). Eurographics Association, pp. 136--146.

Digital Library

[6]

{CH04} Carr N. A., Hart J. C.: Two algorithms for fast reclustering of dynamic meshed surfaces. In Eurographics Symposium on Geometry Processing 2004 (2004). The Eurographics Association. pp. 229--239.

Digital Library

[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]

{DR05} DeCoro C., Rusinkiewicz S.: Pose-independent simplification of articulated meshes. In Symposium on Interactive 3D Graphics (Apr. 2005).

Digital Library

[10]

{Gar99} Garland M.: Multiresolution modeling: Survey & future opportunities, 1999. In Eurographics '99 - State of the Art Reports, pages 111--131, 1999.

[11]

{GH97} Garland M., Heckbert P. S.: Surface simplification using quadric error metrics. In SIGGRAPH '97 (1997), ACM Press/Addison-Wesley Publishing Co., pp. 209--216.

Digital Library

[12]

{Hop96} Hoppe H.: Progressive meshes. In SIGGRAPH '96 (1996), ACM Press, pp. 99--108.

Digital Library

[13]

{Hop97} Hoppe H.: View-dependent refinement of progressive meshes. In SIGGRAPH '97 (1997), ACM Press/Addison-Wesley Publishing Co., pp. 189--198.

Digital Library

[14]

{Hop99} Hoppe H.: New quadric metric for simplifying meshes with appearance attributes. In Proc. 10th IEEE Visualization Conference (Washington, DC, USA, 1999), IEEE Computer Society.

Digital Library

[15]

{KK98a} Karypis G., Kumar V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 1 (1998), 359--392.

Digital Library

[16]

{KK98b} Karypis G., Kumar V.: Multilevel k-way partitioning scheme for irregular graphs. J. Parallel and Distributed Computing 48, 1 (1998), 96--129.

Digital Library

[17]

{KL70} Kernighan B. W., Lin S.: An efficient heuristic for partitioning graphs. Bell Systems Tech. J. 49 (Feb. 1970), 291--308.

[18]

{LDSS99} Lee A., Dobkin D., Sweldens W., Schröder P.: Multiresolution mesh morphing. In SIGGRAPH '99 (Aug. 1999), Computer Graphics Proceedings, Annual Conference Series, pp. 343--350.

Digital Library

[19]

{LE97} Luebke D., Erikson C.: View-dependent simplification of arbitrary polygonal environments. In SIGGRAPH '97 (1997), ACM Press/Addison-Wesley Publishing Co., pp. 199--208.

Digital Library

[20]

{LL05} Lin C.-H., Lee T.-Y.: Metamorphosis of 3d polyhedral models using progressive connectivity transformations. IEEE Transactions on Visualization and Computer Graphics 11, 1 (2005), 2--12.

Digital Library

[21]

{LRC*02} Luebke D., Reddy M., Cohen J. D., Varshney A., Watson B., Huebner R.: Level of Detail for 3-D Graphics. Morgan Kaufmann, 2002.

Digital Library

[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]

{SP01} Shamir A., Pascucci V.: Temporal and spatial level of details for dynamic meshes. In Proc. ACM symposium on Virtual reality software and technology (2001), ACM Press, pp. 77--84.

Digital Library

[24]

{SPB00} Shamir A., Pascucci V., Bajaj C.: Multiresolution dynamic meshes with arbitrary deformations. In Proc. Visualization '00 (2000), IEEE Computer Society Press, pp. 423--430.

Digital Library

[25]

{SWG*03} Sander P. V., Wood Z. J., Gortler S. J., Snyder J., Hoppe H.: Multi-chart geometry images. In Proc. Eurographics/ACM SIGGRAPH symposium on Geometry processing (2003), Eurographics Association, pp. 146--155.

Digital Library

[26]

{XV96} Xia J. C., Varshney A.: Dynamic view-dependent simplification for polygonal models. In Proc. 7th conference on Visualization (1996), IEEE Computer Society Press, pp. 327--ff.

Digital Library

Cited By

Zheng ZWang TFeng QPan ZGao XWu K(2024)Proxy Asset Generation for Cloth Simulation in GamesACM Transactions on Graphics10.1145/365817743:4(1-12)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658177
Yu JWang Z(2024)Super-Resolution Cloth Animation with Spatial and Temporal CoherenceACM Transactions on Graphics10.1145/365814343:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658143
Legrand HThiery JBoubekeur T(2019)Filtered Quadrics for High‐Speed Geometry Smoothing and ClusteringComputer Graphics Forum10.1111/cgf.1359738:1(663-677)Online publication date: 12-Feb-2019
https://doi.org/10.1111/cgf.13597
Show More Cited By

Progressive multiresolution meshes for deforming surfaces
1. Computing methodologies
  1. Computer graphics
2. Theory of computation

Recommendations

Edge flips and deforming surface meshes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

We study edge flips in a surface mesh and the maintenance of a deforming surface mesh. If the vertices are dense with respect to the local feature size and the triangles have angles at least a constant, we can flip edges in linear time such that all ...
Subdivision tree based multiresolution representation of arbitrary triangle meshes
Progressive compression of arbitrary triangular meshes
VIS '99: Proceedings of the conference on Visualization '99: celebrating ten years

In this paper we present a mesh compression method based on a multiresolution decomposition whose detail coefficients have a compact representation and thus smaller entropy than the original mesh. Given an arbitrary triangular mesh with an irregular ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation

July 2005

366 pages

ISBN:1595931988

DOI:10.1145/1073368

Conference Chairs:
Demetri Terzopoulos
New York University, USA
,
Victor Brian Zordan
University of California at Riverside, USA
,
Program Chairs:
Ken Anjyo
OLM Digital, Inc., Japan
,
Petros Faloutsos
University of California at Los Angeles, USA

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCA05

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA05: Symposium on Computer Animation

July 29 - 31, 2005

California, Los Angeles

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

61
Total Citations
View Citations
876
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)4

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zheng ZWang TFeng QPan ZGao XWu K(2024)Proxy Asset Generation for Cloth Simulation in GamesACM Transactions on Graphics10.1145/365817743:4(1-12)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658177
Yu JWang Z(2024)Super-Resolution Cloth Animation with Spatial and Temporal CoherenceACM Transactions on Graphics10.1145/365814343:4(1-14)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3658143
Legrand HThiery JBoubekeur T(2019)Filtered Quadrics for High‐Speed Geometry Smoothing and ClusteringComputer Graphics Forum10.1111/cgf.1359738:1(663-677)Online publication date: 12-Feb-2019
https://doi.org/10.1111/cgf.13597
Zang YYang BLiang FXiao X(2018)Novel Adaptive Laser Scanning Method for Point Clouds of Free-Form ObjectsSensors10.3390/s1807223918:7(2239)Online publication date: 11-Jul-2018
https://doi.org/10.3390/s18072239
Lyu LZhang JFan M(2018)An Efficiency Control Method Based on SFSM for Massive Crowd RenderingAdvances in Multimedia10.1155/2018/39583062018Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1155/2018/3958306
Thiery JGuy ÉBoubekeur TEisemann E(2016)Animated Mesh Approximation With Sphere-MeshesACM Transactions on Graphics10.1145/289835035:3(1-13)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2898350
Wang YLi GZeng ZHe H(2016)Articulated‐Motion‐Aware Sparse Localized DecompositionComputer Graphics Forum10.1111/cgf.1307636:8(247-259)Online publication date: 9-Dec-2016
https://doi.org/10.1111/cgf.13076
Ramos FHuerta JBenitez F(2016)Characterization of Multiresolution Models for Real-Time Rendering in GPU-Limited EnvironmentsArticulated Motion and Deformable Objects10.1007/978-3-319-41778-3_16(157-167)Online publication date: 2-Jul-2016
https://doi.org/10.1007/978-3-319-41778-3_16
Beacco APelechano NAndújar C(2015)A Survey of Real‐Time Crowd RenderingComputer Graphics Forum10.1111/cgf.1277435:8(32-50)Online publication date: 15-Oct-2015
https://doi.org/10.1111/cgf.12774
Fathy GHassan HSheta WBahgat R(2015)Efficient framework for mobile walkthrough applicationPervasive and Mobile Computing10.1016/j.pmcj.2014.08.00818:C(40-54)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1016/j.pmcj.2014.08.008
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten