Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations


Spécialité : Mathématiques et Informatique

27/01/2017 - 14:00 Mr Li Wang Grand Amphi de l'INRIA Rhône-Alpes, Montbonnot

Mots clé :
  • CVT
  • Regularity
This thesis addresses the problem of computing volumetric tessellations of three-dimensional shapes, i.e., given a three-dimensional shape that is usually represented by its boundary surface, how to optimally subdivide the interior of the surface into smaller shapes, called cells, according to several criteria related to accuracy, uniformity and regularity. We consider centroidal Voronoi tessellations, which are uniform and regular volumetric tessellations. 
A centroidal Voronoi tessellation (CVT) of a shape can be viewed as an opti- mal subdivision in the sense that the cells' centers of mass, called centroids, are regularly distributed inside the shape. CVTs have been used in computer vision and graphics because of their properties of uniformity and regularity that are immune to shape variations. However, problems such as how to evaluate the regularity of a CVT and how to build a CVT from different representations of shapes remain. 
As one contribution of this thesis, we propose regularity criteria based on the normalized second order moments of the cells. These regularity criteria allow evaluating volumetric tessellations and specially comparing the regularity of different Tessellations without the assumption that their shape and number of sites should be the same. Meanwhile, we propose a hierarchical approach based on a subdivision scheme that preserves cell regularity and the local optimality of CVTs. Experimental results show that our approach performs more efficiently and builds more regular CVTs according to the regularity criteria than state-of-the-art methods. 
Another contribution is a novel CVT algorithm for implicit shapes and an extensive comparison between the Marching Cubes, the Delaunay refinement technique and our algorithm. The keys of our algorithm are to use convex hulls and local improvements to build accurate boundary cells. We present a comparison of these three algorithms with different criteria including accuracy, regularity and complexity on a large number of different data. The results show that our algorithm builds more accurate and regular volumetric tessellations than the other approaches. 
We also explore applications such as a shape animation framework based on CVTs that generates plausible animations with real dynamics.


  • Mr Edmond Boyer (Directeur de recherche - Inria Grenoble Rhône-Alpes )
  • Mr Franck Hetroy Wheeler (Pofesseur - Grenoble INP )


  • Mr Bruno Levy (Directeur de Recherche - Inria Nancy-Grand Est )
  • Mr Pierre Alliez (Directeur de recherche - Inria Sophia Antipolis Méditerranée )


  • Mme Stefanie Hahmann (Professeur - Grenoble INP )
  • Mr Sébastien Valette (Chercheur - CNRS Lyon )