Meshing, Geometric Modeling and Numerical Simulation 3 Storage, Visualization and In Memory Strategies

In Volume 1, the theoretical foundations relating to triangulations, finite element shape functions and their interpretations as geometric patches were explored. This has made it possible to build tools that make the geometric modeling of any object possible. These elements are used in Volume 2 to treat meshing problems in their different implementations.

Meshing, Geometric Modeling and Numerical Simulation 3 offers technical additions to the methods seen in the first two volumes and a significant portion of this book is dedicated to mesh visualization problems and solutions, especially those with a high degree of complexity.

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

Frédéric Alauzet and Adrien Loseille are researchers at Inria, both with particular expertise in meshing adaptation, error estimators, solution methods (advanced solvers in fluid mechanics), remeshing methods and high order methods, among other things.

Loïc Maréchal is a long-time collaborator at Inria as an engineer and a leading authority on hexahedra. He is also an expert on data structures and problems related to memory management.

Foreword ix

Introduction xi

Chapter 1 Data and Basic Techniques 1

1.1 Basic data structures and basic techniques 1

1.1.1 Basic data structures 2

1.1.2 Basic techniques 22

1.2 Internal data structures 29

1.2.1 What should be stored in an internal structure and how? 29

1.2.2 Internal structures, method by method 31

1.3 External data structures 34

1.4 Data structures and memory access 36

Chapter 2 Mesh Transformations, Patching, Merging and Immersion 39

2.1 Geometric transformations 40

2.1.1 Conventional geometric transformations 40

2.1.2 Cutting a non-simplicial element into simplices 46

2.1.3 Decomposition into simplices of a non-simplicial mesh 48

2.1.4 Decompositions for a complying connection 56

2.1.5 Decomposition of a high-degree element 57

2.2 Reconnection 58

2.3 Merging 65

2.4 Immersion 77

Chapter 3 Renumbering and Memory 81

3.1 Vertex and node renumbering 82

3.1.1 Numbering and storage of a matrix in profile mode 82

3.1.2 Numbering and algorithm performance 84

3.1.3 Some methods for node renumbering 86

3.2 Renumbering of the elements 92

3.2.1 Motivation examples 92

3.2.2 Some methods for renumbering elements 92

3.2.3 Renumbering and mesh partition 94

3.3 Some examples 98

Chapter 4 High-Degree Mesh Visualization 105

4.1 Geometric operators and topological operators 106

4.1.1 Geometric operators 106

4.1.2 Topological operators 107

4.2 Representation of curved meshes 107

4.3 Quick introduction to OpenGL and to the design of a graphics software program 116

4.4 Some examples 136

Chapter 5 Visualization of a Solution Field Related to a High-Degree Mesh 145

5.1 Element recursive subdivision 146

5.2 Recursive subdivision of a solution field 152

5.3 Classic or adaptive tessellation 154

5.4 Toward the design of graphic software based on OpenGL 156

5.4.1 Palette definition 157

5.4.2 Cut definition 160

5.4.3 "Pixel-exact" or "almost pixel-exact" representation 169

5.4.4 Normals and shading 170

5.4.5 Level lines and surfaces and application to "wireframe" plots 171

5.4.6 Representation of non-scalar functions 176

5.4.7 Simplified scheme for a graphic software program 177

5.5 Some examples 181

Chapter 6 Meshes and Finite Element Calculations 185

6.1 From continuous formulation to discrete notation 187

6.2 Calculation of an elementary matrix 189

6.2.1 The special case of the first-degree triangle 190

6.2.2 A generic notation for all elements 191

6.2.3 The generic notation for the four chosen elements and heat equation 197

6.2.4 Lagrange triangle of degree 1 with three nodes 197

6.2.4.1 Lagrange quadrilateral of degree 1 × 1 with four nodes 201

6.2.4.2 Straight-sided Lagrange triangle of degree 2 with six nodes 209

6.2.4.3 Lagrange isoparametric (curved) triangle of degree 2 with six nodes 218

6.2.4.4 In practice 230

6.2.5 The generic notation for the four chosen elements, elasticity equation 233

6.2.6 Lagrange triangle of degree 1 with three nodes 233

6.2.6.1 The other three elements 235

6.2.6.2 In practice 235

6.3 Matrix or right-hand side assembly 237

Chapter 7 Meshes and Finite Volume Calculation 243

7.1 Presentation of the finite volume method with a first-order problem 243

7.1.1 Time discretization 244

7.1.2 Spatial discretization 245

7.2 Finite volume methods for two-dimensional Euler equations 249

7.2.1 Spatial discretization 250

7.2.1.1 Finite volume cell definition 251

7.2.1.2 Calculation of upwind conservative fluxes 252

7.2.2 Time discretization 256

7.3 From theory to practice 257

7.3.1 Data structures 257

7.3.2 Resolution algorithms 259

7.4 Numerical examples 260

Chapter 8 Examples Through Practice 265

8.1 Reading, writing and manipulating a mesh 266

8.2 Programming a hashing algorithm 269

8.3 One point insertion operator per cavity, application to image compression 272

8.4 Retrieving a connected component 281

8.5 Exercises on metrics 283

Chapter 9 Some Algorithms and Formulas 293

9.1 Bernstein polynomials and Bézier forms 293

9.1.1 Bernstein polynomials 293

9.1.2 Bézier forms 294

9.1.3 Formulas (lengths, surface areas and volumes) for curved elements 296

9.2 Localization problems in a curved mesh 301

9.2.1 Current point parameter values 301

9.2.2 Localization 305

9.3 Space-filling curves 306

9.3.1 A Z-curve 306

9.3.2 A Hilbert curve 309

Conclusion and Perspectives 313

Bibliography 315

Index 319

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.