La librairie CGAL est une librairie en C++, développée initialement par des chercheurs en géométrie algorithmique, qui dispose de nombreuses fonctionnalités et algorithmes implémentés. Elle permet de réaliser des calculs en coordonnées exactes ou approchées, en manipulant des données 2D et 3D. Son manuel est très complet, et il illustre la diversité des usages couverts par la librairie.
La structure de données que nous allons utiliser dans cette série de TP est la structure des surfaces polyédrales qui s'appuie sur une structure de données en demie arêtes.
Une partie des programmes implémentés lors de ce TP seront réutilisés lors du prochain TP, lequel sera un TP noté.
L'un des formats de fichiers standard pris en charge par CGAL est le format off. Vous pouvez récupérer des fichiers au format off sur internet, par exemple :
Si vous souhaitez plus tard utiliser vos propres maillages, vous pouvez les modéliser dans blender, puis utiliser un script permettant de supporter ce format à l'export : Import/Export OFF. Commencer par télécharger le fichier import_off.py sur le git du projet, puis suivez les instructions pour installer cet addon dans blender. Vous êtes maintenant capable d'exporter des fichiers au format off depuis le menu File > Export de blender.
Le programme genre.cpp utilise la librairie CGAL pour charger un maillage, puis calcule le genre de cette surface en comptant le nombre de sommets, arêtes et faces du maillage (il ne fonctionne donc pas avec les maillages comportant plusieurs composantes connexes, ou avec les surfaces à bord).
Après avoir parcouru la documentation expliquant comment créer un programme example CGAL, utilisez le script cgal_create_CMakeLists pour générer un fichier CMakeLists.txt. Utiliser ensuite cmake pour compiler ce premier exemple. Le bon usage veut que l'on sépare le code source des versions compilées du programme. Une bonne pratique consiste donc à placer les codes sources dans un répertoire src, d'y générer le fichier CMakeLists.txt, puis de lancer cmake depuis un autre répertoire (nommé build), en donnant le chemin du dossier source en paramètre de la commande cmake.
Petit coup de main : le dépôt TP1 geoalgo ZZ3F1 contient un environnement prêt à l'usage, qui respecte cette pratique.
Vérifier à partir d'un fichier off exporté depuis blender que le programme fonctionne correctement.
En parcourant la documentation de CGAL, on voit qu'il est aussi facile de parcourir chacune des faces d'un maillage, et dans chacun d'eux, de parcourir chacune des demie-arêtes qui le composent : example with circulator writing objet file format. Attention, quand dans cet exemple les auteurs utilisent une distance, il ne s'agit pas de la distance euclidienne entre les points, mais du calcul de l'identifiant du point (distance dans l'espace des Handle, équivalent grossier de pointeurs). Indication : utilisez la méthode CGAL::squared_distance entre les points associés aux sommets.
Travail à réaliser : écrire un programme qui calcule pour chaque face d'un maillage donné son périmètre. Afficher cette liste de longueurs dans la sortie standard.
Afin de visualiser simplement le résultat de ces calculs, une méthode consiste à sauver le maillage, en associant à chaque face du maillage une couleur correspondant à la mesure réalisée sur ce maillage. Le format OFF supporte de manière optionnelle l'information de couleur par face (voir l'exemple donné sur la page du format).
Malheureusement, l'export OFF de CGAL ne sait pas prendre en compte les couleurs : Neither normal vectors nor color attributes are evaluated.
Travail à réaliser : écrire une fonction qui prend en entrée un maillage, un ensemble de valeurs scalaires (std::map<Polyhedron::Facet_handle, double>), ainsi qu'un nom de fichier, et qui sauve le maillage au format OFF, en transformant les valeurs scalaires en couleurs pour chaque facette du maillage.
Remarque : on pourra par exemple choisir un dégradé entre blanc et rouge pour la couleur, le blanc correspondant à la valeur la plus faible, le rouge à la valeur la plus élevée.
Remarque : on pourra adapter la méthode d'export des OFF déjà donnée en exemple.
Il est bien sûr possible d'importer dans blender les fichiers off ainsi générés. Cependant, pour une visualisation rapide, le logiciel MeshLab est un outil incontournable. Vous pouvez soit l'installer, soit utiliser sa version js, exécutable depuis le navigateur.
Si vous avez démarré la version exécutable de meshlab, rendez-vous dans le menu File > Import Mesh..., puis sélectionnez votre fichier off. Il est possible d'activer l'affichage des couleurs de faces en utilisant le menu Render > Color > Per Face.
En s'inspirant du travail réalisé dans le premier calcul de propriété locale, implémenter les fonctionnalités suivantes :
Vous pouvez aussi imaginer vos propres mesures de propriétés locales.