Mesh Generation

Mesh Generation......Page 5
Contents......Page 7
Introduction......Page 13
Symbols and Notations......Page 19
1 General Definitions......Page 21
1.1 Covering-up and triangulation......Page 22
1.2 Mesh. mesh element. finite element mesh......Page 26
1.3 Mesh data structures......Page 33
1.4 Control space and neighborhood space......Page 41
1.5 Mesh quality and mesh optimality......Page 43
2 Basic Structures and Algorithms......Page 47
2.1 Why use data structures?......Page 48
2.2 Elementary structures......Page 50
2.3 Basic notions about complexity......Page 55
2.4 Sorting and searching......Page 58
2.5 One-dimensional data structures......Page 64
2.6 Two and three-dimensional data structures......Page 71
2.7 Topological data structures......Page 76
2.8 Robustness......Page 79
2.9 Optimality of an implementation......Page 82
2.10 Examples of generic algorithms......Page 85
3 A Comprehensive Survey of Mesh Generation Methods......Page 97
3.1 Classes of methods......Page 98
3.2 Structured mesh generators......Page 99
3.2.1 Algebraic interpolation methods......Page 100
3.2.2 PDE-based methods......Page 102
3.2.3 Multiblock method......Page 103
3.2.4 Product method (topology-based method)......Page 105
3.3 Unstructured mesh generators......Page 106
3.3.1 Spatial decomposition methods......Page 108
3.3.2 Advancing-front method......Page 111
3.3.3 Delaunay technique......Page 116
3.3.4 Tentative comparison of the three classical methods......Page 119
3.3.5 Other methods......Page 121
3.4.1 Mesh generation via a parametric space......Page 124
3.4.2 Implicit surface triangulation......Page 126
3.4.3 Direct surface meshing......Page 127
3.4.4 Surface remeshing......Page 128
3.5 Mesh adaptation......Page 130
3.6 Parallel unstructured meshing......Page 131
4.1 Algebraic methods......Page 135
4.1.1 Trivial mapping functions......Page 136
4.1.2 Quadrilateral or triangular analogy......Page 137
4.1.3 Surface meshing......Page 145
4.1.4 Hexahedral, pentahedral or tetrahedral analogy......Page 146
4.1.5 Other algebraic methods and alternative methods......Page 149
4.2.1 Basic ideas......Page 151
4.3.1 Basic ideas......Page 155
4.3.2 Partitioning the domain......Page 156
4.3.3 Computational issues and application examples......Page 157
5 Quadtree-octree Based Methods......Page 165
5.1 Overview of spatial decomposition methods......Page 166
5.2 Classical tree-based mesh generation......Page 173
5.3 Governed tree-based method......Page 191
5.4 Other approaches......Page 194
5.5 Extensions......Page 197
6 Advancing-front Technique for Mesh Generation......Page 203
6.1 A classical advancing-front technique......Page 205
6.2 Governed advancing-front method......Page 222
6.3 Application examples......Page 227
6.4 Combined approaches......Page 229
6.5 Extensions......Page 232
7 Delaunay-based Mesh Generation Methods......Page 237
7.1 Voronoï diagram and Delaunay triangulation......Page 238
7.2.1 Maintaining a constrained entity......Page 247
7.2.2 Enforcing a constraint......Page 248
7.3 Classical Delaunay meshing......Page 252
7.3.1 Simplified Delaunay type triangulation method......Page 254
7.3.2 Boundary integrity and domain identification......Page 256
7.3.3 Field point creation......Page 257
7.3.4 Optimization......Page 259
7.3.5 Practical issues......Page 260
7.3.6 Application examples......Page 261
7.4 Other methods......Page 263
7.4.2 Field point creation......Page 264
7.4.3 Boundary enforcement......Page 265
7.5 Isotropic governed Delaunay meshing......Page 266
7.6 Extensions......Page 269
7.6.2 Anisotropic Delaunay meshing......Page 270
7.6.3 Surface meshing......Page 275
8 Other Types of Mesh Generation Methods......Page 277
8.1 Product method......Page 278
8.2 Grid or pattern-based methods......Page 282
8.3 Optimization-based method......Page 285
8.4 Quads by means of triangle combination......Page 292
8.5 Quads by means of a direct method......Page 298
8.6 Hex meshing......Page 300
8.7 Miscellaneous......Page 302
9 Delaunay Admissibility. Medial Axis and Applications......Page 305
9.1 Delaunay-admissible set of segments in R2......Page 306
9.2 Delaunay-admissible set of segments in R3......Page 312
9.3 Delaunay-admissible set of triangular faces......Page 314
9.4 Medial axis......Page 320
9.5 Mid-surface......Page 327
9.6 Applications......Page 328
10 Quadratic Forms and Metrics......Page 333
10.1 Bilinear and quadratic forms......Page 334
10.2 Distances and lengths......Page 339
10.3 Metric-based operations......Page 344
10.4 Metric construction......Page 352
10.4.1 Parametric surface meshing......Page 353
10.4.2 Finite element simulation with error control......Page 354
11 Differential Geometry......Page 363
11.1 Metric properties of curves and arcs......Page 364
11.2 Metric properties of a surface......Page 379
11.3 Computational issues about surfaces......Page 389
11.4 Non-linear problems......Page 394
12 Curve Modeling......Page 397
12.1 Interpolation and smoothing techniques......Page 399
12.2 Lagrange and Hermite interpolation......Page 402
12.3 Explicit construction of a composite curve......Page 406
12.4 Control polygon based methods......Page 408
12.5 Béier curves......Page 411
12.6 From composite curves to B-splines......Page 416
12.7 Rational curves......Page 425
12.8 Curve definitions and numerical issues......Page 429
12.9 Towards a “pragmatic” curve definition?......Page 433
13 Surface Modeling......Page 437
13.1 Specific surfaces......Page 438
13.2 Interpolation-based surfaces......Page 439
13.3 Tensor product and control polyhedron......Page 444
13.4 Triangular patches and Bézier triangles......Page 448
13.5 Other types of patches......Page 452
13.6 Composite surfaces......Page 454
13.7 Explicit construction of a composite surface......Page 459
14 Curve Meshing......Page 465
14.1 Meshing a segment......Page 466
14.2 Meshing a parametric curve......Page 473
14.3 Curve meshing using a discrete definition......Page 485
14.4 Re-meshing algorithm......Page 488
14.5 Curves in R3......Page 490
15 Surface Meshing and Re-meshing......Page 493
15.1 Curve meshing (curve member of a surface)......Page 494
15.2 First steps in surface meshing......Page 495
15.3 A single patch......Page 505
15.4 Multi-patches surface (patch-dependent)......Page 515
15.5 Multi-patches surface (patch-independent)......Page 517
15.6 Ill-defined multi-patches surface......Page 519
15.7 Molecular surfaces......Page 521
15.8 Surface reconstruction......Page 523
15.9 Discrete surface (re-meshing process)......Page 525
16 Meshing Implicit Curves and Surfaces......Page 529
16.1 Review of implicit functions......Page 530
16.2 Implicit function and meshing......Page 535
16.3 Implicit curve meshing......Page 539
16.4 Implicit surface meshing......Page 547
16.5 Extensions......Page 558
17.1 Mesh (geometric) modifications......Page 561
17.2 Merging two meshes......Page 569
17.3 Node creation and node labeling......Page 575
17.4 Renumbering issues......Page 579
17.5 Miscellaneous......Page 589
18 Mesh Optimization......Page 593
18.1 About element measurement......Page 594
18.2 Mesh quality (classical case)......Page 598
18.3 Mesh quality (isotropic and anisotropic case)......Page 604
18.4 Tools for mesh optimization......Page 608
18.5 Strategies for mesh optimization......Page 619
18.6 Computational issues......Page 620
18.7 Application examples......Page 621
19 Surface Mesh Optimization......Page 625
19.1 Quality measures......Page 626
19.2 Discrete evaluation of surface properties......Page 634
19.3 Constructing a geometric support......Page 645
19.4 Optimization operators......Page 647
19.5 Optimization methods......Page 656
19.6 Application examples......Page 658
20 A Touch of Finite Elements......Page 665
20.1 Introduction to a finite element style computation......Page 666
20.2 Definition and first examples of finite elements......Page 670
20.3 Error estimation and convergence......Page 674
20.4 Stiffness matrix and right-hand side......Page 679
20.5 A few examples of popular finite elements......Page 692
21 Mesh Adaptation and H-methods......Page 695
21.1 Control space (background mesh)......Page 696
21.2 Adaptation by local modifications......Page 703
21.3 Global isotropic adaptation method......Page 710
21.4 Global anisotropic adaptation method......Page 718
21.5.1 General framework of a local adaptation method......Page 724
21.5.2 General framework of a global adaptation method......Page 726
21.6 Application examples......Page 729
22 Mesh Adaptation and P or Hp-methods......Page 737
22.1 P2 mesh......Page 738
22.2 P-compatibility......Page 744
22.3 Construction of P2 elements......Page 749
22.4 Elements of higher degree......Page 752
22.5 P-methods and hp-methods......Page 753
23 Moving or Deformable Meshing Techniques......Page 755
23.1 Rigid body motion......Page 756
23.2 ALE methods......Page 760
23.3 Mesh deformation......Page 766
23.4 Interface tracking......Page 769
24 Parallel Computing and Meshing Issues......Page 777
24.1 Partition of a domain......Page 778
24.2 Parallel meshing process......Page 792
24.3 Parallel meshing techniques......Page 794
Bibliography......Page 801
Index......Page 845