Algorithmes et critères pour les Tessellations volumétriques de Voronoi Centroïdales

This thesis addresses the problem of volumetric tessellations from 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 concerning accuracy, uniformity and regularity. We consider centroidal Voronoi tessellation that is an effective approach for building uniform and regular volumetric tessellations.A centroidal Voronoi tessellation (CVT) of a shape can be viewed as an optimal subdivision with the cells whose centers of mass, called centroids, are optimally distributed inside the shape. CVTs have been widely used in computer vision and graphics because of their properties of uniformity and regularity that are immune to shape variations. However, the problems such as how to evaluate the regularity of a CVT and how to build a CVT from different types of shapes remain a challenge.One contribution of this thesis is that 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 CVTs 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 of Marching Cubes, Delaunay refinement and our algorithm. The key of our algorithm is using convex hulls and the local improvement 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 variant data. The results show that Marching Cubes is the fastest one and our algorithm build more accurate and regular volumetric tessellations than the others.We also explore the applications such as a shape animation framework based on CVTs that generates plausible animations with real dynamics. And the source code of the whole work of this thesis is available online for the purpose of further research.Cette thèse traite du problème de la tessellation volumétrique à partir des formes en trois dimensions, c’est-à-dire, étant donné une forme tridimensionnelle qui est habituellement représentée par sa surface au bord, comment subdiviser l’intérieur de la surface en formes plus petites, appelées cellules, de manière optimale selon plusieurs critères concernant l’exactitude, l’uniformité et la régularité. Nous considérons la tessellation de Voronoi centroidale qui est une approche efficace pour construire des tessellations volumétriques uniformes et régulières.Une tessellation de Voronoi centroidale (CVT) d’une forme peut être considérée comme une subdivision optimale avec les cellules dont les centres de masse, appelés centroides, sont répartis de manière optimale l’intérieur de la forme. CVTs ont été largement utilisés dans la vision par ordinateur et l’infographie en raison de leurs propriétés d’uniformité et de régularité qui sont indépendantes des variations de la forme. Cependant, les problèmes tels que comment évaluer la régularité d’une CVT et comment construire une CVT à partir des formes de types différents restent un défi.Nous proposons, comme contribution de cette thèse, que des critères de régularité basés sur des moments de second ordre normalisés des cellules. Ces critères de régularité permettent d’évaluer les tessellations volumétriques, et surtout, de comparer la régularité des différents CVTs 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 construit de manière plus efficace 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 un nouvel algorithme de CVT pour les formes implicites et une comparaison approfondie entre l’algorithme Marching Cubes (MC), le raffinement de Delaunay et notre algorithme. L’idée clé de notre algorithme est l’utilisation des enveloppes convexes et l’amélioration locale pour construire des cellules au bord précises. Nous présentons une comparaison des trois algorithmes avec des critères différents, y compris la précision, la régularité et la complexité sur un grand nombre de données variantes. Les résultats montrent que MC est le plus rapide et que le notre construit les tessellations volumétriques les plus précises et les plus régulières.Nous explorons aussi les applications comme, par exemple, un framework d’animation des formes basées sur CVTs qui génère des animations plausibles avec une réelle dynamique. Le code source de l’ensemble des travaux de cette thèse est disponible en ligne dans le but de la recherche future