An Introduction to Unstructured Mesh Generation Methods and Softwares for Scientific Computing

in the 2019 International Summer School in Beihang University

Course location: New Main Building F-222,
Address: No. 37 Xueyuan Road, Haidian District, Beijing, P.R. China, 100083

July 01 -- July 26, 2019

Beijing, China

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 Lecture Materials Home Work
July 1 08:00 -- 11:30 Introduction Lecture 1  
    What is mesh generation?
about this course,
incremental construction,
the convex hull problem
    Triangulations in the plane    
    Defnitions, simplicial complexes,
planar graphs, Euler's formula,
a sweepline algorithm
    Delaunay triangulations    
    Voronoi diagrams, empty circumcircle criterion
lifting transformation, the Delaunay lemma,
Lawson's flip algorithm
randomized incremental flip algorithm
    Software implementation    
    Triangle-based data structure, point location
spatial sorting, hilbert curve sorting
exact filtered predicates
    Triangular Mesh Generation and Adaptation    
    Constrained Delaunay triangulation,
quality mesh generation, Delaunay refinement,
mesh adaptation,
optimal Delaunay triangulation,
centroidal Voronoi tessellation
    Weighted Delaunay triangulations    
    Weighted points, weighted distance
Power diagram, orthogonality,
duality, regular subdivisons, Acyclic theorem
incremental flip construction
    Tetrahedral mesh generation and Adaptation    
    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    


[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] 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.

We will use freefem++ to illustrate the basics of finite element methods and mesh adptation

Home Work

Lecture Notes

1. General Information

This lecture gives an introduction about this course.



Lecture notes

Further readings

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

Further readings on constrained Delaunay triangulations

Further readings on Delaunay refinement

4. Software Implementation: Detri2

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



Lecture notes

Additional reading materials:

Hang Si, July 2019