Course 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 hang.si@wias-berlin.de

News

• [2019-07-01] Welcome to our first lecture on Monday, July 01, at 08:00, at F222, New Main Building, Address: No. 37 Xueyuan Road, Haidian District, Beijing, P.R. China, 100083.

Description

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:

• Introduction to mesh generation and applications.
• Overview of mesh generation methods developed in the last three decades.
• Introduction to classical mesh generation techniques: Delaunay-based, grid-based, octree-based, and advancing front.
• Introduction to freely available meshing, visualization, solid modeling softwares, such as Detri2, TetGen, Paraview, Blender, etc.
• Delaunay triangulations and constrained Delaunay triangulations.
• Delaunay tetrahedralizations and constrained Delaunay tetrahedralizations.
• Mesh quality and mesh validation.
• Adaptive mesh generation.
• Mesh improvement and optimization.
• Curve and surface mesh generation.
• Geometric primitives and numerical robustness.

Schedule

Literature

[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)

Softwares

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.

• Triangle, A two-dimensional Delaunay mesh generator.
• Gmsh, A three-dimensional finite element mesh generator with built-in pre- and post-processing facilities
• Paraview, an open-source, multi-platform data analysis and visualization application.
• Blender, an open-source, 3d modeling software.

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

• FreeFem++, an open-source, finite element software.

Home Work

Lecture Notes

1. General Information

This lecture gives an introduction about this course.

   

Topics

• Motivation examples.
• General information of this course.
• Rules of homework and oral presentations.
• Basic concepts in mesh generation.

Lecture notes

• Fundamentals.pdf

Further readings

• The Preface (PDF) and Chapter 1 (PDF) of the book [4] 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)

2. Triangulations in the Plane

This lecture introduces triangulations of point sets in the plane.

   

Topics

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

Lecture notes

Further readings

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

3. Triangular Mesh Generation and Adaptation

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

 

Topics

• Constrained triangulations.
• Edge recovery algorithms.
• Mesh quality measures.
• Delaunay refinement.
• Mesh improvement and adaptation techniques.

Lecture notes

• Mesh2d.pdf
• Chapter 2 (Section 2.2 and 2.3) of Edelsbrunner's book [1].

Further readings 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.
  

Further readings 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)

4. Software Implementation: Detri2

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

     

Topics

• Traingulation data structure.
• Local mesh modifications by flips.
• Spatial sorting techniques.
• Efficient Robust geometric predicates.
• Symbolic perturbations.

Lecture notes

Additional reading materials:

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