Géométrie et Synthèse d'Images

TD du 3 Décembre 2003

On souhaite appliquer à un maillage une opération de subdivision à la manière de Loop. On commence par mettre en place une structure de données permettant un accès facile au voisinage topologique d'un sommet d'un maillage.

Gestion des voisinages

On suppose que l'on a chargé un modèle (maillage) au format geomview :

Définir une structure de liste chainée de sommets (on travaillera au choix avec l'indice du sommet dans le tableau général des sommets ou avec un pointeur sur la structure "vertex").
écrire une fonction d'insertion unique dans cette liste (si le sommet à ajouter y figure déjà on ne l'ajoute pas).
Ajouter à chaque sommet (vertex) la liste des sommets voisins (au moins un triangle s'appuie sur ces deux sommets) et écrire une fonction pour établir ces listes.
A titre de test, on peut utiliser ces informations pour colorier le maillage en fonction de la distance topologique à un sommet particulier du maillage. Pour cela
- Définir une structure de file (first in, first out) pour stocker un ensemble de sommets (avec par exemple des fonctions Put, Get, IsEmpty...)
- Utiliser cette structure pour parcourir le maillage (à partir d'un sommet choisi comme vous voudrez) "en largeur d'abord", en notant pour chaque sommet lors de son insertion dans la file sa "distance" au sommet d'origine.

Subdivision de Loop

On va construire une suite de maillages M(k+1) = R( M(k) ) qui converge vers une surface continue (C1) :

On rappelle que la transformation R est définie de la façon suivante autour d'un sommet

de valence n:

Les indices étant pris modulo n, avec

Le cas des nouveaux sommets (crées sur les aretes) nécessite une attention particulière, puisqu'il faut déterminer les sommets à utiliser. Une manière d'y parvenir est de rechercher les sommets qui sont voisins à la fois des deux extremités de l'arete. Ecrire une fonction qui accepte en entré deux sommets voisins et renvoie les deux sommets (au plus) complétant les triangles qui s'appuient sur l'arete.
Ecrire un programme qui réalise la transformation de Loop sur un maillage au format geomview. On appliquera bien sur cette transformation plusieurs fois de suite en affichant les maillages successifs.

Dernière mise à jour: 2 Décembre 2003

Francois.Sillion@imag.fr