David Cazier MRMap2D

Accueil || Travaux de recherche || Projets et collaborations || Publications || Curriculum Vitae
Simulation de foules || Détection de collisions || Cartes multirésolutions || Reconstruction || Cartes non-variétés

Modèles combinatoire multirésolutions

La représentation multirésolution d'objets géométriques suscite un intérêt croissant dans de nombreux domaines de l'informatique graphique. Dans ce cadre, une surface n'est plus modélisée par un maillage unique, mais par une série de maillages imbriqués, constituant des niveaux de résolution, et par les règles permettant de passer de l'un à l'autre. La représentation est dite adaptative si la résolution maximale n'est pas la même partout. Les modèles multirésolution trouvent des applications en analyse multirésolution, pour le filtrage ou la compression de maillages, en transmission progressive et pour un affichage dépendant du point de vue.

Les surfaces de subdivision sont une des méthodes permettant de construire des surfaces multirésolution. Les modèles utilisés sont souvent des forêts de quadtrees dérivant naturellement des schémas de subdivision employés (quadrisection de faces). Ces structures sont limitées aux maillages triangulaires ou carrés et les requêtes d'adjacence y sont exécutées en O(log(n)) ce qui reste gênant pour les traitements géométriques usuels.

A contrario, les maillages très denses issus d'acquisition 3D peuvent avoir une connectivité irrégulière. Dans ce cadre, les maillages progressifs forment une hiérarchie naturelle obtenue grâce à des contraction de cellules. Ces modèles n'exploitent pas de structure multirésolution et doivent reconstruire les maillages à la volée, pour pouvoir appliquer les algorithmes précédemment cités.

Nous avons proposé une structure de données tout à fait originale, les cartes multi-résolution ou MR-maps 2-KCB09. Elle est basée sur les cartes combinatoires et en hérite la formalisation, la généralité et l'efficacité. Le modèle des MR-maps est également adaptatif c'est-à-dire qu'il permet un raffinement à une profondeur variable suivant les zones de l'objet modélisé. Suite à la définition des MR-maps, nous avons proposé un plongement de celles-ci sur des surfaces de subdivision 3-KCB07, 4-KCB07.

Nous avons montré que le coût mémoire des MR-maps était similaire aux quadtrees dans le cas général et adaptatif alors que l'efficacité des parcours des différents niveaux de résolution est grandement améliorée et reste en temps constant quelque soit le niveau de résolution utilisé.

Ce nouveau type de plongement, jamais proposé pour des cartes combinatoires, possède de nombreux avantages. Les MR-maps supportent un large éventail de schémas de subdivision : les schémas primaux (découpant les faces) ou duaux (éclatement de sommets), et même des schémas plus originaux et non encore utilisés en multi-résolutions comme le schéma \sqrt(3) ou le schéma quad/triangle 4-KCB07a (mélangeant facettes triangulaires et rectangulaires).