Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations
Algorithmes et Critères pour les Tessellations Volumétriques de Voronoi Centroïdales
Résumé
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.
Cette thèse traite du problème du calcul d’une tessellation volumique d’une forme tridimensionnelle, c’est-à-dire, étant donnée une forme tridimensionnelle qui est habituellement représentée par sa surface frontière, comment subdiviser de manière optimale l’intérieur de la surface en formes plus petites, appelées cellules, selon plusieurs critères concernant la précision, l’uniformité et la régularité. Nous considérons les tessellations de Voronoi centroïdales qui sont des tessellations volumiques uniformes et régulières.
Une tessellation de Voronoi centroïdale (CVT) d’une forme peut être considérée comme une subdivision optimale au sens où les centres de masse, appelés centroides des cellules, sont répartis de manière optimale à l’intérieur de la forme. CVTs ont été utilisés en vision par ordinateur et en infographie en raison de leurs propriétés d’uniformité et de régularité qui sont indépendantes des variations de la forme. Cependant, des problèmes restent ouverts, comme l’évaluation de la régularité d’une CVT ou la construction d’une CVT a` partir de formes représentées de diférentes manières.
Une contribution de cette thèse est que nous proposons des critères de régularité basées sur les moments de second ordre normalisés des cellules. Ces critères de régularité permettent d’évaluer les tessellations volumiques, et surtout de comparer la régularité des différentes Tessellations sans l’hypothèse que leur forme et leur nombre de sites devraient être les mêmes. Nous proposons également une approche hiérarchique basée sur un schéma de subdivision qui préserve la régularité des cellules et l’optimalité locale des CVTs. Les résultats expérimentaux montrent que notre approche est plus efficace et construit des CVTs plus régulières que les méthodes de l’état de l’art selon les critères de régularité.
Une autre contribution est une nouvelle algorithme de calcul de CVT pour les formes implicites et une comparaison approfondie entre le Marching Cubes, la technique du raffinement de Delaunay et notre algorithme. La clé de notre algorithme est d’utiliser des enveloppes convexes et une amélioration locale pour construire des cellules au bord avec précision. Nous présentons une comparaison des trois algorithmes avec des critères différents, comme la précision, la régularité et la complexité sur un grand nombre de données différentes. Les résultats montrent que notre méthode construit les tessellations volumiques les plus précises et les plus régulières.
Nous explorons aussi des applications comme, par exemple, une chaîne de traitement d’animation des formes basées sur les CVTs qui génère des animations plausibles à partir de dynamique réelle.
Loading...