Les sujets sont à faire seul ou en binôme. Chaque sujet sélectionné est barré de la liste une fois qu’il a été sélectionné deux fois (sur le mode premier demandé, premier servi).
Le travail à produire est le suivant:
– lire les articles en référence, lorsque listés.
– mettre en œuvre l’algorithme et une démonstration C++ en partant des TPs.
– expérimenter
– rédiger un rapport (max ~10 pages, au format pdf) qui détaille votre approche et vos expérimentations.
– préparer une présentation de 15 minutes pour une soutenance prévue le 19 juin (horaires et ordres de passage à venir sur cette page).
LISTE DE PASSAGE
9h00 – 9h45 ROUXEL – TAVENARD
9h45 – 10h15 MEYER
10h15 – 11h00 PESNEAU – MONNIER
11h00 – 11h30 EVAIN
11h30 – 12h00 GODARD
break
12h15 – Réunion d’évaluation
13h15 – 14h00 REIZINE – LESAGE
14h00 – 14h45 COHEN – CHARRAS
14h45 – 15h15 STEINSTRAESSER
15h15 – 15h45 CRESSOT
Sujet 1 : reconstruction de bâtiments à partir de données LIDAR aérienne [Thomas Pesneau et Robin Monnier]
En utilisant CGAL, proposer un algorithme permettant de reconstruire les toits de données Lidar aérien sous forme de surfaces avec bords. Le maillage en sortie devra avoir une faible complexité. Utiliser en entrée un des trois fichiers ply du dossier « Lidar_aerien_toits ».
Sujet 2 : Segmentation de scans LIDAR aérien [Simon Evain, Loic Cressot]
Sur la base du TP3 et en vous aidant du TP2, proposer un algorithme permettant de segmenter des nuages de points issus de Lidar aérien en 3 classes : bâtiment, sol et végétation. Utiliser en entrée un des trois fichiers ply du dossier « Lidar_aerien_scenes ».
Sujet 3 : Régularisation de primitives planaires [Sami SIRAJ-DINE et Chaïmaa Kadaoui, Charles Reizine et Adrien Lesage]
A partir d’une configuration de plans extraite par le code du TP2, proposer un algorithme permettant de détecter les paires de plans 1/ parallèles, 2/ coplanaires et 3/ orthogonaux. Dans un second temps proposer une méthode pour régulariser les plans entre eux en fonction des régularités détectées.
Indications : la détection des régularités devra faire intervenir un paramètre d’angle et un paramètre de position.
Sujet 4 : Adjacence de primitives planaires [Adrien Touboul et Pierre-Alain Langlois]
A partir d’une configuration de plans extraite par le code du TP2, proposer trois différentes métriques pour détecter les paires de plans adjacents, i.e. liés par une relation de connexion. Comparer et discuter l’efficacité des trois métriques proposées.
Sujet 5 : Segmentation de maillage avec végétation [Nathan ROUXEL et Hugues TAVENARD, Victor Cohen et Franck Charras]
Sur la base du TP3, proposer un algorithme permettant de segmenter des maillages en 4 classes : toit, façade, sol et végétation. Utiliser en entrée un des trois fichiers ply du dossier « mesh_MVS ».
Sujet 6 : convergence de l’itération de Lloyd [Joao Guilherme CALDAS STEINSTRAESSER]
A partir du TP « Delaunay 2D », étudier la convergence de l’itération de Lloyd en calculant la moyenne de la norme des vecteurs de déplacement des sites, en fonction des itérations. Tracer la même courbe pour l’énergie minimisée par l’itération. Attention : le calcul de cette énergie requiert soit de mettre en œuvre une quadrature (un échantillonnage uniforme de points dans les cellules de Voronoi), soit de trouver une forme close à partir d’une décomposition des cellules en triangles, et d’une transformée affine du triangle canonique pour lequel une forme close est triviale. Essayez les deux approches.
1 – Expérimenter avec différentes initialisations (points uniformes, ou concentrés dans un coin du domaine, sur une ligne, etc).
2 – Quelle est l’influence du domaine sur la convergence ? Mener des expériences avec un domaine en forme de « sablier », avec un goulet d’étranglement, où les sites initiaux sont générés sur la partie haute du sablier. Varier la largeur du goulet et observer.
3 – Quelles idées proposez-vous pour accélérer la convergence ? En termes d’initialisation puis de variante « Newton » de l’itération.
Sujet 7 : itération de Lloyd et densité variable
A partir du TP « Delaunay 2D ». La version corrigée du TP utilise une fonction de densité. Mettre en œuvre une variante utilisant une fonction de densité variable qui impacte le calcul du centre de masse et requiert une quadrature.
1 – Mettre en œuvre la quadrature à base de points générés uniformément.
2 – Mettre en œuvre la quadrature à base de triangles.
3 – Expérimenter en définissant une fonction de densité linéaire, puis radiale, puis sinusoïdale, etc. Calculer la distribution des de l’énergie minimisée par l’itération, pour chaque cellule de Voronoi (requiert une quadrature via un échantillonnage uniforme de points dans les cellules de Voronoi), et observer l’équi-distribution de l’énergie au cours des itérations.
4 – Expérimenter en calculant la distribution des degrés des cellules de Voronoi (hexagones, pentagones, etc) en fonction de la vitesse de gradation de la fonction de densité, pour un grand nombre de sites et une quadrature précise.
Sujet 8 : itération de Lloyd et gestion du bord [Ludovic Godard-Cadillac]
A partir du TP « Delaunay 2D ». La version corrigée du TP utilise un ensemble de points fixes sur le bord du domaine.
1 – Proposer un algorithme qui utilise un disque comme domaine, où les points du bord peuvent se déplacer en étant contraints à rester sur le bord du disque. Calculez non plus un centre de masse mais le point du bord qui minimise la somme des carrés des distances à tous les points de chaque cellule (requiert une quadrature par exemple à base de points).
2 – Proposer un algorithme où le domaine est un disque, et les cellules de Voronoi sont intersectés avec le domaine avant le calcul du centre de masse. Quelle approximation devez-vous faire pour calculer l’intersection ? Vous pouvez aussi ne pas faire l’intersection explicitement mais implicitement lors du calcul des centres de masse. Dans ce cas les générateurs sont repoussés par le bord.
3 – Dans le cas gestion du bord avec intersection, qu’advient-il lorsque le bord est concave ? Proposer une solution qui garantit que les sites restent dans le domaine.
Sujet 9 : Diagramme de Voronoi borné
A partir du TP « maillage 2D » qui utilise une triangulation de Delaunay contrainte, écrire un programme qui calcule et affiche le diagramme de Voronoi borné.
Le diagramme de Voronoi borné est le pseudo-dual de la triangulation de Delaunay contrainte. On peut le construire à partir de la triangulation contrainte en marquant tous les triangles (“aveugles” ou non) dont le sommet de Voronoi dual n’est pas visible depuis ce triangle, la visibilité étant bloquée par une ou plusieurs contraintes. Pour chaque sommet de Delaunay on peut ensuite construire sa cellule de Voronoi duale en circulant sur ses triangles incidents pour assembler des arêtes de Voronoi soit en reliant deux sommets de Voronoi dual de deux triangles successifs t1 et t2 (dans le cas général), soit en intersectant le segment de Voronoi dual de l’arête entre t1 et t2 avec l’arête de contrainte la plus proche (ou les deux arêtes de contrainte les plus proches) bloquant la visibilité (d’autres cas se produisent au bord de l’enveloppe convexe lorsque les arêtes de Voronoi sont des rayons ou des droites).
Dans la démo on devra pouvoir saisir des segments de contraintes et/ou les charger à partir d’un fichier texte.
Articles à lire: partie BVD de “Interleaving Delaunay Refinement and Optimization for 2D Triangle Mesh Generation”. Jane Tournois, Pierre Alliez and Olivier Devillers. 16th International Meshing Roundtable 2007: ftp://ftp-sop.inria.fr/geometrica/alliez/imr16-meshing.pdf
Codes et autres indications: La méthode décrite ci-dessus est naïve car effectue des tests exhaustifs sur les contraintes. En remarquant que l’ensemble des triangles aveugles est un ensemble de composantes connexes de triangles incidentes aux arêtes de contraintes, on peut pre-calculer le marquage des triangles aveugles en itérant sur les contraintes, et en propageant ledit marquage de triangle en triangle en partant d’un cote puis de l’autre de chaque contrainte. On peut en profiter pour stocker dans chaque triangle aveugle la contrainte qui bloque sa visibilité.
Codes et autres indications : Voir CGAL 2D Constrained Delaunay triangulations http://www.cgal.org/Manual/last/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_35.8
Sujet 10 : Interpolation de Sibson (voisins naturels) [Lucas Meyer]
L’interpolation par voisins naturels utilise les diagrammes de Voronoi, cf composant CGAL mentionné ci-dessous.
Expliquer le principe de cette méthode en dimension 2, et donner ses propriétés. Mettre en œuvre une version 2D avec CGAL (TP Delaunay 2D) qui visualise sous forme de terrain l’interpolation à partir de points de points 2D avec attribut d’altitude, ou sous forme de couleurs (RGB) à partir de points 2D avec attribut de couleur.
Articles à lire :
[1] R. Sibson. A brief Description of Natural Neighbour Interpolation, Interpreting Multivariate Data, Woley, 1981.
[2] G. Farin. Surfaces over Dirichlet Tesselations, CAGD, pages 281-292, 1990.
Codes et autres indications :
Voir CGAL 2D and Surface Function Interpolation.
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/packages.html#part_XIV
