Meshing, Geometric Modeling and Numerical Simulation, Volume 2 Metrics, Meshes and Mesh Adaptation

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.

Paul Louis George is Director of Research at the French Institute for Research in Computer Science and Automation (Inria) and one of the most internationally recognized experts in meshing.

Houman Borouchaki is Professor at the University of Technology of Troyes (UTT) in France. He is an expert on meshing problems, geometric modeling and applications in solid mechanics.

Frédéric Alauzet is a researcher at Inria, both with particular expertise in meshing adaptation, error estimators, resolution methods (advanced solvers in fluid mechanics) and remeshing methods.

Adrien Loseille is a researcher at Inria, both with particular expertise in meshing adaptation, error estimators, resolution methods (advanced solvers in fluid mechanics) and remeshing methods.

Patrick Laug is a researcher at Inria with particular expertise in geometric modeling and the generation of curve and surface meshes.

Loïc Maréchal, a long-time collaborator at Inria as an engineer, is an essential reference on hexahedra.

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 L² 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 R³ 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 L^p-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 L^p-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

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.