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

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