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., {"references":["Pierre Alliez, David Cohen-Steiner, Olivier Devillers, Bruno Levy, and\nMathieu Desbrun. Anisotropic polygonal remeshing. ACM.Transactions\non Graphics, 22:485493, 2003.","Pierre Alliez, Eric Colin de Verdiere, Olivier Devillers, and Martin\nIsenburg. Isotropic surface remeshing. In M.S. Kim, editor, SMI03:\nProceedings of Shape Modeling International 2003, pages 4958, Los\nAlamitos, 2003. IEEE Computer Society.","P. Alliez, M. Meyer, and M. Desbrun. Interactive geometry remeshing.\nAcm Transactions on Graphics, 21(3):347354, 2002.","Mario Botsch and Leif Kobbelt. A remeshing approach to\nmultiresolution modeling. In R. Scopigno and D. Zorin, editors,\nProceedings of 2nd Eurographics Symposium on Geometry Processing,\npages 189196. Eurographics, 2004.","V. Kraevoy and A. Sheffer. Cross-parameterization and compatible\nremeshing of 3d models. Computer graphics proceedings, annual\nconference series: SIGGRAPH conference proceedings, 2004.","L. Kobbelt, J. Vorsatz, U. Labsik, and H.P. Seidel. A shrink wrapping\napproach to remeshing polygonal surfaces. Computer Graphics Forum,\n18:119130, 1999.","Emil Praun and Hugues Hoppe. Spherical parametrization and\nremeshing. Computer graphics proceedings, annual conference series:\nSIGGRAPH conference proceedings, pages 340349, 2003.","F. Fan, S. Lai, J.Wang, C. Huang, Y. Li, Mesh Clustering by\nApproximating Centroidal Voronoi Tessellation. Proc. 2009 SIAM/ACM\nJoint Conference on Geometric & Physical Modeling, 2009, pp.\n301-306.","Q. Du, V. Faber, and M. Gunzburger. Centroidal voronoi tessellations:\nApplications and algorithms. SIAM Rev., 41(4):637676, 1999.\n[10] Q. Du, M. D. Gunzburger, and L. Ju. Constrained centroidal voronoi\ntessellations for surfaces. SIAM J. Sci. Comput., 24(5):14881506, 2002.\n[11] A. W. M. Garland and P. S. Heckberty. Hierarchical face clustering on\npolygonal surfaces. In Proceedings of the Symposium on Interactive 3D\nGraphics, 2001.\n[12] S. Valette and J.-M. Chassery. Approximated centroidal voronoi\ndiagrams for uniform polygonal mesh coarsening. 23(3):381389, 2004.\n(Proc. Eurographics04).\n[13] S. Valette, J.-M. Chassery, and R. Prost. Generic remeshing\nof 3d triangular meshes with metric-dependent discrete voronoi\ndiagrams. IEEE Transactions on Visualization and Computer Graphics,\n10(2):369381, 2008."]}