Surfaces polygonales et surfaces de subdivision
Élève : Vetea STOLL
Tuteur : Jacques Olivier Lachaud
Définitions
Surface
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,6,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]
Conversion
La structure de données qu'on a est définie par une liste de points, chaque point étant une liste de 3 éléments, les coordonnées x, y et z du point. puis par une liste de faces, chaque face étant une liste contenant les index des points associés.
Notre triangle ressemblerait alors à ça :
vertex = [[x0,y0,z0], [x1,y1,z1], [x2,y2,z2]]
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 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