ACVD : Robust remeshing via Approximated Centroidal Voronoi Diagrams

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

Figure 1: The input mesh (left) is partitioned by means of variational clustering (middle). Each cluster results in the creation of a new vertex in the coarsened version. The triangulation is deduced from the clusters adjacency (right) and is of very good quality when considering the triangles aspect ratio.


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

Figure 2: A curvature indicator map is built for the bunny mesh (left) and is inserted in the clustering scheme, to obtain a curvature-adapted isotropic mesh.

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 vertices VALE-05. This approach was extended for anisotropic meshing, to provide approximation-effective meshes


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.


  • 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.

    Abstract: In this paper, we propose a generic framework for 3D surface remeshing. Based on a metric-driven Discrete Voronoi Diagram construction, our output is an optimized 3D triangular mesh with a user defined vertex budget. Our approach can deal with a wide range of applications, from high quality mesh generation to shape approximation. By using appropriate metric constraints the method generates isotropic or anisotropic elements. Based on point-sampling, our algorithm combines the robustness and theoretical strength of Delaunay criteria with the efficiency of entirely discrete geometry processing . Besides the general described framework, we show experimental results using isotropic, quadric-enhanced isotropic and anisotropic metrics which prove the efficiency of our method on large meshes, for a low computational cost. [Preprint]
  • 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.

    Abstract: In this paper, we propose an adaptive polygonal mesh coarsening algorithm. This approach is based on the clustering of the input mesh triangles, driven by a discretized variationnal definition of centroidal tesselations. It is able to simplify meshes with high complexity i.e. meshes with a large number of vertices and high genus. We demonstrate the ability our scheme to simplify meshes according to local features such as curvature measures. We also introduce an initial sampling strategy which speeds up the algorithm, an on-the-fly checking step to guarantee the validity of the clustering, and a postprocessing step to enhance the quality of the approximating mesh. Experimental results show the efficiency of our scheme both in terms of speed and visual quality. [Preprint]
  • 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.

    Abstract: We present a novel clustering algorithm for polygonal meshes which approximates a Centroidal Voronoi Diagram construction. The clustering provides an efficient way to construct uniform tessellations, and therefore leads to uniform coarsening of polygonal meshes, when the output triangulation has many fewer elements than the input mesh. The mesh topology is also simplified by the clustering algorithm. Based on a mathematical framework, our algorithm is easy to implement, and has low memory requirements. We demonstrate the efficiency of the proposed scheme by processing several reference meshes having up to 1 million triangles and very high genus within a few minutes on a low-end computer. [Preprint]

Source code and executable

ACVD uses the Visualization ToolKit (VTK)

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

A (rather old...) pre-compiled window$ executable is available here. Note that only the github source code contains the last version.

Design: HTML5 UP.