David Cazier XMap

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 combinatoires non variétés

La plupart des modèles usuels, comme les cartes, permettent de modéliser des variétés de dimension quelconque de manière très efficace. Cependant pour certaines applications, la possibilité de représenter des objets qui ne sont localement pas des variétés reste essentielle. Ces modèles offrent un domaine de représentation plus large, autorisent des sommets singuliers et conduisent à une représentation de complexes cellulaires permettant de combiner ensemble des objets aux dimensions variées, comme des courbes, des surfaces ou des solides.

Le modèle des arêtes radiales, introduit par Weiler en 1988, et les modèles dérivés sont toujours utilisés, bien que gourmand en mémoire et non optimaux pour les requêtes d'adjacence. Des modèles tétraèdriques, plus restreints, sont souvent préférés en pratique car plus efficaces (travaux de De Floriani par exemple).

Nous avons proposé un nouveau modèle pour la représentation des complexes cellulaires quelconques, les X-maps pour cartes étendues. Pour cela nous avons étendu les cartes combinatoires avec une nouvelle relation permettant de lier ses sommets autour de points singuliers. Les composantes connexes d'une X-map privée de cette relation forment une décomposition (non unique) des complexes modélisés en un ensemble de variétés (courbes, surfaces, volumes) accolées. Nous avons proposé, dans 4-CK10, une implémentation duale de ce modèle très compact (jusqu'à 4 fois moins coûteuse que les arêtes radiales). Ce modèle bénéficie de l'efficacité et de la généricité des cartes sur les portions correspondant à des variétés.