Meshing, Geometric Modeling and Numerical Simulation 1: Form Functions, Triangulations and Geometric Modeling

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 the 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 meshing vision.

Table of Contents:
Foreword 9 Introduction 11 Chapter 1 Finite Elements and Shape Functions 15 1.1. Basic concepts 15 1.2. Shape functions, complete elements 18 1.2.1. Generic expression of shape functions 18 1.2.2. Explicit expression for degrees 1–3 22 1.3. Shape functions, reduced elements 26 1.3.1. Simplices, triangles and tetrahedra 27 1.3.2. Tensor elements, quadrilateral and hexahedral elements 31 1.3.3. Other elements, prisms and pyramids 48 1.4. Shape functions, rational elements 49 1.4.1. Rational triangle with a degree of 2 or arbitrary degree 49 1.4.2. Rational quadrilateral of an arbitrary degree 50 1.4.3. General case, B-splines or Nurbs elements 50 Chapter 2 Lagrange and Bézier Interpolants 53 2.1. Lagrange–Bézier analogy 54 2.2. Lagrange functions expressed in Bézier forms 55 2.2.1. The case of tensors, natural coordinates 55 2.2.2. Simplicial case, barycentric coordinates 63 2.3. Bézier polynomials expressed in Lagrangian form 66 2.4. Application to curves 66 2.4.1. Bézier expression for a Lagrange curve 67 2.4.2. Lagrangian expression for a Bézier curve 70 2.5. Application to patches 71 2.5.1. Bézier expression for a patch in Lagrangian form 71 2.5.2. Lagrangian expression for a patch in Bézier form 73 2.6. Reduced elements 74 2.6.1. The tensor case, Bézier expression for a reduced Lagrangian patch 74 2.6.2. The tensor case, definition of reduced Bézier patches 82 2.6.3. The tensor case, Lagrangian expression of a reduced Bézier patch 90 2.6.4. The case of simplices 92 Chapter 3 Geometric Elements and Geometric Validity 95 3.1. Two-dimensional elements 96 3.2. Surface elements 105 3.3. Volumetric elements 105 3.4. Control points based on nodes 111 3.5. Reduced elements 115 3.5.1. Simplices, triangles and tetrahedra 115 3.5.2. Tensor elements, quadrilaterals and hexahedra 116 3.5.3. Other elements, prisms and pyramids 120 3.6. Rational elements 121 3.6.1. Shift from Lagrange rationals to Bézier rationals 121 3.6.2. Degree 2, working on the (arc of a) circle 121 3.6.3. Application to the analysis of rational elements 123 3.6.4. On the use of rational elements or more 138 Chapter 4 Triangulation 141 4.1. Triangulation, definitions, basic concepts and natural entities 142 4.1.1. Definitions and basic concepts 142 4.1.2. Natural entities 145 4.1.3. A ball (topological) of a vertex 145 4.1.4 A shell of a k-face 145 4.1.5 The ring of a k-face 146 4.2. Topology and local topological modifications 146 4.2.1. Flipping an edge in two dimensions 148 4.2.2. Flipping a face in three dimensions 148 4.2.3. Flipping an edge in three dimensions 148 4.2.4. Other flips? 150 4.3. Enriched data structures 151 4.3.1. Minimal structure 151 4.3.2. Enriched structure 152 4.4. Construction of natural entities 153 4.5. Triangulation, construction methods 156 4.6. The incremental method, a generic method 159 4.6.1. Naive triangulation 160 4.6.2. Delaunay triangulation 163 Chapter 5 Delaunay Triangulation 165 5.1. History 166 5.2. Definitions and properties 168 5.3. The incremental method for Delaunay 175 5.4. Other methods of construction 181 5.5. Variants 186 5.6. Anisotropy 188 Chapter 6 Triangulation and Constraints 193 6.1. Triangulation of a domain 194 6.1.1. Triangulation of a domain in two dimensions 195 6.1.2. Triangulation of a domain in three dimensions 202 6.2. Delaunay Triangulation “Delaunay admissibility” 214 6.3. Triangulation of a variety 219 6.4. Topological invariants (triangles and tetrahedra) 222 Chapter 7 Geometric Modeling: Methods 233 7.1. Implicit or explicit form (CAD), starting from an analytical definition 234 7.1.1. Modeling an implicit curve, continuous → discrete 234 7.1.2. Modeling a parametric curve 237 7.1.3. Modeling an implicit surface 238 7.1.4. Modeling of a parametric surface 242 7.2. Starting from a discretization or triangulation, discrete → continuous 246 7.2.1. Case of a curve 247 7.2.2. The case of a surface 253 7.3. Starting from a point cloud, discrete → discrete 278 7.3.1. The case of a curve in two dimensions 278 7.3.2. The case of a surface 283 7.4. Extraction of characteristic points and characteristic lines 302 Chapter 8 Geometric Modeling: Examples 305 8.1. Geometric modeling of parametric patches 306 8.2. Characteristic lines of a discrete surface 311 8.3. Parametrization of a surface patch through unfolding 311 8.4. Geometric simplification of a surface triangulation 324 8.5. Geometric support for a discrete surface 325 8.6. Discrete reconstruction of a digitized object or environment 330 Chapter 9 A Few Basic Algorithms and Formulae 343 9.1. Subdivision of an entity (De Casteljau) 344 9.1.1. Subdivision of a curve 344 9.1.2. Subdivision of a patch 345 9.2. Computing control coefficients (higher order elements) 348 9.3. Algorithms for the insertion of a point (Delaunay) 351 9.3.1. Classic algorithm 352 9.3.2. Modified algorithms 355 9.4. Construction of neighboring relationships, balls and shells 357 9.4.1. Neighboring relationships 357 9.4.2. Construction of the ball of a vertex 359 9.4.3. Construction of the shell of an edge 361 9.5. Localization problems 363 9.5.1. Triangulations or simplicial meshes 363 9.5.2. Other meshes 367 9.6. Some formulae 367 Conclusions and Perspectives 369 Bibliography 371 Index 377