3D Mesh Coarsening via Uniform Clustering

Authors: Shuhua Lai, Kairui Chen

Abstract:

In this paper, we present a fast and efficient mesh coarsening algorithm for 3D triangular meshes. Theis approach can be applied to very complex 3D meshes of arbitrary topology and with millions of vertices. The algorithm is based on the clustering of the input mesh elements, which divides the faces of an input mesh into a given number of clusters for clustering purpose by approximating the Centroidal Voronoi Tessellation of the input mesh. Once a clustering is achieved, it provides us an efficient way to construct uniform tessellations, and therefore leads to good coarsening of polygonal meshes. With proliferation of 3D scanners, this coarsening algorithm is particularly useful for reverse engineering applications of 3D models, which in many cases are dense, non-uniform, irregular and arbitrary topology. Examples demonstrating effectiveness of the new algorithm are also included in the paper.

Keywords: Coarsening, mesh clustering, shape approximation, mesh simplification.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1124609

References:

[1] Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Levy, and Mathieu Desbrun. Anisotropic polygonal remeshing. ACM.Transactions on Graphics, 22:485493, 2003.
[2] Pierre Alliez, Eric Colin de Verdiere, Olivier Devillers, and Martin Isenburg. Isotropic surface remeshing. In M.S. Kim, editor, SMI03: Proceedings of Shape Modeling International 2003, pages 4958, Los Alamitos, 2003. IEEE Computer Society.
[3] P. Alliez, M. Meyer, and M. Desbrun. Interactive geometry remeshing. Acm Transactions on Graphics, 21(3):347354, 2002.
[4] Mario Botsch and Leif Kobbelt. A remeshing approach to multiresolution modeling. In R. Scopigno and D. Zorin, editors, Proceedings of 2nd Eurographics Symposium on Geometry Processing, pages 189196. Eurographics, 2004.
[5] V. Kraevoy and A. Sheffer. Cross-parameterization and compatible remeshing of 3d models. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, 2004.
[6] L. Kobbelt, J. Vorsatz, U. Labsik, and H.P. Seidel. A shrink wrapping approach to remeshing polygonal surfaces. Computer Graphics Forum, 18:119130, 1999.
[7] Emil Praun and Hugues Hoppe. Spherical parametrization and remeshing. Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings, pages 340349, 2003.
[8] F. Fan, S. Lai, J.Wang, C. Huang, Y. Li, Mesh Clustering by Approximating Centroidal Voronoi Tessellation. Proc. 2009 SIAM/ACM Joint Conference on Geometric & Physical Modeling, 2009, pp. 301-306.
[9] Q. Du, V. Faber, and M. Gunzburger. Centroidal voronoi tessellations: Applications and algorithms. SIAM Rev., 41(4):637676, 1999.
[10] Q. Du, M. D. Gunzburger, and L. Ju. Constrained centroidal voronoi tessellations for surfaces. SIAM J. Sci. Comput., 24(5):14881506, 2002.
[11] A. W. M. Garland and P. S. Heckberty. Hierarchical face clustering on polygonal surfaces. In Proceedings of the Symposium on Interactive 3D Graphics, 2001.
[12] S. Valette and J.-M. Chassery. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening. 23(3):381389, 2004. (Proc. Eurographics04).
[13] 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):369381, 2008.