See also

Stage M2R 2006 : Exploration interactive de gros maillages surfaciques et volumiques

Réalisé par Sébastien BARBIER
Encadrants: Georges-Pierre BONNEAU et Lionel Revéret.

Sujet

Les méthodes de simplification de maillage en vue de leur exploration temps réel fonctionnent en deux temps. Dans une étape de pré-processing une hiérarchisation des données est calculée, basée sur des opérateurs de simplification atomique du maillage (contraction d’une arête ou d’un triangle, suppression d’un sommet…). Cette étape peut être coûteuse en temps et en mémoire. Dans un second temps, un algorithme de parcours (pseudo-) temps réel de la structure de données hiérarchique est appliqué. Cet algorithme, prenant en compte le point de vue de la scène, la complexité de l’objet et les capacités graphiques de la machine, permet de calculer un maillage approximant le maillage exact, et correspondant à un chemin extrait de la structure hiérarchique issue de la phase de pré-processing. Une application distribuée de visualisation multirésolution de grands maillages a été implémentée dans le cadre d’un stage de Master 1. Celle-ci met en jeu un PC « principal » affichant grâce à un projecteur vidéo le maillage global simplifié, et un PC « secondaire » portable (éventuellement un assistant numérique ou un TabletPC) chargé d’afficher les détails locaux du maillage. Ainsi le PC portable fait office de loupe locale permettant d’afficher les détails fins du maillage et des données portées par ce maillage. Cette application est basée sur une librairie publique permettant l’extraction du maillage approximant. Cette librairie a l’avantage de pouvoir être utilisée quelque soit l’opérateur de simplification atomique choisi. Cette généralité se traduit par des temps d’extraction incompatibles avec une exploration interactive, même pour des tailles de maillage modestes.
Le but principal de ce stage est de développer des algorithmes d’extraction interactifs ou même temps réel, spécialisés pour l’opérateur de contraction d’arête, et pour la sélection par proximité géométrique. Ces algorithmes utiliseront une structure de données secondaire sous la forme d’une forêt d’octrees, liée au graphe acyclique provenant des contractions d’arêtes. Suivant la progression du travail sur cette partie théorique, le stage pourra comporter de plus une phase pratique d’implémentation des algorithmes dans le cadre d’une mini-plateforme d’expérimentation mettant en jeu les deux PCs (fixes et portable), le projecteur, et un écran de projection arrière.

Contributions

Nous avons développé une application fonctionnant en mémoire interne comme en mémoire externe pour pouvoir traiter de manière interactive l'exploration de maillages surfaciques et volumiques.
Ces travaux reposent sur la notion de bi-résolution. En effet, ils utilisent uniquement deux maillages : un maillage grossier représentant la globalité de l'objet permettant à l'utilisateur de se repérer ; et un maillage précis fin d'où est extrait une région locale d'intérêt précisée par l'utilisateur. Ces deux maillages sont ensuite reliés en un seul maillage.
Pour cela, nous utilisons une clusterisation de sommets du maillage fin qui permet dès lors de construire de manière astucieuse le maillage grossier et de raccorder les deux maillages à un moindre coût. L'extraction de la région fine d'intérêt est réalisée via des structures de données type tables de hachage, et en utilisant la cohérence temporelle afin de diminuer la complexité algorithmique et garantir l'interactivité.
Cette méthode générale fonctionne à la fois en mémoire interne et en mémoire externe (afin de traiter de gros maillages de plusieurs dizaines de millions de sommets) pour les maillages surfaciques et volumiques. Elle garantit une interactivité notable pour les maillages volumiques.

Résultats

Voici quelques résultats sur les maillages surfaciques et volumiques. Des vidéos sont disponibles pour rendre compte de l'interactivité de l'application.