Course info

Authors: Jean Daniel Boissonnat and Mariette Yvinec.

Level: Advanced.

Prerequisites: Basic knowledge in computer science and computational geometry.

Description:

Many applications in various different domains like scientific computing, robotics, CAD-CAM, geometric modelisation or medical imagis, require a discretization of the objects under study or of their boundaries. Unstructured simplicial meshes (made of triangles in 2D and tetrahedra in 3D ) are widely used discretizations because of their flexibility to adapt to complex geometries. This course proposes an introduction to the field of unstructured simplicial mesh generation,covering 2D and 3D volume meshes generation as well as the generation of surface meshes to approximate or reconstruct surfaces. The material presented here is especially focused on methods based on Delaunay refinement because of their ability to offer guaranteed results.

Format: Slides in pdf-format.

Bibliography:

• 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.

• J. Shewchuk. Delaunay Refinement Algorithms for Triangular Mesh Generation, Computational Geometry: Theory and Applications 22(1-3):21-74, May 2002. PostScript (5,128k, 54 pages)

• M. Bern and D. Eppstein. Mesh generation and optimal triangulation. In Computing in Euclidean Geometry. D.Z. Du and F.K. Hwang editors, World Scientific, 2nd edition, 1995.

• What is a good linear finite element? Interpolation, conditioning, anisotropy and quality measures. unpublished preprint, 2002. Available from J. Shewchuk web page.

Course material

Here

• Basic tools: convex hulls and polytopes, triangulations, Delaunay triangulations and Voronoi diagrams, Laguerre diagrams. Lecture notes
• Constrained and Delaunay constrained triangulations Slides
• Delaunay refinement meshing in 2D Slides and 3D Slides
• Other meshing methods. Quality of meshes for interpolation and finite elements applications. Slides
• Surfaces meshes and surface reconstruction Lecture notes