École des Ponts ParisTech
Deuxième semestre 2019-2020 [lundi 8h30-11h15]
Résumé
L’objectif de ce cours est de mettre en lumière le rôle prépondérant des maillages (de surfaces et 3D) pour la modélisation géométrique, la simulation et la visualisation. Le cours permettra aux élèves d’acquérir des connaissances théoriques et pratiques sur la génération de maillages 3D et de surfaces, le traitement de maillages de surfaces et la reconstruction de scènes 3D à partir de dispositifs de mesure (lasers, images). Pour la génération de maillage la priorité sera donnée aux approches basées sur les diagrammes de Voronoi et les triangulations de Delaunay, et procédant par filtrage, raffinement et optimisation. Pour la reconstruction de surfaces on abordera la fois des méthodes interpolantes s’appuyant sur les triangulations de Delaunay, et des méthodes variationnelles s’appuyant sur l’équation de Poisson ou le calcul de vecteurs propres. On étudiera également l’apport d’approches probabilistes basées sur de la géométrie stochastique. On s’attachera enfin à mettre chaque technique présentée dans un contexte applicatif comme la reconstruction 3D de scènes urbaines (voir figure) et le calcul scientifique pour la ville durable.
A l’issue de ce module les élèves maitriseront des structures de données fondamentales en géométrie algorithmique, comme les enveloppes convexes, les diagrammes de Voronoi et les triangulations. Ils auront eu une présentation d’algorithmes depuis leurs aspects théoriques (concepts géométriques sous-jacents, étude de complexité, terminaison) jusqu’à leur implantation au cours des TPs en utilisant le langage C++ et la bibliothèque de calcul géométrique CGAL.
Pour la vie professionnelle ce module permet aux étudiants de prendre du recul sur un aspect important de l’ingénierie numérique: la génération de maillages pour la simulation, et la modélisation de scènes 3D à partir de mesures laser ou d’images. Que ce soit pour une finalité calcul ou image (ingénierie ou multimédia), la géométrie devient une composante essentielle de la “boite à outils standard” de l’ingénieur.
Nuage de points sur un bâtiment généré par un système Lidar aéroporté (gauche) et une reconstruction correspondante sous forme d’un maillage adapté à la régularité de la scène (droite).
Intervenants
Pierre Alliez et Florent Lafarge, Inria Sophia Antipolis – Mediterranee
Supports de cours et lectures recommandees:
– Polygon Mesh Processing. Mario Botsch, Mark Pauly, Leif Kobbelt, Pierre Alliez, Bruno Levy. CRC press.
– Geometry and Topology for Mesh Generation. H. Edelsbrunner. Cambridge Univ. Press, Cambridge, England.
– Curve and Surface Reconstruction : Algorithms with Mathematical Analysis, T. Dey, Cambridge University Press.
– Delaunay Mesh Generation, Siu-Wing Cheng, Tamal Dey, Jonathan Shewchuk, CRC Press.
PROGRAMME DU MODULE :
- Motivations scientifiques et applicatives.
- Notions de base: enveloppe convexe, diagramme de Voronoi, triangulation de Delaunay.
- Génération de maillages isotropes (2D, surface, 3D) par filtrage et raffinement de Delaunay.
- Optimisation de maillages isotropes (2D, 3D) en termes de qualité en forme.
- Optimisation de maillages isotropes de surfaces en termes de qualité en forme puis en termes d’erreur d’approximation.
- Reconstruction de surfaces à partir de nuages de points.
- Classification de scènes urbaines à partir d’images aériennes et satellitaires.
- Reconstruction 3D de scènes urbaines à partir de mesures laser.
Modalites
7 cours de 2H30, dont 5 cours magistraux et 2 TPs sur machine.
Les TPs sont effectués en C++ avec la bibliothèque de calcul géométrique CGAL.
Agenda
- 10 février (Florent Lafarge)
- 24 février (Florent Lafarge)
- 2 mars (Pierre Alliez)
- 16 mars (Pierre Alliez), en distanciel / video
- Maillages par raffinement de Delaunay [video, format mp4, 50 mins, 600 Mo]
- Optimisation de maillages [video, format mp4, 47 minutes, 600 Mo]
- 23 mars (Florent Lafarge) avec AdobeConnect
- 25 mars (Florent Lafarge) avec AdobeConnect
- 30 mars (Pierre Alliez) avec AdobeConnect
- La bibliothèque C++ CGAL
- Projet CGAL
- Enveloppes convexes
- Triangulations 2D, 3D
- Maillages
- Traitement de nuages de points
- La bibliothèque C++ CGAL
TPs C++ CGAL / Qt
Machine virtuelle (virtual box):
- Installer virtual box
- Télécharger la machine virtuelle (lien) (1.6 Go!)
- Importer depuis virtual box, mot de passe “cgql”
- Pour tester: ouvrir le LX terminal depuis le bureau
- cd cgal/tps/2d-convex-hull/src
- cmake .
- make
- ./convex
Installation
En vue de préparer vos machines pour les TPs C++, suivez les instructions suivantes (attention: installez tout soit en 32 soit en 64 bits):
- Installer CMake
- installer Qt5 (open source, avec bibliothèques précompilées).
- installer CGAL. Suivant votre plateforme: vous trouverez de l’aide sur cette page. Attention: pour Windows il y a un tutorial dédié.
- installer boost. Prenez bien les binaires depuis cette page.