Unstructured Mesh Generation, Algorithms and Softwares
DescriptionMesh 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:
ScheduleHere is the schedule for the course, tentative.
| What is mesh generation? |
about this course;
|Triangulations in the plane||Lecture 2|
| Convex hulls|
Definitions, simplicial complexes,
a sweepline algorithm
| further reading|
Jeff Ericson's notes on convex hull
| 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,
optimal Delaunay triangulation,
centroidal Voronoi tessellation
| Triangle-based data structure, point location |
spatial sorting, hilbert curve sorting
exact filtered predicates
|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
|Review and further topics|
 Herbert Edelsbrunner. Geometry and Topology for Mesh Generation, Cambridge University Press, 2001. ( link to publisher) (PDF)  Günter M. Ziegler. Lectures on Polytopes, Springer-Verlag, New York, 1995. (link to publisher)  J. A. De Loera, Jö Rambau, and F. Santos. Triangulations, Structures for Algorithms and Applications, Springer Verlag Berlin Heidelburg, 2010. (link to publisher)  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 )  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)  S.-W. Cheng and T. K. Dey and J. R. Shewchuk. Delaunay Mesh Generation. CRC Press, Boca Raton, FL. 2012. ( link to this book)  Y. Zheng and J. J. Chen. Unstructured Mesh Generation: Theories, Algorithms and Applications 03.2016.  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.
- Detri2 , A two-dimensional Delaunay mesh generator.
- TetGen, A three-dimensional Delaunay mesh generator.
The following (open source) softares will be used for visualization and comparison.
- HW1 (due 2018-12-02)
This lecture gives an introduction about this course.
- Motivation examples.
- General information of this course.
- Rules of homework and oral presentations.
- Basic concepts in mesh generation.
- A review of the historical development of mesh generation.
- A tutorial of softwares.
- General introduction
- Overview of unstructured methods
- The Preface (PDF) and Chapter 1 (PDF) of the book  edited by Bharat K. Soni, Joe F. Thompson, and Nigel P. Weatherill give a very comprehensive introduction about mesh generation and engineering methods.
- 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)
- Steve Owen, A Survey of Unstructured Mesh Generation Technology (PDF), Proceedings of 7th International Meshing Roundtable, 1998, 239-267.
- Steve Owen, An Introduction to Mesh Generation Algorithms ( PDF ), Short course, 14th International meshing roundtable, 2005.
- Daniel S. H. Lo. Finite Element Mesh Generation, CRC Press, Boca Raton, Florida 33431, January 2015. ( link to publisher)
- M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Computing in Euclidean Geometry, World Scientific, 1995, 47-123. ( PDF )
- M. Bern and P. Plassmann. Mesh generation. Chapter 6, Handbook of Computational Geometry, North-Holland, 2000, 291-332. ( PDF )
- Lecture notes of J. R. Shewchuk. (PDF) (Chapter 1, Introduction)
This lecture introduces triangulations of point sets in the plane.
- Simplexes and simplical complexes.
- Planar graph and Euler's formula.
- Incremental construction.
- Voronoi diagrams and Delaunay triangulations.
- Lawson's flip algorithm.
- Randomized incremental flip algorithm.
- Aurenhammer, F. Voronoi diagrams -- a study of fundamental geometric data structures, ACM Comput. Surveys, 1991, 23, 345-405. (PDF)
A very good survey paper about Viornoi and Delaunay.
- Guibas, L. J., Knuth, D. E. and Sharir, M. Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 1992, 7, 381-413. (PDF)
This is the original paper that presented the randomized incremental algorithm that will be discussed in this lecture.
- Fortune, S. Sweepline algorithm for Voronoi diagrams, Algorithmica, 1987, 2, 153-174. (PDF)
This is another classical algorithm that construct Voronij diagram and Delaunay triangulation. It has $O(n \log n)$ worst-case running time.
- Barber, C. B., Dobkin, D. P. and Huhdanpaa, H. T. The Quickhull algorithm for convex hulls, ACM Tranactions on Mathematical Software, 1996, 22, 469-483. (PDF)
Another incremental algorithm for constructing Voronoi and Delaunay triangulation. It is based on the lifting map principle.
- Devillers, O., Pion, S. and Teillaud, M. Walking in triangulation, International Journal of Foundations of Computer Science, 2002, 13, 181-199 (PDF)
A study about the simplest point location scheme.
- Su, P. and Drysdale, R. A Comparison of Sequential Delaunay Triangulation Algorithms, Comput. Geom. Theory Appl, ACM Comput. Geom. Theory Appl, 1996, 61-70 (PDF)
This lecture discusses triangular mesh generation and adaptation for 2d domains.
- Constrained triangulations.
- Edge recovery algorithms.
- Mesh quality measures.
- Delaunay refinement.
- Mesh improvement and adaptation techniques.
References on constrained Delaunay triangulations
- Lee, D. T. and Lin, A. K. Generalized Delaunay triangulations for planar graphs, Discrete and Computational Geometry, 1986, 1, 201-217 (PDF)
A classical paper (possibly the first paper) that introduces constrained Delaunay triangulation.
- Chew, L. P. Constrained Delaunay triangulations, Algorithmica, 1989, 4, 97-108 (PDF)
Another classical paper that introduces constrained Delaunay triangulation. It presents a fast $O(n \log n)$ algorithm to construct it.
- Seidel, R. Constrained Delaunay triangulations and Voronoi diagrams with obstacles 1978-1988 Ten Years IIG, 1988, 178-191
- Shewchuk, J. R. & Brown, B. C. Fast segment insertion and incremental construction of constrained Delaunay triangulations, Comput. Geom., 2015, 48, 554-574 (PDF) (Talk slides)
A recent paper about CDT construction.
- Shewchuk, J. R. Updating and Constructing Constrained Delaunay and Constrained Regular Triangulations by Flips, Proc. 19th Ann. Symp. on Comput. Geom., 2003, 86-95. (PDF) (Talk slides)
This is a 3d algorithm, but we will use its idea for constructing 2d planar constrained Delaunay triangulation.
References on Delaunay refinement
- Chew, L. P. Guaranteed-Quality Triangular Meshes, Dept. of Comp. Sci., Cornell University, 1989 (PDF)
One of the earliest Delaunay refinement algorithms. It guarantees minimum angle no less than 30 degree. It generates uniform sized Delaunay mesh.
- Ruppert, J. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation, Journal of Algorithms, 1995, 18, 548-585 (PDF)
One of the earliest Delaunay refinement algorithms. It guarantees minimum angle no less than 20.7 degree. It generates size-adapated Delaunay mesh. This is original algorithm that we will introduce in this lecture.
- Shewchuk, J. R. Delaunay refinement algorithms for triangular mesh generation, Computational Geometry Theory and applications, 2002, 22, 21-74 (PDF)
- Shewchuk, J. R. Theoretically Guaranteed Delaunay Mesh Generation--In Practice, International Meshing Roundtable, September 2005. (Talk slides).
- Miller, G. L., Pav, S. E. and Walkington, N. J. When and Why Ruppert's Algorithm Works, Proc. 12th International Meshing Roundtable, 2003, 91-102 (PDF)
- Pav, S. E. Delaunay Refinement Algorithm, Ph.D. thesis, PhD thesis, Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania, 2003
- Chernikov, A. N. and Chrisochoides, N. Generalized Insertion Region Guides for Delaunay Mesh Refinement, SIAM J. Scientific Computing, 2012, 34, A1333-A1350 (PDF)
This lecture discusses a software implementation of 2d triangular mesh generator Detri2.
- Traingulation data structure.
- Local mesh modifications by flips.
- Spatial sorting techniques.
- Efficient Robust geometric predicates.
- Symbolic perturbations.
- Shewchuk, J. R. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Applied Computational Geometry: Towards Geometric Engineering, Lin, M. C.\& Manocha, D. (Eds.) Springer, 1996, 1148, 203-222. (PDF)
- Guibas, L. and Stolfi, J. Primitives for the Manipulation of general subdivisions and the computation of Voronoi diagrams, ACM Transactions on Graphics, 1985, 4, 75-123 (PDF)
- Boissonnat, J.-D., Devillers, O., Pion, S., Teillaud, M. and Yvinec, M. Triangulatings in CGAL Computational Geometry, Theory and Applications, 2002, 22, 5-19 (PDF)
- Shewchuk, J. R. Robust Adaptive Floating-Point Geometric Predicates, Proceedings of the 12th Annual Symposium on Computational Geometry, 1996 (PDF)
- Devillers, O. and Pion, S. Efficient Exact Geometric Predicates for Delaunay Triangulations, 5th Workshop on Algorithm Engineering and Experiments (ALENEX), 2003, 37-44 (PDF)
- Edelsbrunner, H. and Mücke, E. P. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithm, ACM Transactions on Graphics, 1990, 9, 66-104 (PDF)