Maillages et applications

École des Ponts ParisTech
Deuxième semestre 2016-2017 [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.

meshes-urban
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-alliez3
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

TPs C++ CGAL / Qt

Télécharger la machine virtuelle virtual box.

ou


Installation

En vue de préparer vos machines pour les TPs C++, suivez les instructions suivantes:

  • Installer CMake
  • Il faut ensuite installer et compiler soit Qt4 (testé avec 4.7) avec CGAL 4.3, soit Qt5 avec le dernier CGAL

– Sous Windows: voir depuis cette page
– Sous Linux: yum install cgal
– Sous mac: sudo port install cgal, sinon voir depuis cette page

Les TPs:

Envelopes convexes 2D et triangulation de Delaunay 2D (sous Qt 4.7)
Envelopes convexes 2D et triangulation de Delaunay 2D (sous Qt 5)

Detection de plans par croissance de regions

Segmentation de maillages