TD7 : Décimation

L'objectif de ce TP est d'implémenter deux techniques de décimation : la première sur une nuage de points par voxélisation dans un Octree; la seconde sur un maillage triangulaire par contraction d'arêtes à l'aide d'une structure en demi-arête (half-edge).

Téléchargez et compilez cette nouvelle base de code :

curl -O https://www.labri.fr/perso/pbenard/teaching/simg/Ressources/si_tp7.zip

Elle continent notamment une classe PointCloud permettant de charger un nuage de points au format asc (suite de triplets positions et normales). La classe Mesh a été également modifiée pour utiliser la structure en demi-arête implémentée par Surface_mesh.

1. Nuage de points

Afin de décimer "adaptativement" un nuage de point dont la densité est irrégulière, il est nécessaire d'estimer son organisation spatiale. Pour cela, il est courant d'utiliser une structure de partitionnement de l'espace. Dans ce TP, vous implémenterez un Octree, une structure arborescente construite en subdivisant récursivement l'espace en huit cellules régulières (Node) jusqu'à atteindre une densité cible de points par cellule. Une fois cette structure construite, décimer adaptativement le nuage de point revient à supprimer les niveaux inférieurs de l'Octree.

Octree aux profondeurs 1, 3 et 5

1. Implémentez la fonction Octree::build qui construira l'Octree jusqu'à ce que la profondeur _maxDepth ou le nombre de point par cellule _cellSize soit atteint. L'algorithme est simple. La première cellule de l'Octree correspond à la boîte englobante du nuage de points. Ensuite, tant que les conditions précédentes ne sont pas validées, chaque cellule terminale de l'arbre est subdivisée en 8 cellules égales, chacune d'elles stockant le premier et dernier index des points qu'elle contient. Cela suppose – tout au long de la construction – de maintenir trier les points (tableau _positions et _normals) en fonction du partitionnement.

Après suppression de 4 niveaux

2. Utilisez la classe WireCube pour dessiner l'Octree à une profondeur donnée (que vous pouvez rendre contrôlable au clavier). Vous pouvez ajouter à la classe Octree une méthode retournant la liste des boites englobantes jusqu'à une profondeur donnée.

3. Implémentez la fonction Octree::decimateOneDepth qui diminuera d'un niveau la profondeur de l'Octree en remplaçant les feuilles de profondeur maximale par le barycentre des points qu'elles contiennent.

4. Implémentez la fonction Octree::decimate(int maxNumOfPoints) qui décimera le nuage de points jusqu'à ce qu'il contienne moins de maxNumOfPoints points.

5. Si possible, testez également avec le très volumineux (300Mo) nuage de points original scan.asc obtenu par acquisition laser.

2. Maillage triangulaire

La connectivité du maillage offre déjà une structuration spatiale de l'objet à décimer. Pour exploiter cette information, vous suivrez l'approche proposée par H. Hoppe dans l'article Progressive Meshes (ACM Siggraph, 1996). Cet algorithme de simplification très populaire repose sur une opération élémentaire de contraction d’arête (edge-collapse).

La contraction d'une arête orientée $(u,v)$ consiste à supprimer l'arête du maillage en ramenant toutes les arêtes aboutissant à $u$ vers $v$. Cette opération entraîne non seulement la suppression du sommet $u$, mais aussi la suppression des faces triangulaires à gauche et à droite de l'arête. Elle permet donc de passer d'un maillage cohérent à un autre maillage cohérent. En priorisant l'ordre de contraction des arêtes selon une métrique géométrique (comme leur longueur), la décimation sera adaptative.

Pour réaliser cette opération, il est nécessaire de parcourir le voisinage d'un sommet. Pour cela, vous utiliserez un structure de half-edge, ou demi-arête, qui permet de stocker efficacement les relations d’adjacence et d’incidence sur le maillage.

1. Pour vous familiariser avec la syntaxe de Surface_mesh, observez la méthode Mesh::load. Vous y découvrirez en particulier comment parcourir les sommets du maillage (Vertex_iterator) et comment accéder à leurs attributs (position, normale, etc.). Vous pourrez de la même façon parcourir les arêtes et les faces du maillage, ou circuler autour d'un sommet.

2. Implémentez la fonction Mesh::decimate qui simplifiera le maillage par contractions successives d'arêtes. Surface_mesh fournit déjà les méthodes is_collapse_ok et collapse pour tester la validité d'une contraction et contracter une demi-arête. Affectez une priorité de décimation à chaque arête et stockez-les dans une file de priorité (classe Heap). Énumérez les arêtes pour les contracter successivement jusqu'à atteindre le nombre de faces cible. Attention, chaque contraction modifie la norme des arêtes dans le voisinage immédiat de $(u,v)$, et nécessite donc une mise à jour de ces arêtes dans la file de priorité (Heap::update).

Une fois la décimation terminée, appelez la fonction Surface_mesh::garbage_collection pour nettoyer l'half-edge. Appelez également les méthodes Mesh::load et Mesh::init pour mettre à jour les données envoyées au GPU. Utilisez la touche 'w' pour afficher le maillage en wireframe.

Stanford Bunny original et décimé, nombre de face divisé par 2 puis 4.

3. La contraction d'une arête peut introduire un pli (fold) dans le maillage. Pour les éviter, il faut détecter les configurations problématiques, c'est-à-dire l'inversion de la normale d'une des faces avant et après contraction de l'arête. Auquel cas, il faut soit déclarer cette contraction comme invalide (en lui affectant par exemple une très forte pénalité), soit tenter de résoudre le pli en "basculant" une arête (edge flip).

Nombre de face divisé par 8, décimation sans et avec la détection des plis.