Grid Generation Methods (eBook)

Preface to the Second Edition 6
Contents 12
1 General Considerations 19
Introduction 19
General Concepts Related to Grids 20
Grid Cells 21
Requirements Imposed on Grids 23
Grid Size and Cell Size 23
Grid Organization 24
Cell and Grid Deformation 24
Consistency with Geometry 25
Consistency with Solution 25
Compatibility with Numerical Methods 27
Grid Classes 28
Structured Grids Generated by Mapping Approach 28
Realization of Grid Requirements 29
Coordinate Grids 30
Boundary-Conforming Grids 31
Shape of Computational Domains 32
Unstructured Grids 33
Block-Structured Grids 34
Communication of Adjacent Coordinate Lines 35
Topology of the Grid 35
Conditions Imposed on Grids in Blocks 37
Overset Grids 38
Hybrid Grids 39
Approaches to Grid Generation 39
Methods for Structured Grids 40
Algebraic Methods 40
Differential Methods 40
Variational Methods 41
Methods for Unstructured Grids 41
Octree Approach 41
Delaunay Approach 42
Advancing-Front Techniques 42
Big Codes 43
Interactive Systems 44
New Techniques 45
Domain Decomposition 45
New Methods 45
Comments 46
2 Coordinate Transformations 48
Introduction 48
General Notions and Relations 49
Jacobi Matrix 49
Tangential Vectors 50
Normal Vectors 52
Representation of Vectors Through the Base Vectors 53
Metric Tensors 55
Covariant Metric Tensor 55
Contravariant Metric Tensor 56
Geometric Interpretation 56
Relations Between Covariant and Contravariant Elements 57
Cross Product 58
Geometric Meaning 58
Relation to Volumes 59
Relation to Base Vectors 60
Relations Concerning Second Derivatives 61
Christoffel Symbols 61
Differentiation of the Jacobian 63
Basic Identity 64
Conservation Laws 66
Scalar Conservation Laws 66
Mass Conservation Law 67
Convection-Diffusion Equation 67
Laplace Equation 68
Vector Conservation Laws 68
Example 70
Time-Dependent Transformations 72
Reformulation of Time-Dependent Transformations 72
Basic Relations 73
Velocity of Grid Movement 73
Derivatives of the Jacobian 74
Basic Identity 75
Equations in the Form of Scalar Conservation Laws 75
Examples of Scalar Conservation-Law Equations 76
Parabolic Equation 76
Mass Conservation Law 77
Convection-Diffusion Equation 77
Energy Conservation Law 77
Linear Wave Equation 78
Lagrangian Coordinates 79
Equations in the Form of Vector Conservation Laws 79
Comments 83
3 Grid Quality Measures 84
Introduction 84
Curve Geometry 84
Basic Curve Vectors 85
Tangent Vector 85
Curves in Three-Dimensional Space 86
Curvature 87
Torsion 88
Surface Geometry 89
Surface Base Vectors 89
Metric Tensors 90
Covariant Metric Tensor 90
Contravariant Metric Tensor 91
Second Fundamental Form 92
Surface Curvatures 92
Principal Curvatures 92
Mean Curvature 93
Gaussian Curvature 94
Metric-Tensor Invariants 94
Algebraic Expressions for the Invariants 95
Geometric Interpretation 96
Characteristics of Grid Lines 97
Sum of Squares of Cell Edge Lengths 98
Eccentricity 98
Curvature 99
Local Straightness of the Coordinate Line 99
Expansion of the Curvature Vector in the Normal Vectors 100
Measure of Coordinate Line Curvature 101
Measure of Coordinate Line Torsion 102
Characteristics of Faces of Three-Dimensional Grids 102
Cell Face Skewness 102
Face Aspect-Ratio 103
Cell Face Area Squared 103
Cell Face Warping 104
Mean Curvature of the Coordinate Surface 104
Gaussian Curvature of the Coordinate Surface 105
Measures of Face Warping 105
Characteristics of Grid Cells 105
Cell Aspect-Ratio 106
Square of Cell Volume 106
Cell Area Squared 106
Cell Skewness 106
Characteristics of Nonorthogonality 107
Grid Density 108
Characteristics of Deviation from Conformality 109
Two-Dimensional Space 110
Evaluation of the Cell Angles 110
Evaluation of the Cell Aspect Ratio 111
Three-Dimensional Space 112
Generalization to Arbitrary Dimensions 113
Grid Eccentricity 113
Measures of Grid Warping and Grid Torsion 113
Quality Measures of Simplexes 114
Comments 115
4 Stretching Method 117
Introduction 117
Formulation of the Method 118
Theoretical Foundation 120
Model Problems 121
Basic Majorants 124
Relation Between Optimal Univariate Transformations and Majorants of the First Derivative 124
Exponential Functions 126
Power Singularities 127
Logarithmic Function 128
Relations Among Basic Majorants 128
Interior Layers 128
Estimates of the Higher Derivatives 130
Invariants of Equations 131
Basic Intermediate Transformations 132
Basic Local Stretching Functions 132
Width of Boundary Layers 134
Basic Boundary Contraction Functions 136
Basic Univariate Transformations 137
Continuous Mappings 138
Smooth Mappings 138
Other Univariate Transformations 141
Eriksson Function 141
Tangent Function 141
Procedure for the Construction of Local Contraction Functions 142
Construction of Basic Intermediate Transformations 143
Functions with Boundary Contraction 144
Functions with Interior Contraction 144
Clustering near Arbitrary Surfaces 145
Nonuniform Clustering 146
Comments 146
5 Algebraic Grid Generation 148
Introduction 148
Transfinite Interpolation 148
Unidirectional Interpolation 149
General Formulas 149
Two-Boundary Interpolation 150
Tensor Product 150
Boolean Summation 151
Bidirectional Interpolation 151
Three-Dimensional Interpolation 152
Recursive Form of Transfinite Interpolation 152
Outer Boundary Interpolation 153
Two-Dimensional Interpolation 153
Algebraic Coordinate Transformations 154
Formulation of Algebraic Coordinate Transformation 154
General Algebraic Transformations 156
Lagrange and Hermite Interpolations 158
Coordinate Transformations Based on Lagrange Interpolation 158
Lagrange Polynomials 159
Spline Functions 159
Construction Based on General Functions 160
Relations Between Blending Functions 161
Transformations Based on Hermite Interpolation 162
Construction of Blending Functions 163
Deficient Form of Hermite Interpolation 164
Specification of Normal Directions 164
Control Techniques 165
Transfinite Interpolation from Triangles and Tetrahedrons 166
Comments 168
6 Grid Generation Through Differential Systems 170
Introduction 170
Laplace Systems 172
Two-Dimensional Equations 173
Three-Dimensional Equations 176
Poisson Systems 179
Formulation of the System 180
Justification for the Poisson System 181
Equivalent Forms of the Poisson System 183
Orthogonality at Boundaries 185
Two-Dimensional Equations 186
Local Straightness at the Boundary 187
Three-Dimensional Equations 188
Projection of the Poisson System on the Boundary Curve 190
Control of the Angle of Intersection 192
Biharmonic Equations 196
Formulation of the Approach 196
Transformed Equations 197
Orthogonal Systems 197
Derivation from the Condition of Orthogonality 198
Multidimensional Equations 199
Hyperbolic and Parabolic Systems 200
Specification of Aspect Ratio 201
Initial-Value Problems 201
Specification of Jacobian 203
Orthogonal Grids in Two Dimensions 203
Two-Dimensional Nonorthogonal Grids 205
Three-Dimensional Version 205
Parabolic Equations 206
Hybrid Grid Generation Scheme 206
Comments 207
7 Dynamic Adaptation 209
Introduction 209
One-Dimensional Equidistribution 210
Example of an Equidistributed Grid 211
Original Formulation 213
Differential Formulation 214
Specification of Weight Functions 215
Optimally Distributed Grid 216
Equidistant Mesh 220
Utilization of the Second Derivative and Curvature 222
Equidistribution in Multidimensional Space 223
One-Directional Equidistribution 223
Multidirectional Equidistribution 224
Combination of One-Dimensional Equidistributions 224
Composition of Univariate Equidistributions 225
Control of Grid Quality 225
Equidistribution over Cell Volume 227
Adaptation Through Control Functions 230
Specification of the Control Functions in Elliptic Systems 230
Poisson System 230
Other Equations 231
Hyperbolic Equations 232
Grids for Nonstationary Problems 232
Method of Lines 233
Moving-Grid Techniques 233
Specification of Spatial Grid Distribution 233
Grid Movement Induced by Boundary Movement 234
Specification of Grid Speed 234
Time-Dependent Deformation Method 235
Comments 237
8 Variational Methods 241
Introduction 241
Calculus of Variations 241
General Formulation 242
Euler-Lagrange Equations 243
Functionals Dependent on Metric Elements 246
Functionals Dependent on Tensor Invariants 247
Two-Dimensional Tensor 247
Three-Dimensional Tensor 248
Convexity Condition 249
Integral Grid Characteristics 250
Dimensionless Functionals 250
Grid Skewness 250
Deviation from Orthogonality 251
Deviation from Conformality 252
Dimensionally Heterogeneous Functionals 254
Smoothness Functionals 254
Functionals of Orthogonality 254
Functionals Dependent on Second Derivatives 256
Functionals of Eccentricity 256
Functionals of Grid Warping and Grid Torsion 257
Adaptation Functionals 257
One-Dimensional Functionals 258
Multidimensional Approaches 259
Volume-Weighted Functional 260
Tangent-Length-Weigthed Functionals 261
Normal-Length-Weighted Functionals 261
Metric-Weighted Functionals 262
General Approach 263
Nonstationary Functionals 263
Weight Functions 264
Functionals of Attraction 264
Lagrangian Coordinates 264
Attraction to a Vector Field 266
Jacobian-Weighted Functional 267
Energy Functionals of Harmonic Function Theory 269
General Formulation of Harmonic Maps 269
Application to Grid Generation 270
Relation to Other Functionals 270
Combinations of Functionals 271
Natural Boundary Conditions 272
Comments 272
9 Curve and Surface Grid Methods 274
Introduction 274
Grids on Curves 275
Formulation of Grids on Curves 275
Grid Methods 277
Differential Approach 277
Variational Approach 278
Monitor Formulation 278
Formulation of Surface Grid Methods 279
Mapping Approach 279
Associated Metric Relations 281
Beltramian System 282
Beltramian Operator 282
Surface Grid System 283
Interpretations of the Beltramian System 285
Variational Formulation 285
Harmonic-Mapping Interpretation 286
Formulation Through Invariants 287
Formulation Through the Surface Christoffel Symbols 288
Surface Gauss Equations 288
Weingarten Equation 289
Mean Curvature 289
Relation Between Beltrami's Equation and Christoffel Symbols 290
Relation to Conformal Mappings 293
Projection of the Laplace System 295
Control of Surface Grids 296
Control Functions 296
Projection on the Boundary Line 297
Monitor Approach 298
Control by Variational Methods 299
Functionals Dependent on Invariants 300
Weight Skewness and Orthogonality Functionals 301
Weight Functions 301
Orthogonal Grid Generation 302
Hyperbolic Method 303
Hyperbolic Governing Equations 304
Comments 304
10 Comprehensive Method 306
Introduction 306
Hypersurface Geometry and Grid Formulation 308
Hypersurface Grid Formulation 308
Monitor Hypersurfaces 309
Metric Tensors 310
Christoffel Symbols 311
Relations Between Metric Elements 313
Functional of Smoothness 314
Formulation of the Functional 314
Geometric Interpretation 315
Dimensionless Functionals 317
Euler-Lagrange Equations 318
Equivalent Forms 320
Hypersurface Grid Systems 322
Inverted Beltrami Equations 322
Formulation of Comprehensive Grid Generator 324
Energy and Diffusion Functionals 324
Relation to Harmonic Functions 325
Beltrami and Diffusion Equations 326
Inverted Beltrami and Diffusion Equations 328
Numerical Algorithms 330
Finite-Difference Algorithm 331
One-Dimensional Equation 332
Two-Dimensional Equations 333
Three-Dimensional Equations 334
Spectral Element Algorithm 335
Formulation of Control Metrics 337
Specification of Individual Control Metrics 338
Control Metric for Generating Field-Aligned Grids 338
Control Metric for Generating Grids Adapting to the Values of a Function 339
Control Metrics for Generating Grids Adapting to the Gradient of a Function 341
Control Metrics for Generating Grids with Balanced Properties 342
Application to Solution of Singularly-Perturbed Equations 343
Comments 344
11 Unstructured Methods 346
Introduction 346
Consistent Grids and Numerical Relations 347
Convex Cells 347
Simplexes and Simplex Cells 348
Consistent Grids 348
Three-Dimensional Discretization 349
Discretization by Triangulation 350
Methods Based on the Delaunay Criterion 350
Dirichlet Tessellation 352
Incremental Techniques 352
A-Priori-Given Set of Points 353
Modernized Bowyer-Watson Technique 353
Approaches for Insertion of New Points 354
Two-Dimensional Approaches 355
Voronoi Diagram 355
Incremental Bowyer-Watson Algorithm 356
Properties of the Planar Delaunay Cavity 356
Initial Triangulation 358
Diagonal-Swapping Algorithm 358
Constrained Form of Delaunay Triangulation 359
Principal Component 359
Formulation of the Constrained Triangulation 360
Boundary-Conforming Triangulation 361
Point Insertion Strategies 361
Point Placement at the Circumcenter of the Maximum Triangle 362
Unconstrained Triangulation 362
Generalized Choice of the Insertion Triangles 364
Voronoi-Segment Point Insertion 364
Formulation of the Algorithm 364
Properties of the Triangulation 365
Surface Delaunay Triangulation 367
Three-Dimensional Delaunay Triangulation 367
Unconstrained Technique 368
Constrained Triangulation 368
Advancing-Front Methods 369
Procedure of Advancing-Front Method 369
Strategies to Select Out-of-Front Vertices 370
Grid Adaptation 371
Advancing-Front Delaunay Triangulation 371
Three-Dimensional Prismatic Grid Generation 372
Comments 373
References 376
Index 399