Surfaces polygonales et surfaces de subdivision

Élève : Vetea STOLL

Tuteur : Jacques Olivier Lachaud

Structure de données demie arêtes ailées

Description

Dans cette structure de données les arêtes (ex point A et B) sont décomposée en 2 demie arêtes (A vers B et B vers A) sont définies implicitement par un indice.

Chaque demie arête a une demie arête suivante (next) une demie arête opposée (opp) un point vers lequel la demie arête pointe (to_vertex) et l'indice de la face à laquelle la demie arête est associée (face), si il n'y a pas de face on mettra -1 par convention.

Pour accéder à ces paramètres on définie des listes de longueur n avec n nombre de demie arêtes pour chaque paramètre.

Les faces ont une demie arête associée de façon arbitraire (w_face) également pour les points (w_vertex).

On fera également des listes pour ces paramètres de longueur n avec n nombre de face et nombre de points.

La structure de donnée d'un triangle ressemblera à ça :

next : [2,5,4,1,0,3]

opp : [1,0,3,2,5,4]

to_vertex : [1,0,2,1,0,2]

face : [0,-1,0,-1,0,-1]

w_face : [0]

w_vertex : [1,3,5]

On utilise cette structure de données car elle est plus facile à manipuler pour faire la subdivision par la suite.

Conversion

La structure de données qu'on a est définie par une liste de faces, chaque face étant une liste contenant les index des points associés.

Notre triangle ressemblerait alors à ça :

faces = [ [0,1,2] ]

On parcourt la liste des faces et on parcourt chaque face. On a donc des arêtes définies par pointA = faces[ i ] [ j ] et pointB = faces[ i ] [ (j+1) % len(faces[ i ]) ].

On peut alors définir une demie arête (pointA -> pointB) ainsi que son opposée (pointB -> pointA) en faisant attention attention qu'elle n'aie pas déjà été définie.

Pour définir des indices aux demies arêtes il suffit de garder en mémoire le nombre d'itérations qui ont eu lieu, qu'on va appeler n. Chaque demie arête aura l'indice 2n et chaque demie arête opposée aura l'indice 2n+1

Les listes sont alors un jeu d'enfant à remplir, excepté next, en particulier quand on définie les demies arêtes opposées car on ne sait pas à l'avance quel sera la demie arête suivante. On les définie alors par -1 temporairement.

Quand l'algorithme continue, si quand on veut définir une demie arête on se rend compte qu'elle a déjà été créée, on met à jour ses listes next et face. Mais il reste alors les demies arêtes du bord.

Après avoir executé cette première partie de la conversion, on s'occupe donc des next pour les demies arêtes opposées.

On commence par parcourir la liste des demies arêtes au bord (celles pour lesquelles la face associée est -1) et pour chaque demie arête, on prend l'opposée et tant que la demie arête n'est pas au bord, on prend l'opposée de la demie arête précédente (l'inverse de next).

Pour trouver la demie arête précédente il suffit de prendre la demie arête suivante jusqu'a ce qu'on retombe sur celle que l'on avait au départ, on aura donc la demie arête précédente en mémoire.

Cette demie arête est donc la suivante de celle que l'on avait au départ.

Déconversion

La déconversion est un peu plus simple. On commence par parcourir w_face, et on rajoute le to_vertex de la demie arête dans une liste tant que la demie arête suivante n'est pas celle que l'on avait au départ.