1st Edition
Delaunay Mesh Generation
Written by authors at the forefront of modern algorithms research, Delaunay Mesh Generation demonstrates the power and versatility of Delaunay meshers in tackling complex geometric domains ranging from polyhedra with internal boundaries to piecewise smooth surfaces. Covering both volume and surface meshes, the authors fully explain how and why these meshing algorithms work.
The book is one of the first to integrate a vast amount of cutting-edge material on Delaunay triangulations. It begins with introducing the problem of mesh generation and describing algorithms for constructing Delaunay triangulations. The authors then present algorithms for generating high-quality meshes in polygonal and polyhedral domains. They also illustrate how to use restricted Delaunay triangulations to extend the algorithms to surfaces with ridges and patches and volumes with smooth surfaces.
For researchers and graduate students, the book offers a rigorous theoretical analysis of mesh generation methods. It provides the necessary mathematical foundations and core theoretical results upon which researchers can build even better algorithms in the future.
For engineers, the book shows how the algorithms work well in practice. It explains how to effectively implement them in the design and programming of mesh generation software.
Introduction
Meshes and the goals of mesh generation
Delaunay triangulations and Delaunay refinement algorithms
A brief history of mesh generation
A personal history of working in mesh generation
Simplices, complexes, and polyhedra
Metric space topology
How to measure an element
Two-Dimensional Delaunay Triangulations
Triangulations of a planar point set
The Delaunay triangulation
The parabolic lifting map
The Delaunay Lemma
The flip algorithm
The optimality of the Delaunay triangulation
The uniqueness of the Delaunay triangulation
The weighted Delaunay triangulation
Symbolic weight perturbations
Constrained Delaunay triangulations in the plane
Algorithms for Constructing Delaunay Triangulations
The orientation and incircle predicates
A dictionary data structure for triangulations
Inserting a vertex into a Delaunay triangulation
Inserting a vertex outside a Delaunay triangulation
The running time of vertex insertion
Optimal point location by a conflict graph
The incremental insertion algorithm
Deleting a vertex from a Delaunay triangulation
Inserting or deleting a vertex in a CDT
Inserting a segment into a CDT
The gift-wrapping algorithm
Three-Dimensional Delaunay Triangulations
Triangulations of a point set in Rd
The Delaunay triangulation in Rd
The optimality of the Delaunay triangulation in Rd
Bistellar flips and the flip algorithm
Three-dimensional constrained Delaunay triangulations
Algorithms for Constructing Delaunay Triangulations in R3
A dictionary data structure for tetrahedralizations
Delaunay vertex insertion in R3
Biased randomized insertion orders
Optimal point location by a conflict graph in R3
Point location by walking
The gift-wrapping algorithm in R3
Inserting a vertex into a CDT in R3
Inserting a polygon into a CDT
Delaunay Refinement in the Plane
A generic Delaunay refinement algorithm
Ruppert’s Delaunay refinement algorithm
Implementation and running time
A proof of termination
A proof of size optimality and optimal grading
Meshing domains with small angles
Constrained Delaunay refinement
Voronoi Diagrams and Weighted Complexes
Voronoi diagrams
Weighted Voronoi and weighted Delaunay
Quarantined complexes
Tetrahedral Meshing of PLCs
A tetrahedral Delaunay refinement algorithm
Implementation and running time
A proof of termination and good grading
Refining slivers away
Constrained Delaunay tetrahedral refinement
Weighted Delaunay Refinement for PLCs with Small Angles
The ideas behind weighted Delaunay refinement
Protecting vertices and segments
The refinement stage
A proof of termination and good grading
Sliver Exudation
The main idea and the algorithm
Implementing sliver exudation
Properties of the union of weighted Delaunay triangulations
The Sliver Theorem
Refinement for Sliver Exudation
Enforcing domain conformity with uncertain vertex weights
A refinement algorithm for sliver exudation
A guarantee of domain conformity during sliver exudation
A proof of termination, good quality, and good grading
Finite triangulations and the Sliver Theorem
Smooth Surfaces and Point Samples
Topological spaces
Maps, homeomorphisms, and isotopies
Manifolds
Smooth manifolds
The medial axis and local feature size of a smooth manifold
The variation in normal vectors on smooth surfaces
Approximations of tangents by simplices
Restricted Delaunay Triangulations of Surface Samples
Restricted Voronoi diagrams and Delaunay triangulations
The Topological Ball Theorem
Distances and angles in ε-samples
Local properties of restricted Voronoi faces
Global properties of restricted Voronoi faces
The fidelity of the restricted Delaunay triangulation
Meshing Smooth Surfaces and Volumes
Delaunay surface meshing with a known local feature size
Topology-driven surface meshing
A practical surface meshing algorithm
Extensions: quality, smoothness, and polyhedral surfaces
Tetrahedral meshing of volumes bounded by smooth surfaces
Meshing Piecewise Smooth Complexes
Piecewise smooth complexes and their triangulations
An algorithm for meshing PSCs
The ball properties and the PSC Lemma
A proof of termination
Manifold patch triangulations and homeomorphism
Extensions: polygonal surfaces, quality, and tetrahedral
Bibliography
Index
Notes and Exercises appear at the end of each chapter.
Biography
Siu-Wing Cheng is a professor in the Department of Computer Science and Engineering at the Hong Kong University of Science and Technology. Professor Cheng is an advisory committee member of the International Symposium on Algorithms and Computation and a board member of the Asian Association for Algorithms and Computation. His research interests include computational geometry, mesh generation, manifold reconstruction, and algorithms. He earned a Ph.D. in computer science from the University of Minnesota, Twin Cities.
Tamal K. Dey is a professor of computer science at Ohio State University, where he leads the Jyamiti group, which develops software such as the well-known Cocone software for surface reconstruction and DelPSC software for mesh generation. He previously held faculty positions at Indiana University-Purdue University and IIT Kharagpur and research positions at the University of Illinois and Max-Planck Institute. His research interests include computational geometry and topology and their applications in graphics and geometric modeling. He earned a Ph.D. from Purdue University.
Jonathan Shewchuk is a professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He is best known for his Triangle software for high-quality triangular mesh generation, which won the 2003 James Hardy Wilkinson Prize in Numerical Software, and his paper "Introduction to the Conjugate Gradient Method without the Agonizing Pain." He received his Ph.D. in computer science from Carnegie Mellon University.
