Houman Borouchaki, University of Technology of Troyes, France.Paul-Louis George, French Institute for Research in Computer Science and Automation, France.

• Foreword 9Introduction 11Chapter 1 Finite Elements and Shape Functions 151.1. Basic concepts 151.2. Shape functions, complete elements 181.2.1. Generic expression of shape functions 181.2.2. Explicit expression for degrees 1–3 221.3. Shape functions, reduced elements 261.3.1. Simplices, triangles and tetrahedra 271.3.2. Tensor elements, quadrilateral and hexahedral elements 311.3.3. Other elements, prisms and pyramids 481.4. Shape functions, rational elements 491.4.1. Rational triangle with a degree of 2 or arbitrary degree 491.4.2. Rational quadrilateral of an arbitrary degree 501.4.3. General case, B-splines or Nurbs elements 50Chapter 2 Lagrange and Bézier Interpolants 532.1. Lagrange–Bézier analogy 542.2. Lagrange functions expressed in Bézier forms 552.2.1. The case of tensors, natural coordinates 552.2.2. Simplicial case, barycentric coordinates 632.3. Bézier polynomials expressed in Lagrangian form 662.4. Application to curves 662.4.1. Bézier expression for a Lagrange curve 672.4.2. Lagrangian expression for a Bézier curve 702.5. Application to patches 712.5.1. Bézier expression for a patch in Lagrangian form 712.5.2. Lagrangian expression for a patch in Bézier form 732.6. Reduced elements 742.6.1. The tensor case, Bézier expression for a reduced Lagrangian patch 742.6.2. The tensor case, definition of reduced Bézier patches 822.6.3. The tensor case, Lagrangian expression of a reduced Bézier patch 902.6.4. The case of simplices 92Chapter 3 Geometric Elements and Geometric Validity 953.1. Two-dimensional elements 963.2. Surface elements 1053.3. Volumetric elements 1053.4. Control points based on nodes 1113.5. Reduced elements 1153.5.1. Simplices, triangles and tetrahedra 1153.5.2. Tensor elements, quadrilaterals and hexahedra 1163.5.3. Other elements, prisms and pyramids 1203.6. Rational elements 1213.6.1. Shift from Lagrange rationals to Bézier rationals 1213.6.2. Degree 2, working on the (arc of a) circle 1213.6.3. Application to the analysis of rational elements 1233.6.4. On the use of rational elements or more 138Chapter 4 Triangulation 1414.1. Triangulation, definitions, basic concepts and natural entities 1424.1.1. Definitions and basic concepts 1424.1.2. Natural entities 1454.1.3. A ball (topological) of a vertex 1454.1.4 A shell of a k-face 1454.1.5 The ring of a k-face 1464.2. Topology and local topological modifications 1464.2.1. Flipping an edge in two dimensions 1484.2.2. Flipping a face in three dimensions 1484.2.3. Flipping an edge in three dimensions 1484.2.4. Other flips? 1504.3. Enriched data structures 1514.3.1. Minimal structure 1514.3.2. Enriched structure 1524.4. Construction of natural entities 1534.5. Triangulation, construction methods 1564.6. The incremental method, a generic method 1594.6.1. Naive triangulation 1604.6.2. Delaunay triangulation 163Chapter 5 Delaunay Triangulation 1655.1. History 1665.2. Definitions and properties 1685.3. The incremental method for Delaunay 1755.4. Other methods of construction 1815.5. Variants 1865.6. Anisotropy 188Chapter 6 Triangulation and Constraints 1936.1. Triangulation of a domain 1946.1.1. Triangulation of a domain in two dimensions 1956.1.2. Triangulation of a domain in three dimensions 2026.2. Delaunay Triangulation “Delaunay admissibility” 2146.3. Triangulation of a variety 2196.4. Topological invariants (triangles and tetrahedra) 222Chapter 7 Geometric Modeling: Methods 2337.1. Implicit or explicit form (CAD), starting from an analytical definition 2347.1.1. Modeling an implicit curve, continuous → discrete 2347.1.2. Modeling a parametric curve 2377.1.3. Modeling an implicit surface 2387.1.4. Modeling of a parametric surface 2427.2. Starting from a discretization or triangulation, discrete → continuous 2467.2.1. Case of a curve 2477.2.2. The case of a surface 2537.3. Starting from a point cloud, discrete → discrete 2787.3.1. The case of a curve in two dimensions 2787.3.2. The case of a surface 2837.4. Extraction of characteristic points and characteristic lines 302Chapter 8 Geometric Modeling: Examples 3058.1. Geometric modeling of parametric patches 3068.2. Characteristic lines of a discrete surface 3118.3. Parametrization of a surface patch through unfolding 3118.4. Geometric simplification of a surface triangulation 3248.5. Geometric support for a discrete surface 3258.6. Discrete reconstruction of a digitized object or environment 330Chapter 9 A Few Basic Algorithms and Formulae 3439.1. Subdivision of an entity (De Casteljau) 3449.1.1. Subdivision of a curve 3449.1.2. Subdivision of a patch 3459.2. Computing control coefficients (higher order elements) 3489.3. Algorithms for the insertion of a point (Delaunay) 3519.3.1. Classic algorithm 3529.3.2. Modified algorithms 3559.4. Construction of neighboring relationships, balls and shells 3579.4.1. Neighboring relationships 3579.4.2. Construction of the ball of a vertex 3599.4.3. Construction of the shell of an edge 3619.5. Localization problems 3639.5.1. Triangulations or simplicial meshes 3639.5.2. Other meshes 3679.6. Some formulae 367Conclusions and Perspectives 369Bibliography 371Index 377

Houman Borouchaki, University of Technology of Troyes, France.Paul-Louis George, French Institute for Research in Computer Science and Automation, France.

• Foreword 9Introduction 11Chapter 1 Finite Elements and Shape Functions 151.1. Basic concepts 151.2. Shape functions, complete elements 181.2.1. Generic expression of shape functions 181.2.2. Explicit expression for degrees 1–3 221.3. Shape functions, reduced elements 261.3.1. Simplices, triangles and tetrahedra 271.3.2. Tensor elements, quadrilateral and hexahedral elements 311.3.3. Other elements, prisms and pyramids 481.4. Shape functions, rational elements 491.4.1. Rational triangle with a degree of 2 or arbitrary degree 491.4.2. Rational quadrilateral of an arbitrary degree 501.4.3. General case, B-splines or Nurbs elements 50Chapter 2 Lagrange and Bézier Interpolants 532.1. Lagrange–Bézier analogy 542.2. Lagrange functions expressed in Bézier forms 552.2.1. The case of tensors, natural coordinates 552.2.2. Simplicial case, barycentric coordinates 632.3. Bézier polynomials expressed in Lagrangian form 662.4. Application to curves 662.4.1. Bézier expression for a Lagrange curve 672.4.2. Lagrangian expression for a Bézier curve 702.5. Application to patches 712.5.1. Bézier expression for a patch in Lagrangian form 712.5.2. Lagrangian expression for a patch in Bézier form 732.6. Reduced elements 742.6.1. The tensor case, Bézier expression for a reduced Lagrangian patch 742.6.2. The tensor case, definition of reduced Bézier patches 822.6.3. The tensor case, Lagrangian expression of a reduced Bézier patch 902.6.4. The case of simplices 92Chapter 3 Geometric Elements and Geometric Validity 953.1. Two-dimensional elements 963.2. Surface elements 1053.3. Volumetric elements 1053.4. Control points based on nodes 1113.5. Reduced elements 1153.5.1. Simplices, triangles and tetrahedra 1153.5.2. Tensor elements, quadrilaterals and hexahedra 1163.5.3. Other elements, prisms and pyramids 1203.6. Rational elements 1213.6.1. Shift from Lagrange rationals to Bézier rationals 1213.6.2. Degree 2, working on the (arc of a) circle 1213.6.3. Application to the analysis of rational elements 1233.6.4. On the use of rational elements or more 138Chapter 4 Triangulation 1414.1. Triangulation, definitions, basic concepts and natural entities 1424.1.1. Definitions and basic concepts 1424.1.2. Natural entities 1454.1.3. A ball (topological) of a vertex 1454.1.4 A shell of a k-face 1454.1.5 The ring of a k-face 1464.2. Topology and local topological modifications 1464.2.1. Flipping an edge in two dimensions 1484.2.2. Flipping a face in three dimensions 1484.2.3. Flipping an edge in three dimensions 1484.2.4. Other flips? 1504.3. Enriched data structures 1514.3.1. Minimal structure 1514.3.2. Enriched structure 1524.4. Construction of natural entities 1534.5. Triangulation, construction methods 1564.6. The incremental method, a generic method 1594.6.1. Naive triangulation 1604.6.2. Delaunay triangulation 163Chapter 5 Delaunay Triangulation 1655.1. History 1665.2. Definitions and properties 1685.3. The incremental method for Delaunay 1755.4. Other methods of construction 1815.5. Variants 1865.6. Anisotropy 188Chapter 6 Triangulation and Constraints 1936.1. Triangulation of a domain 1946.1.1. Triangulation of a domain in two dimensions 1956.1.2. Triangulation of a domain in three dimensions 2026.2. Delaunay Triangulation “Delaunay admissibility” 2146.3. Triangulation of a variety 2196.4. Topological invariants (triangles and tetrahedra) 222Chapter 7 Geometric Modeling: Methods 2337.1. Implicit or explicit form (CAD), starting from an analytical definition 2347.1.1. Modeling an implicit curve, continuous → discrete 2347.1.2. Modeling a parametric curve 2377.1.3. Modeling an implicit surface 2387.1.4. Modeling of a parametric surface 2427.2. Starting from a discretization or triangulation, discrete → continuous 2467.2.1. Case of a curve 2477.2.2. The case of a surface 2537.3. Starting from a point cloud, discrete → discrete 2787.3.1. The case of a curve in two dimensions 2787.3.2. The case of a surface 2837.4. Extraction of characteristic points and characteristic lines 302Chapter 8 Geometric Modeling: Examples 3058.1. Geometric modeling of parametric patches 3068.2. Characteristic lines of a discrete surface 3118.3. Parametrization of a surface patch through unfolding 3118.4. Geometric simplification of a surface triangulation 3248.5. Geometric support for a discrete surface 3258.6. Discrete reconstruction of a digitized object or environment 330Chapter 9 A Few Basic Algorithms and Formulae 3439.1. Subdivision of an entity (De Casteljau) 3449.1.1. Subdivision of a curve 3449.1.2. Subdivision of a patch 3459.2. Computing control coefficients (higher order elements) 3489.3. Algorithms for the insertion of a point (Delaunay) 3519.3.1. Classic algorithm 3529.3.2. Modified algorithms 3559.4. Construction of neighboring relationships, balls and shells 3579.4.1. Neighboring relationships 3579.4.2. Construction of the ball of a vertex 3599.4.3. Construction of the shell of an edge 3619.5. Localization problems 3639.5.1. Triangulations or simplicial meshes 3639.5.2. Other meshes 3679.6. Some formulae 367Conclusions and Perspectives 369Bibliography 371Index 377