Delaunay Mesh Generation

Siu-Wing Cheng	Tamal Krishna Dey	Jonathan Richard Shewchuk
Hong Kong University of Science and Technology	The Ohio State University	University of California at Berkeley
-------------------------------------------------------------------	-------------------------------------------------------------------	-------------------------------------------------------------------

CRC Press, Boca Raton, Florida, December 2012. xii+375 pages.
Buy it from Taylor & Francis, from Amazon, or from Barnes & Noble.
Please send comments, questions, and errata to all three authors at

Our book is a thorough guide to Delaunay refinement algorithms that are mathematically guaranteed to generate meshes with high quality, including triangular meshes in the plane, tetrahedral volume meshes, and triangular surface meshes embedded in three dimensions. It is also the most complete guide available to Delaunay triangulations and algorithms for constructing them. We have designed the book for two audiences: researchers, especially graduate students, and engineers who design and program mesh generation software. Exercises are included; so is implementation advice.

Delaunay refinement algorithms for mesh generation construct meshes of triangles or tetrahedra (“elements”) that are suitable for applications like interpolation, rendering, terrain databases, geographic information systems, and most demandingly, the solution of partial differential equations by the finite element method. Delaunay refinement algorithms operate by maintaining a Delaunay or constrained Delaunay triangulation which is refined by inserting additional vertices until the mesh meets constraints on element quality and size. These algorithms offer theoretical bounds on element quality, edge lengths, and spatial grading of element sizes; topological and geometric fidelity to complicated domains, including curved domains with internal boundaries; and truly satisfying performance in practice.

The first third of the book lays out the mathematical underpinnings of Delaunay triangulations and the most practical algorithms for constructing them. The second third of the book describes Delaunay refinement algorithms for domains expressed as piecewise linear complexes, which model polygons and polyhedra but also support internal boundaries. The final third of the book describes Delaunay refinement algorithms for curved domains—specifically, smooth surfaces, volumes bounded by smooth surfaces, and piecewise smooth domains that have curved ridges and patches and are represented by piecewise smooth complexes.

The book has fifteen chapters, summarized below. Check out free samples of the Table of Contents and Preface (PDF, 198k, 13 pages), Chapter 1 (PDF, 708k, 30 pages), Chapter 2 (PDF, 286k, 24 pages), Chapter 9 (PDF, 472k, 17 pages), and Chapter 13 (PDF, 455k, 29 pages).

• 1. Introduction. Meshes and the goals of mesh generation; a brief history of mesh generation; simplices, complexes, and polyhedra; metric space topology; how to measure and judge elements.

• 2. Two-dimensional Delaunay triangulations. Triangulations and Delaunay triangulations of point sets; the parabolic lifting map; the Delaunay Lemma; the flip algorithm; the optimality and uniqueness of the Delaunay triangulation; weighted Delaunay triangulations; triangulations of polygons and piecewise linear complexes; piecewise linear complexes and constrained Delaunay triangulations.

• 3. Algorithms for constructing Delaunay triangulations. Geometric predicates; data structures; incremental vertex insertion algorithms and their analysis; inserting or deleting a vertex in a Delaunay triangulation or a constrained Delaunay triangulation; point location; inserting a segment into a constrained Delaunay triangulation; the gift-wrapping algorithm.

• 4. Three-dimensional Delaunay triangulations. Triangulations and Delaunay triangulations in higher dimensions; the optimality of higher-dimensional Delaunay triangulations; bistellar flips and the flip algorithm; three-dimensional constrained Delaunay triangulations; the CDT Theorem.

• 5. Algorithms for constructing Delaunay triangulations in R³. Data structures; incremental insertion in three dimensions and its analysis; biased randomized insertion orders; point location; gift-wrapping in three dimensions; inserting a vertex or a polygon into a constrained Delaunay triangulation.

• 6. Delaunay refinement in the plane. Delaunay refinement algorithms; Ruppert's algorithm for triangular mesh generation; implementation; guarantees of termination, good quality, size optimality, and optimal grading; domains with small angles; constrained Delaunay refinement.

• 7. Voronoi diagrams and weighted complexes. Voronoi diagrams; weighted Voronoi diagrams and weighted Delaunay triangulations; quarantined complexes.

• 8. Tetrahedral meshing of PLCs. Tetrahedral Delaunay refinement; implementation; guarantees of termination, good quality, and good grading; refining slivers away; constrained Delaunay tetrahedral refinement.

• 9. Weighted Delaunay refinement for PLCs with small angles. Principles of weighted Delaunay refinement; protecting vertices and segments; a weighted Delaunay refinement algorithm; guarantees of termination and good grading.

• 10. Sliver exudation. Principles of sliver exudation; implementation; the Sliver Theorem.

• 11. Refinement for sliver exudation. Encroachment rules; a weighted Delaunay refinement algorithm for sliver exudation; guarantees of domain conformity, termination, good quality, and good grading; revisiting the Sliver Theorem.

• 12. Smooth surfaces and point samples. Topological spaces; maps, homeomorphisms, and isotopies; manifolds; smooth manifolds; the medial axis and the local feature size; ε-samples of surfaces; approximation theory for well-sampled surfaces.

• 13. Restricted Delaunay triangulations of surface samples. Restricted Voronoi diagrams and restricted Delaunay triangulations; the Topological Ball Theorem; distances and angles in ε-samples; properties of restricted Voronoi faces; homeomorphism, isotopy, and geometric fidelity of restricted Delaunay triangulations of well-sampled surfaces.

• 14. Meshing smooth surfaces and volumes. Triangular Delaunay surface meshing with a known local feature size; topology-driven surface meshing; practical surface meshing; enforcing quality and smoothness; remeshing polyhedral surfaces; tetrahedral meshing of volumes bounded by smooth surfaces.

• 15. Meshing piecewise smooth complexes. Piecewise smooth complexes and their triangulations; protecting vertices and ridges; a Delaunay refinement algorithm for meshing PSCs; the PSC Lemma; guarantees of termination, good quality, and homeomorphism; enforcing quality; volume meshing.

Erratum