Skip to Content

Delaunay Mesh Generation

By Siu-Wing Cheng, Tamal K. Dey, Jonathan Shewchuk

Chapman and Hall/CRC – 2012 – 410 pages

Series: Chapman & Hall/CRC Computer and Information Science Series

Purchasing Options:

  • Add to CartHardback: $93.95
    978-1-58488-730-0
    December 4th 2012

Description

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.

Contents

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.

Author Bio

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.

Name: Delaunay Mesh Generation (eBook)Chapman and Hall/CRC 
Description: By Siu-Wing Cheng, Tamal K. Dey, Jonathan Shewchuk. 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...
Categories: Algorithms & Complexity, Mechanics, Mathematics & Statistics for Engineers