Triangulations, maillages et modélisation géométrique

Résumé :
De nombreuses applications, dans des domaines aussi variés que le calcul scientifique, la robotique, la CAO, la modélisation géométrique ou l'imagerie médicale, reposent sur une discrétisation des objets étudiés ou de leur frontières. Les maillages simpliciaux non structurés (formés de tétraèdres en 3d et de triangles en 2d) constituent l'un des outils les plus utilisés. Ce cours propose une introduction aux problèmes de la génération de maillages volumiques (en 2d et 3d), de l'approximation et de la reconstruction de surfaces. Le cours privilégie les solutions basées sur les diagrammes de Voronoi et les triangulations de Delaunay qui offrent des résultats certifiés.

Triangulations et maillages (M. Yvinec) :
- Présentation
- Enveloppe convexe et polytopes~: Combinatoire, dualité, théorème de la borne supérieure. Algorithmique de l'enveloppe convexe
- Triangulations et diagrammes de Voronoi: Complexes simpliciaux. Complexite des triangulations en dimension 2 et 3. Diagrammes de Voronoi, Triangulation de Delaunay, espace des sphères. Diagrammes de puissance et triangulations régulières.
- Triangulations contraintes: Condition d'existence et construction des triangulations contraintes. Optimalité des triangulations Delaunay contraintes.
- Maillages 1 et Maillages 2: Introduction aux maillages. Maillages par raffinement de Delaunay. La méthode de Ruppert en dimension 2 et 3.
- Maillages 3: Autres méthodes de maillages. Evaluation des maillages et critères de qualité. Introduction la méthode des éléments finis.
Maillage de surfaces (J-D. Boissonnat)
- Présentation
- Echantillonnage de surfaces. Triangulation de Delaunay restreinte. Propriétés géométriques et topologiques. Algorithme de maillage.
- Axe médian, homotopie, stabilité, approximation. Flot dans un diagramme de Voronoi.
- Reconstruction de surface. Interpolation de données non structurés. Voisins naturels. Moindres carrés glissant (MLS moving least square).

Bibliographie :
* M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, Germany, 2nd edition, 2000.
* J-D. Boissonnat and M. Yvinec. Algorithmic Geometry. Cambridge University Press, UK, 1998. Translated by Hervé Brönnimann.
* E. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge, 2001.

Mariette Yvinec

Last modified: Thu Jan 6 13:56:45 CET 2005