Triangulations, and more precisely meshes, are at the heart of many problems relating to a wide variety of scientific disciplines, and in particular numerical simulations of all kinds of physical phenomena. In numerical simulations, the functional spaces of approximation used to search for solutions are defined from meshes, and in this sense these meshes play a fundamental role. This strong link between meshes and functional spaces leads us to consider advanced simulation methods in which the meshes are adapted to the behaviors of the underlying physical phenomena. This book presents the basic elements of this vision of meshing.
These mesh adaptations are generally governed by a posteriori error estimators representing an increase of the error with respect to a size or metric. Independently of this metric of calculation, compliance with a geometry can also be calculated using a so-called geometric metric. The notion of mesh thus finds its meaning in the metric of its elements.
Table of Contents
Foreword ix
Introduction xi
Chapter 1. Metrics, Definitions and Properties 1
1.1. Definitions and properties 2
1.2. Metric interpolation and intersection 6
1.2.1. Metric interpolation 7
1.2.2. Metric intersection 13
1.3. Geometric metrics 14
1.3.1. Geometric metric for a curve 16
1.3.2. Geometric metric for a surface 17
1.3.3. Turning any metric into a geometric metric 23
1.4. Meshing metrics 23
1.5. Metrics gradation 24
1.6. Element metric 31
1.6.1. Metric of a simplicial element 31
1.6.2. Metric of a non-simplicial element 37
1.6.3. Metric of an element of arbitrary degree 38
1.7. Element shape and metric quality 38
1.8. Practical computations in the presence of a metric 46
1.8.1. Calculation of the length 46
1.8.2. The calculation of an angle, area or volume 49
Chapter 2. Interpolation Errors and Metrics 53
2.1. Some properties 54
2.2. Interpolation error of a quadratic function 55
2.3. Bézier formulation and interpolation error 62
2.3.1. For a quadratic function 63
2.3.2. For a cubic function 66
2.3.3. For a polynomial function of arbitrary degree 80
2.3.4. Error threshold or mesh density 85
2.4. Computations of discrete derivatives 86
2.4.1. The L2 double projection method 86
2.4.2. Green formula 88
2.4.3. Least square and Taylor 89
Chapter 3. Curve Meshing 93
3.1. Parametric curve meshing 95
3.1.1. Curve in R3 95
3.1.2. About metrics used and computations of lengths 99
3.1.3. Curve plotted on a patch 103
3.2. Discrete curve meshing 104
3.3. Remeshing a meshed curve 104
Chapter 4. Simplicial Meshing 107
4.1. Definitions 108
4.2. Variety (surface) meshing 109
4.2.1. Patch-based meshing 110
4.2.2. Discrete surface remeshing 119
4.2.3. Meshing using a volume mesher 120
4.3. The meshing of a plane or of a volume domain 122
4.3.1. Tree-based method 123
4.3.2. Front-based method 126
4.3.3. Delaunay-based method 129
4.3.4. Remeshing of a meshed domain 134
4.4. Other generation methods? 136
Chapter 5. Non-simplicial Meshing 141
5.1. Definitions 142
5.2. Variety meshing 143
5.3. Construction methods for meshing a planar or volume domain 145
5.3.1. Cylindrical geometry and extrusion method 147
5.3.2. Algebraic methods and block-based methods 148
5.3.3. Tree-based method 172
5.3.4. Pairing method 174
5.3.5. Polygonal or polyhedral cell meshing 176
5.3.6. Construction of boundary layers 177
5.4. Other generation methods 182
5.4.1. “Q-morphism” or “H-morphism” meshing 182
5.4.2. Meshing using a reference frame field 183
5.5. Topological invariants (quadrilaterals and hexahedra) 185
Chapter 6. High-order Mesh Construction 195
6.1. Straight meshes 196
6.1.1. Local node numbering 196
6.1.2. Overall node numeration 201
6.1.3. Node positions 204
6.1.4. On filling up matrices according to element degrees 207
6.2. Construction of curved meshes 208
6.2.1. First-degree mesh 209
6.2.2. Node creation 209
6.2.3. Deformation and validation 210
6.2.4. General scheme 211
6.3. Curved meshes on a variety, curve or surface 215
Chapter 7. Mesh Optimization 225
7.1. Toward a definition of quality 226
7.2. Optimization process 233
7.2.1. Global methods 233
7.2.1.1. Optimization of a cost function 233
7.2.1.2. Iterative relaxation of the position of vertices by duality (simplices) 234
7.2.1.3. Global optimization of the position of vertices (quadrilaterals and hexahedra) 235
7.2.2. Local operators and local methods 236
7.2.2.1. Vertex moves by barycentering 236
7.2.2.2. Vertex moves and Laplacian operator 237
7.2.2.3. Moving or removing vertices and flips by insertion or reinsertion 241
7.2.2.4. Edge flips 241
7.2.2.5. Cluster of edge flips 243
7.2.2.6. Edge or face flip by reinsertion 244
7.2.2.7. Edge slicing 244
7.2.2.8. Removal of an edge by merging 245
7.2.2.9. Metric field update 246
7.2.2.10. Topological and metric criteria 246
7.2.2.11. Strategies 246
7.3. Planar mesh 248
7.4. Surface mesh 250
7.5. Volume meshing 251
7.6. High-degree meshing 254
Chapter 8. Mesh Adaptation 265
8.1. Generic framework for adaptive computation, the continuous mesh 266
8.1.1. Duality between discrete and continuous geometric entities 267
8.1.2. Duality between discrete and continuous interpolation error 269
8.1.3. Discrete-continuous duality in one diagram 272
8.2. Optimal control of the interpolation error in Lp-norm 272
8.3. Generic scheme of stationary adaptation 279
8.3.1. Error estimators 282
8.3.2. Interpolation of solution fields 287
8.4. Unsteady adaptation 289
8.4.1. Space-time error estimators based on the characteristics of the solution 290
8.4.2. Extension of the error analysis for the fixed-point algorithm for unsteady mesh adaptation 291
8.4.3. Mesh adaptation for unsteady problems 292
8.4.4. Unsteady mesh adaptation targeted at a function of interest 294
8.4.5. Conservative interpolation of solution fields 295
8.5. Mobile geometry with or without deformation 297
8.5.1. General context of the adaptation for mobile and/or deformable geometries 297
8.5.2. ALE continuous optimal mesh minimizing the interpolation error in Lp-norm 298
8.5.3. Space-time error estimator for moving geometry problems 300
Chapter 9. Meshing and Parallelism 303
9.1. Renumbering via a filling curve 304
9.2. Parallelism: two memory paradigms and different strategies 307
9.3. Algorithm parallelization for mesh construction 312
9.4. Parallelization of a mesh construction process, partition then meshing 324
9.5. Mesh parallelization, meshing then partition 326
Chapter 10. Applications 331
10.1. Surface meshing 332
10.2. In computational fluid dynamics 334
10.3. Computational solid mechanics 341
10.4. Computational electromagnetism 345
10.5. Renumbering and parallelism 346
10.6. Other more exotic applications 349
Chapter 11. Some Algorithms and Formulas 353
11.1. Local numbering of nodes of high-order elements 354
11.2. Length computations etc., in the presence of a metric field 364
11.3. Quality 369
Conclusions and Perspectives 373
Bibliography 375
Index 387
