Mesh clustering by approximating centroidal Voronoi tessellation

ABSTRACT

An elegant and efficient mesh clustering algorithm is presented. The faces of a polygonal mesh are divided into different clusters for mesh coarsening purpose by approximating the Centroidal Voronoi Tessellation of the mesh. The mesh coarsening process after clustering can be done in an isotropic or anisotropic fashion. The presented algorithm improves previous techniques in local geometric operations and parallel updates. The new algorithm is very simple but is guaranteed to converge, and generates better approximating meshes with the same computation cost. Moreover, the new algorithm is suitable for the variational shape approximation problem with L^{2, 1} distortion error metric and the convergence is guaranteed. Examples demonstrating efficiency of the new algorithm are also included in the paper.

REFERENCES

• 1: D. Cohen-Steiner, P. Alliez, and M. Desbrun. Variational shape approximation. ACM Transactions on Graphics. Special issue for SIGGRAPH conference, pages 905--914, 2004.
• 2: Q. Du, V. Faber, and M. Gunzburger. Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev., 41(4):637--676, 1999.
• 3: Q. Du, M. D. Gunzburger, and L. Ju. Constrained centroidal voronoi tessellations for surfaces. SIAM J. Sci. Comput., 24(5):1488--1506, 2002.
• 4: P. Frey and H. Borouchaki. Surface mesh evaluation. In 16th International Meshing Roundtable, pages 363--374, 1997.
• 5: I. Guskov, K. Vidimče, W. Sweldens, and P. Schröder. Normal meshes. In SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, pages 95--102, New York, NY, USA, 2000. ACM Press/Addison-Wesley Publishing Co.
• 6: H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. Mesh optimization. In ACM SIGGRAPH Proceedings, pages 19--26, 1993.
• 7: J. C. H. Jesse D. Hall. Gpu acceleration of iterative clustering. The ACM Workshop on General Purpose Computing on Graphics Processors, and SIGGRAPH 2004 poster, Aug. 2004.
• 8: A. Kalvin and R. Taylor. Superfaces: Polygonal mesh simplification with bounded error. IEEE Comput. Graph. Appl., 16(3):64--77, 1996.
• 9: L. Kobbelt, J. Vorsatz, U. Labsik, and H.-P. Seidel. A shrink wrapping approach to remeshing polygonal surfaces. 18(3):119--130, 1999. (Proceedings of EUROGRAPHICS'99).
• 10: J. B. Lasserre and K. E. Avrachenkov. The multi-dimensional version of ∫_a^bx^pdx. The American Mathematical Monthly, 108(2):151--154, 2001.
• 11: B. Lévy, S. Petitjean, N. Ray, and J. Maillot. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph., 21(3):362--371, 2002.
• 12: A. W. M. Garland and P. S. Heckbert. Hierarchical face clustering on polygonal surfaces. In Proceedings of the Symposium on Interactive 3D Graphics, 2001.
• 13: A. Okabe, B. Boots, and K. Sugihara. Spatial Tessellations Concepts and Applications of Voronoi Diagrams. John Wiley & Son, 1992.
• 14: A. Sheffer. Model simplification for meshing using face clustering. Comptuer-Aided Design, 33:925--934, 2001.
• 15: S. Valette and J.-M. Chassery. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening. 23(3):381--389, 2004. (Proc. Eurographics'04).
• 16: S. Valette, J.-M. Chassery, and R. Prost. Generic remeshing of 3d triangular meshes with metric-dependent discrete voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics, 10(2):369--381, 2008.
• 17: S. Valette, I. Kompatsiaris, and J.-M. Chassery. Adaptive polygonal mesh simplification with discrete centroidal voronoi diagrams. In Proceedings of 2nd International Conference on Machine Intelligence ICMI 2005, pages 655--662, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Physically based modeling

Keywords:
centroidal Voronoi tessellation, mesh clustering, shape approximation