Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations

Li Wang 1, 2
2 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 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.
Type de document :
Thèse
General Mathematics [math.GM]. Université Grenoble Alpes, 2017. English. 〈NNT : 2017GREAM002〉
Liste complète des métadonnées

Littérature citée [144 références]  Voir  Masquer  Télécharger

https://tel.archives-ouvertes.fr/tel-01455701
Contributeur : Abes Star <>
Soumis le : vendredi 12 janvier 2018 - 14:57:41
Dernière modification le : samedi 6 octobre 2018 - 01:17:19

Fichier

WANG_2017_archivage.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01455701, version 3

Collections

Citation

Li Wang. Algorithms and Criteria for Volumetric Centroidal Voronoi Tessellations. General Mathematics [math.GM]. Université Grenoble Alpes, 2017. English. 〈NNT : 2017GREAM002〉. 〈tel-01455701v3〉

Partager

Métriques

Consultations de la notice

373

Téléchargements de fichiers

429