Delaunay mesh generation

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... MJIIT Library	33000000000584	QA611.3 C43 2013	Open Access Book	Book	Searching... Unknown
Searching... PSZ JB	30000010328897	QA611.3 C43 2013	Open Access Book	Book	Searching... Unknown

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.

Author Notes

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.

Preface	p. xi
1 Introduction	p. 1
1.1 Meshes and the goals of mesh generation	p. 3
1.1.1 Domain conformity	p. 4
1.1.2 Element quality	p. 5
1.2 Delaunay triangulations and Delaunay refinement	p. 8
1.3 A brief history of mesh generation	p. 10
1.4 A personal history of working in mesh generation	p. 13
1.5 Simplices, complexes, and polyhedra	p. 16
1.6 Metric space topology	p. 19
1.7 How to measure an element	p. 22
1.8 Notes and exercises	p. 27
2 Two-dimensional Delaunay triangulations	p. 31
2.1 Triangulations of a planar point set	p. 31
2.2 The Delaunay triangulation	p. 32
2.3 The parabolic lifting map	p. 33
2.4 The Delaunay Lemma	p. 35
2.5 The flip algorithm	p. 37
2.6 The optimality of the Delaunay triangulation	p. 40
2.7 The uniqueness of the Delaunay triangulation	p. 41
2.8 The weighted Delaunay triangulation	p. 43
2.9 Symbolic weight perturbations	p. 45
2.10 Constrained Delaunay triangulations in the plane	p. 46
2.10.1 Piecewise linear complexes and their triangulations	p. 47
2.10.2 The constrained Delaunay triangulation	p. 50
2.10.3 Properties of the constrained Delaunay triangulation	p. 51
2.11 Notes and exercises	p. 52
3 Algorithms for constructing Delaunay triangulations	p. 55
3.1 The orientation and incircle predicates	p. 56
3.2 A dictionary data structure for triangulations	p. 58
3.3 Inserting a vertex into a Delaunay triangulation	p. 59
3.4 Inserting a vertex outside a Delaunay triangulation	p. 61
3.5 The running time of vertex insertion	p. 64
3.6 Optimal point location by a conflict graph	p. 66
3.7 The incremental insertion algorithm	p. 70
3.8 Deleting a vertex from a Delaunay triangulation	p. 71
3.9 Inserting or deleting a vertex in a CDT	p. 73
3.10 Inserting a segment into a CDT	p. 74
3.11 The gift-wrapping algorithm	p. 77
3.12 Notes and exercises	p. 80
4 Three-dimensional Delaunay triangulations	p. 85
4.1 Triangulations of a point set in Rd	p. 86
4.2 The Delaunay triangulation in Rd	p. 86
4.3 The optimality of the Delaunay triangulation in Rd	p. 89
4.4 Bistellar flips and the flip algorithm	p. 91
4.5 Three-dimensional constrained Delaunay triangulations	p. 95
4.5.1 Piecewise linear complexes and their triangulations in Rd	p. 96
4.5.2 The constrained Delaunay triangulation in R3	p. 98
4.5.3 The CDT Theorem	p. 100
4.5.4 Properties of the constrained Delaunay triangulation in R3	p. 101
4.6 Notes and exercises	p. 102
5 Algorithms for constructing Delaunay triangulations in R3.	p. 105
5.1 A dictionary data structure for tetrahedralizations	p. 106
5.2 Delaunay vertex insertion in R3	p. 106
5.3 Biased randomized insertion orders	p. 108
5.4 Optimal a conflict graph in R3	p. 110
5.5 Point location by walking	p. 113
5.6 The gift-wrapping algorithm in R3	p. 114
5.7 Inserting a vertex into a CDT in R3	p. 115
5.8 Inserting a polygon into a CDT	p. 115
5.9 Notes and exercises	p. 120
6 Delaunay refinement in the plane	p. 123
6.1 A generic Delaunay refinement algorithm	p. 124
6.2 Ruppert's Delaunay refinement algorithm	p. 126
6.3 Implementation and running time	p. 129
6.4 A proof of termination	p. 131
6.5 A proof of size optimality and optimal grading	p. 137
6.6 Meshing domains with small angles	p. 142
6.7 Constrained Delaunay refinement	p. 147
6.8 Notes and exercises	p. 148
7 Voronoi diagrams and weighted complexes	p. 153
7.1 Voronoi diagrams	p. 154
7.2 Weighted Voronoi and weighted Delaunay	p. 156
7.2.1 Properties of orthoballs	p. 159
7.3 Quarantined complexes	p. 161
7.3.1 The Monotone Power Lemma	p. 162
7.3.2 The Orthoball Cover Lemma	p. 163
7.3.3 The Orthocenter Containment Lemma	p. 165
7.4 Notes and exercises	p. 166
8 Tetrahedral meshing of PLCs	p. 169
8.1 A tetrahedral Delaunay refinement algorithm	p. 171
8.2 Implementation and running time	p. 176
8.3 A proof of termination and good grading	p. 177
8.4 Refining slivers away	p. 184
8.5 Constrained Delaunay tetrahedral refinement	p. 184
8.6 Notes and exercises	p. 185
9 Weighted Delaunay refinement for PLCs with small angles	p. 189
9.1 The ideas behind weighted Delaunay refinement	p. 190
9.2 Protecting vertices and segments	p. 191
9.3 The refinement stage	p. 195
9.4 A proof of termination and good grading	p. 197
9.5 Notes and exercises	p. 201
10 Sliver exudation	p. 207
10.1 The main idea and the algorithm	p. 208
10.2 Implementing sliver exudation	p. 210
10.3 The union of weighted Delaunay triangulations	p. 211
10.3.1 Orthoradius-edge ratios of tetrahedra in K(S, ¿)	p. 212
10.3.2 Circumradii of triangles in K(S, ¿)	p. 216
10.3.3 The variation of edge lengths in Del S and K(S, ¿)	p. 219
10.3.4 The degrees of vertices in K(S, ¿)	p. 221
10.4 The Sliver Theorem	p. 223
10.5 Notes and exercises	p. 226
11 Refinement for sliver exudation	p. 231
11.1 Domain conformity with uncertain vertex weights	p. 232
11.2 A refinement algorithm for sliver exudation	p. 233
11.3 A guarantee of domain conformity during sliver exudation	p. 235
11.4 A proof of termination, good quality, and good grading	p. 236
11.5 Finite triangulations and the Sliver Theorem	p. 240
11.6 Notes and exercises	p. 242
12 Smooth surfaces and point samples	p. 245
12.1 Topological spaces	p. 245
12.2 Maps, homeomorphisms, and isotopies	p. 247
12.3 Manifolds	p. 251
12.4 Smooth manifolds	p. 252
12.5 The medial axis and local feature size of a smooth manifold	p. 253
12.5.1 The medial axis	p. 254
12.5.2 Definition of the local feature size	p. 256
12.5.3 Point samples on manifolds	p. 257
12.5.4 Properties of a surface and its medial axis	p. 259
12.6 The variation in normal vectors on smooth surfaces	p. 261
12.7 Approximations of tangents by simplices	p. 264
12.7.1 Short edges are almost parallel to the surface	p. 264
12.7.2 Triangles with small circumradii are almost parallel	p. 266
12.8 Notes and exercises	p. 268
13 Restricted Delaunay triangulations of surface samples	p. 271
13.1 Restricted Voronoi diagrams and Delaunay triangulations	p. 272
13.2 The Topological Ball Theorem	p. 274
13.3 Distances and angles in ¿-samples	p. 276
13.4 Local properties of restricted Voronoi faces	p. 278
13.5 Global properties of restricted Voronoi faces	p. 289
13.6 The fidelity of the restricted Delaunay triangulation	p. 291
13.6.1 The nearest point map is a homeomorphism	p. 291
13.6.2 Proximity and isotopy	p. 293
13.6.3 Fidelity and dihedral angles of the discretized surface	p. 296
13.7 Notes and exercises	p. 298
14 Meshing smooth surfaces and volumes	p. 301
14.1 Delaunay surface meshing with a known local feature size	p. 302
14.1.1 Proof of termination and guarantees	p. 304
14.1.2 Deleting two vertices of the persistent triangle	p. 306
14.1.3 Computing edge-surface intersections	p. 307
14.2 Topology-driven surface meshing	p. 308
14.2.1 Diagnosing violations of the topological ball property	p. 308
14.2.2 A topology-driven Delaunay refinement algorithm	p. 313
14.2.3 Proof of termination and homeomorphism	p. 313
14.3 A practical surface meshing algorithm	p. 314
14.4 Extensions: quality, smoothness, and polyhedral surfaces	p. 318
14.5 Tetrahedral meshing of volumes with smooth boundaries	p. 322
14.5.1 Proof of termination and guarantees	p. 325
14.6 Notes and exercises	p. 329
15 Meshing piecewise smooth complexes	p. 333
15.1 Piecewise smooth complexes and their triangulations	p. 334
15.2 An algorithm for meshing PSCs	p. 335
15.2.1 Protection and the relaxed ball properties	p. 336
15.2.2 The protection stage	p. 338
15.2.3 Refining the protecting balls	p. 342
15.2.4 The refinement stage	p. 344
15.3 The ball properties and the PSC Lemma	p. 347
15.3.1 The ball properties	p. 347
15.3.2 The PSC Lemma	p. 350
15.3.3 Proof of the PSC Lemma	p. 352
15.4 A proof of termination	p. 356
15.5 Manifold patch triangulations and homeomorphism	p. 359
15.6 Extensions: polygonal surfaces, quality, and tetrahedra	p. 364
15.7 Notes and exercises	p. 364
Bibliography	p. 369
Index	p. 387

Available:*

On Order

Summary

Summary

Author Notes

Table of Contents