Implémentation de la méthode Crust pour l’approximation de contours

Projet de Calcul Géométrique

Télécharger

Introduction

Nous avions vu en tp un algorithme de restitution de contours d’une forme à partir de points. Les points donnés provenaient de l’échantillonnage d’un objet réel et donc représentaient la surface de l’objet. Puis l’algorithme utilisé, l’alpha-shape, se chargeait de raccorder les points de manière à retrouver la forme originelle pour qu’on puisse l’afficher.

Seulement, après des tests sur divers objets échantillonnés, et après plusieurs essais de valeurs pour l’alpha-shape, cette méthode s’est avérée assez peu fidèle même si la forme générale était respectée.

C’est pourquoi il nous a paru intéressant de voir quels autres types d’algorithmes étaient utilisés pour évaluer le contour d’une forme, Comme le crust, et quel degré de fidélité ils pouvaient donner.

Utilisation de Delaunay et Voronoï

Le module Calcul géométrique nous a montré un aspect spécifique de la programmation qui est l’optimisation des algorithmes de modélisation d’images, 2D ou 3D.

Nous avons en effet vu tout l’aspect de modélisation par triangulation, où une forme complexe n’est que l’assemblage de formes élémentaires (triangles en 2d et tétraèdres en 3D). Cette méthode est la plus utilisée car elle possède des bases théoriques solides qui ont été largement étudiées, et sur laquelle des algorithmes puissants ont été conçus.

C’est le cas notamment de la triangulation de Delaunay et du diagramme de Voronoï qui en découle. Cette triangulation possède des propriétés intéressantes en ce qui concerne la distance entre les points d’un même triangle par rapport à la distance avec les points d’autres triangles, ce qui fait que cet algorithme est largement utilisé dans les outils de modélisation graphique.

Nous avons étudié ces algorithmes en cours et lors des divers TPs, et ce projet nous a permis de les mettre en application dans une méthode nouvelle que nous n’avions jamais étudié.

Implémentation

Nous avons suivi pour l’implémentation la méthode donné dans le sujet, à savoir construire la triangulation de Delaunay des points donnés, puis y ajouter les sommets de Voronoï obtenus, et enfin ne conserver que les arêtes joignant deux points mesurés.

Les fonctions de triangulation et de calcul des sommets de Voronoï étaient déjà implémentés dans la librairie C++ CGAL, qui nous a été expliquée en cours et sur laquelle nous effectuions nos tps, c’est pourquoi nous avons choisi de nous baser sur cette librairie pour développer notre programme.

Nous avons donc ensuite appelé les différents traitements dans l’ordre prescrit (ça fait un peut médical tout ça…):

Problèmes rencontrés

Tout d’abord, nous nous sommes posé la question de savoir comment récupérer les points représentant un contour. Soit on récupérait des données dans un fichier comme nous l’avions vu dans la technique de l’alpha-shape, soit nous saisissions des points entrés successivement par l’utilisateur.

Nous avons choisi cette deuxième solutions car cela permet à l’utilisateur de varier les formes qu’il veut reconstruire et ainsi essayer des contours complexes sans avoir à écrire tout un fichier texte où la représentation visuelle est difficile. Mais cette approche n’est possible que parce que nous n’avons implémenté l’algorithme que dans un espace 2D, où on pouvait donner de manière exacte la position du point dans le plan.

Un autre problème a été de différencier les points mesurés qui sont donnés par l’utilisateur, et les sommets de Voronoï que l’on calcule ensuite. En effet, comme on affiche les différentes étapes de l’algorithme, on a intégré les sommets de Voronoï à la triangulation. Il était ensuite impossible de distinguer les points mesurés parmi tous les points de la triangulation pour exécuter la dernière étape.

C’est pourquoi nous avons utilisé un vecteur annexe dans lequel nous avons stocker les points mesurés indépendamment de la triangulation. Il était ensuite aisé de tester si les arêtes possédaient des points dans ce vecteur pour trouver le contour calculé.

Conclusion

Ce projet nous a permis de mettre en pratique l’algorithme crust que nous avions étudié en cours. Ainsi, nous avons pu voir de façon expérimentale son fonctionnement et ses limites. L’utilisation de la librairie CGAL a été très efficace. Elle nous a permis d’implémenter très rapidement cet algorithme faisant appel à Delaunay et à Voronoï.