Unstructured Mesh Generation, Algorithms and Softwares

Hang Si
Research Group: Numerical Mathematics and Scientific Computing
Weierstrass Institute for Applied Analysis and Stochastics (WIAS)
Mohrenstr. 39, 10117 Berlin, Germany

Description | Schedule | Literature | Softwares | Lecture Notes | Home Work | FAQ |


Mesh generation finds numerous applications. To automatically generate suitable meshes for an arbitrary 2d and 3d domain is a very challenging task, and it has so far become a major bottleneck in applications. Mesh generation has evolved into an active field for research and development.

We offer a course introducing the theoretical background of mesh generation and the state-of-the-art methods and softwares for generating meshes for scientific computing. The aim of this course is to give the audience an introduction to the research and development in the field of mesh and grid generation. The audience will also learn to use some freely available meshing softwares which are based on the introduced methods. This will allow the audience to develop advanced methods or properly choose the right methods and tools in solving challenging engineering problems in scientific computing.

A main theme of this course is on the theory and algorithms of generating unstructured meshes, such as like triangular and tetrahedral meshes. They are well suited for complicated geometries, can be generated fully automatically, and are feasible for locally mesh adaption. Emphases are given on those methods which have solid theoretical background and good heuristics. Robust and efficient techniques for implementations are introduced.

The following topics will be covered in this course:


Here is the schedule for the course, tentative.
Date Time Topics Notes Codes Home Work
    Introduction Lecture 1    
    What is mesh generation?
about this course;
    Triangulations in the plane Lecture 2    
    Convex hulls
Definitions, simplicial complexes,
Euler's formula,
a sweepline algorithm
    Delaunay triangulations Lecture 2    
    Voronoi diagrams, empty circumcircle criterion
lifting transformation, the Delaunay lemma,
Lawson's flip algorithm
randomized incremental flip algorithm
    Triangular Mesh Generation and Adaptation Lecture 3    
    Constrained Delaunay triangulation,
quality mesh generation, Delaunay refinement,
mesh adaptation,
optimal Delaunay triangulation,
centroidal Voronoi tessellation
    Software implementation Lecture 3    
    Triangle-based data structure, point location
spatial sorting, hilbert curve sorting
exact filtered predicates
    Weighted Delaunay triangulations Lecture 5    
    Weighted points, weighted distance
Power diagram, orthogonality,
duality, regular subdivisons, Acyclic theorem
incremental flip construction
    Tetrahedral mesh generation and Adaptation Lecture 5    
    The Schoenhardt polyhedron, Steiner points
Constrained Delaunay tetrahedralisations,
Shewchuk's CDT theorem, incremental CDT algorithm
Delaunay refinement, sharp features
mesh adaptation
    Review and further topics Lecture 6    
    Further topics      


[1] Herbert Edelsbrunner. Geometry and Topology for Mesh Generation, Cambridge University Press, 2001. ( link to publisher) (PDF)
[2] Günter M. Ziegler. Lectures on Polytopes, Springer-Verlag, New York, 1995. (link to publisher)
[3] J. A. De Loera, Jö Rambau, and F. Santos. Triangulations, Structures for Algorithms and Applications, Springer Verlag Berlin Heidelburg, 2010. (link to publisher)
[4] Handbook of Grid Generation, edited by Bharat K. Soni, Joe F. Thompson, and Nigel P. Weatherill. CRC Press, Boca Raton, Florida 33431, 1999. (link to publisher )
[5] Pascal Jean Frey, Paul-Louis George. Mesh Generation: Application to Finite Elements, Second Edition , ISTE Ltd and John Wiley & Sons, Inc., London W1T 5DX and Hoboken, NJ 07030, 2008. ( link to publisher)
[6] S.-W. Cheng and T. K. Dey and J. R. Shewchuk. Delaunay Mesh Generation. CRC Press, Boca Raton, FL. 2012. ( link to this book)
[7] Y. Zheng and J. J. Chen. Unstructured Mesh Generation: Theories, Algorithms and Applications 03.2016.
[8] Daniel S. H. Lo. Finite Element Mesh Generation, CRC Press, Boca Raton, Florida 33431, January 2015. ( link to publisher)


This lecture will learn the following softwares for 2d and 3d mesh generation.

The following (open source) softares will be used for visualization and comparison.

Home Work

Lecture Notes

1. General Information

This lecture gives an introduction about this course.



Lecture notes


2. Triangulations in the Plane

This lecture introduces triangulations of point sets in the plane.



Lecture notes

Further readings


3. Triangular Mesh Generation and Adaptation

This lecture discusses triangular mesh generation and adaptation for 2d domains.



Lecture notes

References on constrained Delaunay triangulations

References on Delaunay refinement

4. Software Implementation: Detri2

This lecture discusses a software implementation of 2d triangular mesh generator Detri2.



Lecture notes


Hang Si, Sep 2018