“Variational shape approximation” by Cohen-Steiner, Alliez and Desbrun

  • ©David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun




    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 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.


    1. AGARWAL, P., AND SURI, S. 1998. Surface Approximation and Geometric Partitions. SIAM J. Comput. 19, 1016–1035.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    3. AMENTA, N., AND BERN, M. 1999. Surface Reconstruction by Voronoi Filtering. GEOMETRY: Discrete and Computational Geometry 22.]]Google Scholar
    4. ASPERT, N., SANTA-CRUZ, D., AND EBRAHIMI, T. 2002. MESH: Measuring Errors between Surfaces using the Hausdorff Distance. In IEEE Multimedia, 705–708.]]Google Scholar
    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.]] Google ScholarDigital Library
    6. BOISSONNAT, J. D., AND OUDOT, S. 2003. Provably good surface sampling and approximation. In Proc. of Symp. on Geo. Processing, 9–18.]] Google ScholarDigital Library
    7. BOROUCHAKI, H., AND FREY, P. 1998. Adaptive Triangular-Quadrilateral Mesh Generation. Intl. J. Numer. Methods Eng. 41, 915–934.]]Google ScholarCross Ref
    8. BOSSEN, F., AND HECKBERT, P. 1996. A Pliant Method for Anisotropic Mesh Generation. In 5th Intl. Meshing Roundtable, 63–76.]]Google Scholar
    9. BOTSCH, M., AND KOBBELT, L. 2001. Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing. In Eurographics, 402–410.]]Google Scholar
    10. COHEN, A., DAHMEN, W., DAUBECHIES, I., AND DEVORE, R. 2001. Tree Approximation and Optimal Encoding. Appl. Comput. Harmon. Anal. 11, 2, 192–226.]]Google ScholarCross Ref
    11. D’AZEVEDO, E., AND SIMPSON, B. 1991. On Optimal Triangular Meshes for Minimizing the Gradient Error. Numer. Math. 59, 321–348.]]Google ScholarDigital Library
    12. D’AZEVEDO, E. F. 2000. Are Bilinear Quadrilaterals Better Than Linear Triangles? SIAM Journal on Scientific Computing 22(1), 198–217.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    14. DU, Q., FABER, V., AND GUNZBURGER, M. 1999. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Review 41, 4, 637–676.]] Google ScholarDigital Library
    15. FU, J. H. G. 1993. Convergence of curvatures in secant approximations. Journal of Differential Geometry 37, 177–190.]]Google ScholarCross Ref
    16. GARLAND, M., AND HECKBERT, P. 1998. Simplifying Surfaces with Color and Texture using Quadric Error Metrics. In IEEE Visualization Proceedings, 263–269.]] Google ScholarDigital 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.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    19. GRAY, A., ED. 1998. Modern Differential Geometry of Curves and Surfaces. Second edition. CRC Press.]] Google ScholarDigital Library
    20. GRINSPUN, E., AND SCHRÖDER, P. 2001. Normal Bounds for Subdivision-Surface Interference Detection. In IEEE Visualization ’01, 333–340.]] Google ScholarDigital Library
    21. GUSKOV, I., VIDIMCE, K., SWEDLDENS, W., AND SCHRÖDER, P. 2000. Normal Meshes. In Proceedings of ACM SIGGRAPH, 95–102.]] Google ScholarDigital Library
    22. HAUSNER, A. 2001. Simulating Decorative Mosaics. In Proceedings of ACM SIGGRAPH, 573–578.]] Google ScholarDigital 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.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    25. HERTZMANN, A., AND ZORIN, D. 2000. Illustrating Smooth Surfaces. In ACM SIGGRAPH Proceedings, 517–526.]] Google ScholarDigital Library
    26. HOPPE, H., DEROSE, T., DUCHAMP, T., MCDONALD, J., AND STUETZLE, W. 1993. Mesh Optimization. In ACM SIGGRAPH Proceedings, 19–26.]] Google ScholarDigital Library
    27. HOPPE, H. 1996. Progressive Meshes. In ACM SIGGRAPH Proceedings, 99–108.]] Google ScholarDigital 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.]]Google Scholar
    29. INTERRANTE, V., FUCHS, H., AND PIZER, S. 1996. Illustrating Transparent Surfaces with Curvature-Directed Strokes. In IEEE Visualization Proceedings, 211–218.]] Google ScholarDigital 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.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    32. KATZ, S., AND TAL, A. 2003. Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts. ACM Trans. on Graphics 22, 3, 954–961.]] Google ScholarDigital Library
    33. KHO, Y., AND GARLAND, M. 2003. User-Guided Simplification. In Proceedings of ACM Symp. on 13D, 123–126.]] Google ScholarDigital Library
    34. KING, D., AND ROSSIGNAC, J. 1999. Optimal Bit Allocation in Compressed 3D Models. Comput. Geo. Theory & Appl. 14, 1-3, 99–118.]] Google ScholarDigital Library
    35. KLEIN, R., LIEBICH, G., AND STRASSER, W. 1996. Mesh Reduction with Error Control. In IEEE Visualization Proceedings, 311–318.]] Google ScholarDigital 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.]]Google ScholarCross Ref
    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.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    39. LINDSTROM, P., AND TURK, G. 1998. Fast and Memory Efficient Polygonal Simplification. In IEEE Visualization Proceedings, 279–286.]] Google ScholarDigital Library
    40. LINDSTROM, P., AND TURK, G. 2000. Image-driven simplification. ACM Transactions on Graphics 19, 3 (July), 204–241.]] Google ScholarDigital Library
    41. LLOYD, S. 1982. Least square quantization in PCM. IEEE Trans. Inform. Theory 28, 129–137.]]Google ScholarDigital Library
    42. MAILLOT, J., YAHIA, H., AND VERROUST, A. 1993. Interactive Texture Mapping. In ACM SIGGRAPH Proceedings, 27–34.]] Google ScholarDigital 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.]]Google Scholar
    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.]] Google ScholarDigital 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.]]Google ScholarCross Ref
    46. OSHER, S., AND FEDKIW, R., Eds. 2002. Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematics Sciences 153. Springer-Verlag.]]Google Scholar
    47. PAULY, M., GROSS, M., AND KOBBELT, L. P. 2002. Efficient Simplification of Point-Sampled Surfaces. In Proc. of IEEE Visualization, 163–170.]] Google ScholarDigital Library
    48. PEBAY, P. 2002. Planar Quadrangle Quality Measures: Is There Really A Choice? In 11th Intl. Meshing Roundtable, 53–62.]]Google Scholar
    49. RÖSSL, C., AND KOBBELT, L. 2000. Line-art Rendering of 3D Models. In Proceedings of Pacific Graphics, 87–96.]] Google ScholarDigital Library
    50. SANDER, P. V., SNYDER, J., GORTLER, S. J., AND HOPPE, H. 2001. Texture Mapping Progressive Meshes. In ACM SIGGRAPH Proceedings, 409–416.]] Google ScholarDigital 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.]] Google ScholarDigital Library
    52. SHEFFER, A. 2001. Model Simplification for Meshing Using Face Clustering. Computer Aided Design 33, 925–934.]]Google ScholarCross Ref
    53. SHEWCHUK, J. R., 2002. What Is a Good Linear Finite Element? Interpolation, Conditioning, Anisotropy, and Quality Measures. Preprint.]]Google Scholar
    54. SHLAFMAN, S., TAL, A., AND KATZ, S. 2002. Metamorphosis of polyhedral surfaces using decomposition. Eurographics Proceedings (CFG) 22, 3 (Sept.), 219–228.]]Google Scholar
    55. SIMPSON, R. B. 1994. Anisotropic Mesh Transformation and Optimal Error Control. Appl. Num. Math. 14(1-3), 183–198.]] Google ScholarDigital 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.]] Google ScholarDigital 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.]]Google Scholar
    58. TURK, G. 1992. Re-Tiling Polygonal Surfaces. In ACM SIGGRAPH Proceedings, 55–64.]] Google ScholarDigital Library
    59. VÁRADY, T., MARTIN, R. R.,. AND COX, J. 1997. Reverse Engineering of Geometric Models – An Introduction. CAD 29, 4, 255–268.]]Google ScholarCross Ref
    60. WOOD, Z., HOPPE, H., DESBRUN, M., AND SCHRÖDER, P. 2004. Removing Excess Topology in Isosurfaces, ACM Trans. on Graphics 23, 2 (Apr.).]] Google ScholarDigital Library

ACM Digital Library Publication: