Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations

Li Wang 1
1 MORPHEO - Capture and Analysis of Shapes in Motion
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Résumé : 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.
Type de document :
Thèse
Graphics [cs.GR]. UGA - Université Grenoble Alpes, 2017. English
Liste complète des métadonnées


https://hal.inria.fr/tel-01455701
Contributeur : Li Wang <>
Soumis le : vendredi 3 février 2017 - 17:18:41
Dernière modification le : jeudi 15 juin 2017 - 09:08:42
Document(s) archivé(s) le : vendredi 5 mai 2017 - 11:10:35

Identifiants

  • HAL Id : tel-01455701, version 1

Collections

Citation

Li Wang. Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations. Graphics [cs.GR]. UGA - Université Grenoble Alpes, 2017. English. <tel-01455701>

Partager

Métriques

Consultations de
la notice

396

Téléchargements du document

348