Article

Variational shape approximation

Authors:

David Cohen-Steiner,

Mathieu DesbrunAuthors Info & Claims

SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

Pages 905 - 914

https://doi.org/10.1145/1186562.1015817

Published: 01 August 2004 Publication History

Abstract

A method for concise, faithful approximation of complex 3D datasets is key to reducing the computational cost of graphics applications. Despite numerous applications ranging from geometry compression to reverse engineering, efficiently capturing the geometry of a surface remains a tedious task. In this paper, we present both theoretical and practical contributions that result in a novel and versatile framework for geometric approximation of surfaces. We depart from the usual strategy by casting shape approximation as a variational geometric partitioning problem. Using the concept of geometric proxies, we drive the distortion error down through repeated clustering of faces into best-fitting regions. Our approach is entirely discrete and error-driven, and does not require parameterization or local estimations of differential quantities. We also introduce a new metric based on normal deviation, and demonstrate its superior behavior at capturing anisotropy.

Supplementary Material

MOV File (pps080.mov)

Download
11.78 KB

References

[1]

AGARWAL, P., AND SURI, S. 1998. Surface Approximation and Geometric Partitions. SIAM J. Comput. 19, 1016--1035.]]

Digital Library

[2]

ALLIEZ, P., COHEN-STEINER, D., DEVILLERS, O., LÉVY, B., AND DESBRUN, M. 2003. Anisotropic Polygonal Remeshing. ACM Trans. on Graphics 22, 3, 485--493.]]

Digital Library

[3]

AMENTA, N., AND BERN, M. 1999. Surface Reconstruction by Voronoi Filtering. GEOMETRY: Discrete and Computational Geometry 22.]]

[4]

ASPERT, N., SANTA-CRUZ, D., AND EBRAHIMI, T. 2002. MESH: Measuring Errors between Surfaces using the Hausdorff Distance. In IEEE Multimedia, 705--708.]]

[5]

BALMELLI, L., VETTERLI, M., AND LIEBLING, T. M. 2002. Mesh Optimization Using Global Error with Application to Geometry Simplification. Graphical Models 64, 3--4 (May), 230--257.]]

Digital Library

[6]

BOISSONNAT, J. D., AND OUDOT, S. 2003. Provably good surface sampling and approximation. In Proc. of Symp. on Geo. Processing, 9--18.]]

Digital Library

[7]

BOROUCHAKI, H., AND FREY, P. 1998. Adaptive Triangular-Quadrilateral Mesh Generation. Intl. J. Numer. Methods Eng. 41, 915--934.]]

[8]

BOSSEN, F., AND HECKBERT, P. 1996. A Pliant Method for Anisotropic Mesh Generation. In 5th Intl. Meshing Roundtable, 63--76.]]

[9]

BOTSCH, M., AND KOBBELT, L. 2001. Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing. In Eurographics, 402--410.]]

[10]

COHEN, A., DAHMEN, W., DAUBECHIES, I., AND DEVORE, R. 2001. Tree Approximation and Optimal Encoding. Appl. Comput. Harmon. Anal. 11, 2, 192--226.]]

[11]

D'AZEVEDO, E., AND SIMPSON, B. 1991. On Optimal Triangular Meshes for Minimizing the Gradient Error. Numer. Math. 59, 321--348.]]

Digital Library

[12]

D'AZEVEDO, E. F. 2000. Are Bilinear Quadrilaterals Better Than Linear Triangles? SIAM Journal on Scientific Computing 22(1), 198--217.]]

Digital Library

[13]

DÉCORET, X., DURAND, F., SILLION, F., AND DORSEY, J. 2003. Billboard Clouds for Extreme Model Simplification. ACM Trans. on Graphics 22, 3, 689--696.]]

Digital Library

[14]

DU, Q., FABER, V., AND GUNZBURGER, M. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Review 41, 4, 637--676.]]

Digital Library

[15]

FU, J. H. G. 1993. Convergence of curvatures in secant approximations. Journal of Differential Geometry 37, 177--190.]]

[16]

GARLAND, M., AND HECKBERT, P. 1998. Simplifying Surfaces with Color and Texture using Quadric Error Metrics. In IEEE Visualization Proceedings, 263--269.]]

Digital Library

[17]

GARLAND, M., WILLMOTT, A., AND HECKBERT, P. 2001. Hierarchical Face Clustering on Polygonal Surfaces. In ACM Symp. on Interactive 3D Graphics, 49--58.]]

Digital Library

[18]

GIRSHICK, A., INTERRANTE, V., HAKER, S., AND LEMOINE, T. 2000. Line Direction Matters: Argument for the Use of Principal Directions in 3D Line Drawings. In Int. Symp. on Non-Photoreal. Anim. and Rend., 43--52.]]

Digital Library

[19]

GRAY, A., ED. 1998. Modern Differential Geometry of Curves and Surfaces. Second edition. CRC Press.]]

Digital Library

[20]

GRINSPUN, E., AND SCHRÖDER, P. 2001. Normal Bounds for Subdivision-Surface Interference Detection. In IEEE Visualization '01, 333--340.]]

Digital Library

[21]

GUSKOV, I., VIDIMCE, K., SWEDLDENS, W., AND SCHRÖDER, P. 2000. Normal Meshes. In Proceedings of ACM SIGGRAPH, 95--102.]]

Digital Library

[22]

HAUSNER, A. 2001. Simulating Decorative Mosaics. In Proceedings of ACM SIGGRAPH, 573--578.]]

Digital Library

[23]

HECKBERT, P., AND GARLAND, M. 1999. Optimal Triangulation and Quadric-Based Surface Simplification. Journal of Comp. Geo.: Theory and Applications 14(1-3), 49--65.]]

Digital Library

[24]

HECKEL, B., UVA, A. E., HAMANN, B., AND JOY, K. I. 2001. Surface Reconstruction Using Adaptive Clustering Methods. In Geometric Modelling: Dagstuhl 1999, vol. 14, 199--218.]]

Digital Library

[25]

HERTZMANN, A., AND ZORIN, D. 2000. Illustrating Smooth Surfaces. In ACM SIGGRAPH Proceedings, 517--526.]]

Digital Library

[26]

HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, J., AND STUETZLE, W. 1993. Mesh Optimization. In ACM SIGGRAPH Proceedings, 19--26.]]

Digital Library

[27]

HOPPE, H. 1996. Progressive Meshes. In ACM SIGGRAPH Proceedings, 99--108.]]

Digital Library

[28]

INOUE, K., ITOH, T., YAMADA, A., FURUHATA, T., AND SHIMADA, K. 1999. Clustering Large Number Of Faces For 2-Dimensional Mesh Generation. In 8th Int. Meshing Roundtable, 281--292.]]

[29]

INTERRANTE, V., FUCHS, H., AND PIZER, S. 1996. Illustrating Transparent Surfaces with Curvature-Directed Strokes. In IEEE Visualization Proceedings, 211--218.]]

Digital Library

[30]

KALVIN, A. D., AND TAYLOR, R. H. 1996. Superfaces: Polygonal mesh simplification with bounded error. IEEE Comp. Graphics and App. 16, 3 (May), 64--77.]]

Digital Library

[31]

KANUNGO, T., MOUNT, D. M., NETANYAHU, N. S., PIATKO, C. D., SILVERMAN, R., AND WU, A. Y. 2002. A local search approximation algorithm for k-means clustering. In Proceedings of the Symp. on Computational Geometry, 10--18.]]

Digital Library

[32]

KATZ, S., AND TAL, A. 2003. Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts. ACM Trans. on Graphics 22, 3, 954--961.]]

Digital Library

[33]

KHO, Y., AND GARLAND, M. 2003. User-Guided Simplification. In Proceedings of ACM Symp. on 13D, 123--126.]]

Digital Library

[34]

KING, D., AND ROSSIGNAC, J. 1999. Optimal Bit Allocation in Compressed 3D Models. Comput. Geo. Theory & Appl. 14, 1-3, 99--118.]]

Digital Library

[35]

KLEIN, R., LIEBICH, G., AND STRASSER, W. 1996. Mesh Reduction with Error Control. In IEEE Visualization Proceedings, 311--318.]]

Digital Library

[36]

KOBBELT, L., VORSATZ, J., LABSIK, U., AND SEIDEL, H.-P. 1999. A Shrink Wrapping Approach to Remeshing Polygonal Surfaces. Eurographics Proceedings (CGF) 18, 119--130.]]

[37]

LEE, A., SWELDENS, W., SCHRÖDER, P., COWSAR, L., AND DOBKIN, D. 1998. MAPS: Multiresolution Adaptive Parameterization of Surfaces. In ACM SIGGRAPH Proceedings, 95--104.]]

Digital Library

[38]

LÉVY, B., PETITJEAN, S., RAY, N., AND MAILLOT, J. 2002. Least Squares Conformal Maps for Automatic Texture Atlas Generation. In ACM SIGGRAPH Proceedings, 362--371.]]

Digital Library

[39]

LINDSTROM, P., AND TURK, G. 1998. Fast and Memory Efficient Polygonal Simplification. In IEEE Visualization Proceedings, 279--286.]]

Digital Library

[40]

LINDSTROM, P., AND TURK, G. 2000. Image-driven simplification. ACM Transactions on Graphics 19, 3 (July), 204--241.]]

Digital Library

[41]

LLOYD, S. 1982. Least square quantization in PCM. IEEE Trans. Inform. Theory 28, 129--137.]]

Digital Library

[42]

MAILLOT, J., YAHIA, H., AND VERROUST, A. 1993. Interactive Texture Mapping. In ACM SIGGRAPH Proceedings, 27--34.]]

Digital Library

[43]

NADLER, E. 1986. Piecewise-Linear Best £2 Approximation On Triangulations. In Approximation Theory V, C. K. Chui, L. L. Schumaker, and J. D. Ward, Eds. Academic Press, 499--502.]]

[44]

OHTAKE, Y., BELYAEV, A., ALEXA, M., TURK, G., AND SEIDEL, H.-P. 2003. Multi-level Partition of Unity Implicits. ACM Trans. on Graphics 22, 3, 463--470.]]

Digital Library

[45]

OHTAKE, Y., BELYAEV, A., AND PASKO, A. 2003. Dynamic Mesh Optimization for Implicit Surfaces with Sharp Features. Visual Computer 19(2), 115--126.]]

[46]

OSHER, S., AND FEDKIW, R., Eds. 2002. Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematics Sciences 153. Springer-Verlag.]]

[47]

PAULY, M., GROSS, M., AND KOBBELT, L. P. 2002. Efficient Simplification of Point-Sampled Surfaces. In Proc. of IEEE Visualization, 163--170.]]

Digital Library

[48]

PEBAY, P. 2002. Planar Quadrangle Quality Measures: Is There Really A Choice? In 11th Intl. Meshing Roundtable, 53--62.]]

[49]

RÖSSL, C., AND KOBBELT, L. 2000. Line-art Rendering of 3D Models. In Proceedings of Pacific Graphics, 87--96.]]

Digital Library

[50]

SANDER, P. V., SNYDER, J., GORTLER, S. J., AND HOPPE, H. 2001. Texture Mapping Progressive Meshes. In ACM SIGGRAPH Proceedings, 409--416.]]

Digital Library

[51]

SANDER, P., WOOD, Z. J., GORTLER, S., SNYDER, J., AND HOPPE, H. H. 2003. Multi-chart Geometry Images. In Proc. of Symp. on Geo. Processing, 146--155.]]

Digital Library

[52]

SHEFFER, A. 2001. Model Simplification for Meshing Using Face Clustering. Computer Aided Design 33, 925--934.]]

[53]

SHEWCHUK, J. R., 2002. What Is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures. Preprint.]]

[54]

SHLAFMAN, S., TAL, A., AND KATZ, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. Eurographics Proceedings (CFG) 22, 3 (Sept.), 219--228.]]

[55]

SIMPSON, R. B. 1994. Anisotropic Mesh Transformation and Optimal Error Control. Appl. Num. Math. 14(1-3), 183--198.]]

Digital Library

[56]

SORKINE, O., COHEN-OR, D., AND TOLEDO, S. 2003. High-pass Quantization for Mesh Encoding. In Proc. of Symp. on Geo. Processing, 42--51.]]

Digital Library

[57]

SURAZHSKY, V., ALLIEZ, P., AND GOTSMAN, C. 2003. Isotropic Remeshing of Surfaces: a Local Parameterization Approach. In Proceedings of 12th International Meshing Roundtable, 215--224.]]

[58]

TURK, G. 1992. Re-Tiling Polygonal Surfaces. In ACM SIGGRAPH Proceedings, 55--64.]]

Digital Library

[59]

VÁRADY, T., MARTIN, R. R.,. AND COX, J. 1997. Reverse Engineering of Geometric Models - An Introduction. CAD 29, 4, 255--268.]]

[60]

WOOD, Z., HOPPE, H., DESBRUN, M., AND SCHRÖDER, P. 2004. Removing Excess Topology in Isosurfaces, ACM Trans. on Graphics 23, 2 (Apr.).]]

Digital Library

Cited By

Li PGuo JLi HBenes BYan D(2024)SfmCAD: Unsupervised CAD Reconstruction by Learning Sketch-based Feature Modeling Operations2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00447(4671-4680)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00447
Zhang HFan QZhang ZBao BSong YHu CZhang C(2024)Study on blade zoning measurement point planning methodMeasurement10.1016/j.measurement.2024.114670232(114670)Online publication date: Jun-2024
https://doi.org/10.1016/j.measurement.2024.114670
Chen ZShi YNan LXiong ZZhu X(2024)PolyGNN: Polyhedron-based graph neural network for 3D building reconstruction from point cloudsISPRS Journal of Photogrammetry and Remote Sensing10.1016/j.isprsjprs.2024.09.031218(693-706)Online publication date: Dec-2024
https://doi.org/10.1016/j.isprsjprs.2024.09.031
Show More Cited By

Recommendations

Variational shape approximation

A method for concise, faithful approximation of complex 3D datasets is key to reducing the computational cost of graphics applications. Despite numerous applications ranging from geometry compression to reverse engineering, efficiently capturing the ...
Geometry Synthesis on Surfaces Using Field-Guided Shape Grammars

We show how to model geometric patterns on surfaces. We build on the concept of shape grammars to allow the grammars to be guided by a vector or tensor field. Our approach affords greater artistic freedom in design and enables the use of grammars to ...
An Extremum Principle for Shape from Contour

An extremum principle is developed that determines three-dimensional surface orientation from a two-dimensional contour. The principle maximizes the ratio of the area to the square of the perimeter, a measure of the compactness or symmetry of the three-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '04: ACM SIGGRAPH 2004 Papers

August 2004

684 pages

ISBN:9781450378239

DOI:10.1145/1186562

Editor:
Joe Marks
Mitsubishi Electric Research Laboratories (MERL)

Copyright © 2004 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGGRAPH04

Sponsor:

SIGGRAPH

SIGGRAPH04: Special Interest Group on Computer Graphics and Interactive Techniques

August 8 - 12, 2004

California, Los Angeles

Acceptance Rates

SIGGRAPH '04 Paper Acceptance Rate 83 of 478 submissions, 17%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

153
Total Citations
View Citations
5,276
Total Downloads

Downloads (Last 12 months)110
Downloads (Last 6 weeks)15

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li PGuo JLi HBenes BYan D(2024)SfmCAD: Unsupervised CAD Reconstruction by Learning Sketch-based Feature Modeling Operations2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.00447(4671-4680)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.00447
Zhang HFan QZhang ZBao BSong YHu CZhang C(2024)Study on blade zoning measurement point planning methodMeasurement10.1016/j.measurement.2024.114670232(114670)Online publication date: Jun-2024
https://doi.org/10.1016/j.measurement.2024.114670
Chen ZShi YNan LXiong ZZhu X(2024)PolyGNN: Polyhedron-based graph neural network for 3D building reconstruction from point cloudsISPRS Journal of Photogrammetry and Remote Sensing10.1016/j.isprsjprs.2024.09.031218(693-706)Online publication date: Dec-2024
https://doi.org/10.1016/j.isprsjprs.2024.09.031
He KRoerdink JKosinka J(2024)Image vectorization using a sparse patch layoutGraphical Models10.1016/j.gmod.2024.101229135(101229)Online publication date: Oct-2024
https://doi.org/10.1016/j.gmod.2024.101229
Dai JWang YYan D(2024)Feature-preserving Shrink Wrapping with Adaptive AlphaComputer Aided Geometric Design10.1016/j.cagd.2024.102321(102321)Online publication date: Apr-2024
https://doi.org/10.1016/j.cagd.2024.102321
He XLv CHuang PHuang H(2024)WindPoly: Polygonal Mesh Reconstruction via Winding NumbersComputer Vision – ECCV 202410.1007/978-3-031-72970-6_17(294-311)Online publication date: 23-Nov-2024
https://doi.org/10.1007/978-3-031-72970-6_17
Xiong WZhang HPeng BHu ZWu YGuo JHuang H(2023)TwinTex: Geometry-Aware Texture Generation for Abstracted 3D Architectural ModelsACM Transactions on Graphics10.1145/361832842:6(1-14)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618328
Cárdenas JOgayar CFeito FJurado J(2023)Modeling of the 3D Tree Skeleton Using Real-World Data: A SurveyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.319301829:12(4920-4935)Online publication date: Dec-2023
https://doi.org/10.1109/TVCG.2022.3193018
Yan LLi YDai JXie H(2023)UBMDP: Urban Building Mesh Decoupling and PolygonizationIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2023.328859061(1-16)Online publication date: 2023
https://doi.org/10.1109/TGRS.2023.3288590
Do VPham Q(2023)Geometry-Aware Coverage Path Planning for Depowdering on Complex 3D SurfacesIEEE Robotics and Automation Letters10.1109/LRA.2023.32969438:9(5552-5559)Online publication date: Sep-2023
https://doi.org/10.1109/LRA.2023.3296943
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.

Media

Figures

Other

Tables

View Table of Contents