Discrete Voronoi Diagram on the Buny mesh

Purpose and context

The aim of this work is to provide a fast and efficient mesh coarsening/resampling facility for triangular meshes. It can be applied to very complex meshes (several millions of vertices). This approach is based on the clustering of the input mesh elements (vertices or triangles) within a variational framework


The proposed clustering approach generates partitions which are similar to centroidal Voronoi regions, where each region has the same size1. As a consequence, the sampling is very uniform on the surface, and the resulting triangulation has elements with good aspect ratios.

Curvature adaptivity is possible by introducing curvature measures within the clustering scheme (see figure 2). Note that this approach is also useful for remeshing applications (when the user wants the output mesh to have an arbitrary number of vertices2. This approach was extended for anisotropic meshing, to provide approximation-effective meshes 3.


The following anmation shows the clustering evolution during minimization, on the Stanford Bunny. Initial seeds have been concentrated on one side on purpose, and the result shows that our approach is robust to initialization.

Clustering evolution
Output simplification

Source code

ACVD Source code is available on github

This code is distributed under the CECILL-B license (BSD-compatible) © CNRS, INSA-Lyon, UCBL, INSERM.


  1. 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, Volume 14, no. 2, pages 369-381, 2008. ↩︎

  2. Sébastien Valette, Ioannis Kompatsiaris and Jean-Marc Chassery, Adaptive Polygonal Mesh Simplification With Discrete Centroidal Voronoi Diagrams, 2nd International Conference on Machine Intelligence ICMI 2005, Tozeur, Tunisia, November 5-7, pp. 655-662, 2005. ↩︎

  3. Sébastien Valette and Jean-Marc Chassery, Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening, Computer Graphics Forum (Eurographics 2004 proceedings), Vol. 23, No. 3, September 2004, pp. 381-389. ↩︎