Contents
General introduction
Synopsis
Symbols and notations
1 General definitions
1.1 Covering-up and triangulation
1.2 Mesh
1.3 Mesh element
1.4 Finite element mesh
1.5 Mesh data structures
1.5.1 Internal mesh data structure
1.5.2 Output mesh data structure
1.6 Control space
1.7 Neighborhood space
1.8 Mesh quality and mesh optimality
2 Basic structures and algorithms
2.1 Why use data structures ?
2.2 Elementary structures
2.2.1 Table or array
2.2.2 List
2.2.3 Stack
2.2.4 Queue
2.2.5 Objects and pointers
2.3 Basic notions about complexity
2.3.1 Behavior of a function
2.3.2 Complexity, worst case, average case, optimal case
2.3.3 Amortized complexity
2.4 Sorting and searching
2.4.1 Sorting by comparison algorithms
2.4.2 Bucket sorting
2.4.3 Searching algorithms and dichotomies
2.4.4 Three main paradigms
2.5 One dimensional data structures
2.5.1 Binary tree
2.5.2 Hashing
2.5.3 Priority queues
2.6 Two and three-dimensional data structures
2.6.1 Grid-based data structures
2.6.2 Quadtrees and octrees
2.6.3 About filters and side-effects
2.7 Topological data structures
2.7.1 A triangle based representation
2.7.2 Winged-edge data structure
2.7.3 Hierarchical representation
2.7.4 Other representations
2.8 Robustness
2.8.1 Robustness issues
2.8.2 Computational geometry
2.8.3 The algebraic degree of a problem and predicates
2.8.4 Robust and efficient floating-point geometric predicates
2.9 Optimality of an implementation
2.9.1 Memory handling
2.9.2 Running time profiling
2.10 Classical application examples
2.10.1 Enumerating the ball of a given vertex (1)
2.10.2 Enumerating the ball of a given vertex (2)
2.10.3 Searching operations
2.10.4 Enumerating the set of edges in a mesh
2.10.5 About set membership
2.10.6 Constructing the neighborhood relationships
2.10.7 Static and dynamic coloring
2.10.8 About the construction of a dichotomy
3 A comprehensive survey of mesh generation methods
3.1 Classes of methods
3.2 Structured mesh generators
3.2.1 Algebraic interpolation methods
3.2.2 P.D.E.-based methods
3.2.3 Multiblock method
3.2.4 Product method (topology-based method)
3.3 Unstructured mesh generators
3.3.1 Spatial decomposition methods
3.3.2 Advancing-front method
3.3.3 Delaunay technique
3.3.4 Tentative comparison of the three classical methods
3.3.5 Other methods
3.4 Surface meshing
3.4.1 Parametric mesh generation
3.4.2 Implicit surface triangulation
3.4.3 Direct surface meshing
3.4.4 Surface remeshing
3.5 Mesh adaptation
3.5.1 Mesh adaptation scheme
3.5.2 Mesh adaptation techniques
3.6 Parallel unstructured meshing
3.6.1 Parallelism and meshing processes
3.6.2 Domain decomposition
4 Algebraic, P.D.E. and multiblock methods
4.1 Algebraic methods
4.1.1 Trivial mapping functions
4.1.2 Quadrilateral analogy
4.1.3 Triangular analogy
4.1.4 Application examples
4.1.5 Surface meshing
4.1.6 Hexahedral analogy
4.1.7 Pentahedral analogy
4.1.8 Tetrahedral analogy
4.1.9 Other algebraic methods
4.1.10 An alternative to algebraic methods
4.2 P.D.E.-based methods
4.2.1 Basic ideas
4.2.2 Surface meshing and complex shapes
4.3 Multiblock method
4.3.1 Basic ideas
4.3.2 Partitioning the domain
4.3.3 Computational issues
4.3.4 Application examples
5 Quadtree-octree based methods
5.1 Overview of spatial decomposition methods
5.1.1 Terminology and definitions
5.1.2 Operations on trees
5.1.3 Data structures
5.2 Classical tree-based mesh generation
5.2.1 General scheme
5.2.2 Preliminary requirements
5.2.3 Tree construction
5.2.4 Tree balancing
5.2.5 Filtering of the intersection points
5.2.6 Vertex and element creation
5.2.7 Optimization
5.2.8 Computational issues
5.3 Governed tree-based method
5.3.1 Control space
5.3.2 Governed tree construction
5.3.3 Optimization
5.3.4 Application examples
5.4 Other approaches
5.4.1 Combined approaches
5.4.2 Other approaches
5.5 Extensions
5.5.1 Curve and surface mesh generation
5.5.2 Mesh adaptation
6 Advancing-front technique for mesh generation
6.1 A classical advancing-front technique
6.1.1 General scheme
6.1.2 Preliminary requirements
6.1.3 Analysis of the front
6.1.4 Field point creation
6.1.5 Validation
6.1.6 Convergence issues
6.1.7 Point insertion and front updating
6.1.8 Optimization
6.1.9 Practical issues
6.2 Governed advancing-front method
6.2.1 Control space
6.2.2 Field point creation
6.2.3 Optimization
6.3 Application examples
6.4 Combined approaches
6.4.1 Advancing-front Delaunay approach
6.4.2 Advancing-front with preplaced interior points
6.4.3 Hybrid approaches
6.5 Extensions
6.5.1 Anisotropic mesh generation
6.5.2 Surface mesh generation
6.5.3 Mesh adaptation
7 Delaunay-based mesh generation methods
7.1 The Delaunay triangulation
7.1.1 The Voronoï diagram
7.1.2 Delaunay triangulation and Voronoï diagram
7.1.3 Theoretical issues
7.1.4 Practical issues
7.2 Constrained triangulation
7.2.1 Maintaining a constrained entity
7.2.2 Constraints in two dimensions
7.2.3 Constraints in three dimensions
7.3 Classical Delaunay meshing
7.3.1 General scheme
7.3.2 Simplified Delaunay type triangulation method
7.3.3 Boundary integrity
7.3.4 Identifying the elements in the domain
7.3.5 Field point creation
7.3.6 Optimization
7.3.7 Practical issues
7.3.8 Application examples
7.4 Other methods
7.4.1 Point insertion methods
7.4.2 Boundary enforcement
7.4.3 Field point creation
7.5 Isotropic governed Delaunay meshing
7.5.1 Control space
7.5.2 Field point creation
7.6 Extensions
7.6.1 Anisotropic Delaunay meshing
7.6.2 Surface meshing
7.6.3 Mesh adaptation
8 Other types of mesh generation methods
8.1 Product method
8.1.1 Basic principles
8.1.2 Computational issues
8.1.3 Limits
8.1.4 Application examples
8.2 Grid or pattern-based methods
8.3 Optimization-based method
8.3.1 Theoretical background
8.3.2 Synthetic algorithm
8.3.3 Computational issues
8.3.4 Extension in three dimensions
8.3.5 Application examples
8.4 Quads by means of triangle combination
8.4.1 Two basic combinations
8.4.2 Selection of a combination
8.4.3 Optimization
8.4.4 Alternate method
8.4.5 Dealing with a surface
8.5 Quad by means of a direct method
8.5.1 Advancing-front type method
8.5.2 Grid Superposition
8.5.3 Using the medial axis
8.6 Hex meshing
8.7 Miscellaneous
8.7.1 Radial meshes
8.7.2 Recursive partition
9 Medial axis, mid-surface and applications
9.1 Delaunay-admissible set of segments in R[sup(2)]
9.1.1 Terminology and notations
9.1.2 Classification
9.1.3 Analysis of the three configurations
9.1.4 Construction of a Delaunay-admissible set of edges
9.1.5 Delaunay-admissible boundary discretization
9.2 Delaunay-admissible set of segments in R[sup(3)]
9.3 Delaunay-admissible set of triangular faces
9.3.1 Notations
9.3.2 Classification
9.3.3 Analysis of the three configurations
9.3.4 Construction of a Delaunay-admissible set of faces
9.3.5 Delaunay-admissible boundary discretization
9.4 Medial axis
9.4.1 Delaunay triangulation and medial axis construction
9.4.2 Voronoï cells of a set of points and medial axis
9.4.3 Computational issues
9.5 Mid-surface
9.6 Medial axis (mid-surface) transform
9.7 Applications
9.7.1 Domain partitioning
9.7.2 Quad mesh construction
9.7.3 Hex mesh construction
9.7.4 Other applications
10 Quadratic forms and metrics
10.1 Bilinear and quadratic forms
10.1.1 Linear and bilinear forms
10.1.2 Matrix form of a bilinear form
10.1.3 Quadratic forms
10.1.4 Distances and norms
10.1.5 Matrix form of a quadratic form
10.2 Distances and lengths
10.2.1 Classical length
10.2.2 Unit length
10.2.3 Applications
10.3 Metric-based operations
10.3.1 Simultaneous reduction of two metrics
10.3.2 Metric interpolation
10.3.3 Metric intersection
10.3.4 Metric smoothing
10.4 Metric construction
10.4.1 Parametric surface meshing
10.4.2 Finite element simulation with error control
11 Differential geometry
11.1 Metric properties of curves and arcs
11.1.1 Arc length
11.1.2 Curvilinear abscissa, normal parameters and characteristics
11.1.3 Frénet's frame and formula
11.1.4 Local behavior of a planar curve
11.1.5 Arcs in R[sup(3)]. Frénet's frame and Serret-Frénet's formulas
11.1.6 Computing curvature and torsion
11.1.7 Local metric study of arcs in R[sup(3)]
11.1.8 Parameterization of arcs
11.2 Metric properties of a surface
11.2.1 First fundamental quadratic form
11.2.2 Normal. Local frame. Darboux's frame
11.2.3 Normal curvature, curvature and geodesic torsion
11.2.4 Second fundamental form
11.2.5 Computing curvatures and geodesic torsion
11.2.6 Meusnier's circle and theorem
11.2.7 Local behavior of a surface
11.3 Computational issues about surfaces
11.3.1 Curvature computation
11.3.2 Normal curvature analysis
11.3.3 Relationship between curvatures and fundamental forms
11.3.4 Local behavior of a surface
11.4 Non-linear problems
11.4.1 Non-linear issues
11.4.2 Newton-Raphson type algorithms
11.4.3 Divide and conquer algorithm
12 Curve modeling
12.1 Interpolation and smoothing techniques
12.1.1 Parameterization of a set of points
12.1.2 Interpolation based methods
12.1.3 Smoothing based methods
12.1.4 Combined methods
12.2 Lagrange and Hermite interpolation
12.2.1 Lagrange's interpolation scheme
12.2.2 Recursive form for a Lagrange interpolation
12.2.3 Matrix form for a Lagrange interpolation
12.2.4 Lagrange forms of degree 1 and 2
12.2.5 Hermite interpolation scheme
12.2.6 The Hermite cubic form
12.3 Explicit construction of a composite curve
12.4 Control polygon based methods
12.4.1 Control polygon and curve definition
12.4.2 General properties
12.5 Bézier curves
12.5.1 Form of a Bézier curve
12.5.2 About Bernstein polynomials
12.5.3 De Casteljau form for a Bézier curve
12.5.4 Bézier curve of degree 3
12.5.5 Degree elevation of a Bézier curve
12.6 From composite curves to B-Splines
12.6.1 Composite Bézier curves
12.6.2 B-splines curves
12.6.3 Degree 1 B-spline
12.6.4 Degree 2 B-spline
12.6.5 Degree 3 B-spline
12.6.6 Specific controls
12.6.7 A Bézier curve by means of a B-Spline
12.6.8 Relationships between the parameters of a B-Splines
12.7 Rational curves
12.7.1 Definition based on a control polygon
12.7.2 Rational Bézier curve
12.7.3 Rational B-spline curve (NURBS)
12.8 Curve definitions and numerical issues
12.8.1 An exact parameterization of a curve
12.8.2 A given parameterization of a curve
12.8.3 One curve parameterization with more precise definitions
12.8.4 Using a polyline
12.9 Towards a "pragmatic" curve definition ?
12.9.1 Curve definitions and meshing topics
12.9.2 Key-ideas
12.9.3 Construction of a well-suited discrete definition
13 Surface modeling
13.1 Specific surfaces
13.1.1 Surfaces of revolution
13.1.2 Trimmed surfaces
13.1.3 Extruded or sweeping surfaces
13.2 Interpolation-based surfaces
13.2.1 Tensor product based patches (introduction)
13.2.2 Interpolation-based patches
13.2.3 Lagrange interpolation
13.2.4 Transfinite interpolation (Coons patches)
13.3 Tensor product and control polyhedron
13.3.1 Control polyhedron
13.3.2 Bézier quads
13.3.3 B-splines patches
13.4 Triangular patches
13.4.1 Tri-parametric forms
13.4.2 Bézier triangles
13.5 Other types of patches
13.5.1 Rational patches
13.5.2 Rational quad Bézier patches
13.5.3 Rational Bézier triangles
13.5.4 Patches based on an arbitrary polyhedron
13.6 Composite surfaces
13.6.1 Composite Bézier triangles
13.6.2 Other composite surfaces
13.7 Explicit construction of a composite surface
13.7.1 Constructing the curves boundary of a patch
13.7.2 Construction of a patch
14 Curve meshing
14.1 Meshing a segment
14.1.1 Classical segment meshing
14.1.2 Isotropic governed meshing
14.1.3 Anisotropic meshing
14.1.4 Examples of straight segment meshes
14.2 Meshing a parametric curve
14.2.1 Geometric mesh
14.2.2 Meshing algorithm without a metric map
14.2.3 Meshing algorithm with a metric map
14.3 Curve meshing using a discrete definition
14.3.1 Construction of a definition from discrete data
14.3.2 Curve approximation by a polygonal segment
14.3.3 Curve meshing from a discrete definition
14.3.4 Examples of planar curve meshes
14.4 Re-meshing algorithm
14.5 Curves in R[sup(3)]
14.5.1 Dangling curves
14.5.2 Curves of a parametric surface
15 Surface meshing and re-meshing
15.1 Curve meshing (curve member of a surface)
15.2 First steps in surface meshing
15.2.1 Various approaches to surface meshing
15.2.2 Desired properties
15.2.3 Direct surface meshing
15.2.4 Construction in two dimensions and mapping
15.3 A single patch
15.3.1 Typical patches
15.3.2 Desired features in the parametric case
15.3.3 Meshing a patch
15.4 Multi-patches surface (patch dependent)
15.4.1 Meshing the interfaces between patches
15.4.2 Meshing the patches
15.5 Multi-patches surface (patch-independent)
15.5.1 Indirect approach
15.5.2 Direct approach
15.6 Discrete surface (re-meshing process)
15.6.1 Definition of a discrete surface
15.6.2 Re-meshing a discrete surface
15.7 Ill-defined multi-patches surface
16 Meshing implicit curves and surfaces
16.1 Review of implicit functions
16.1.1 A preliminary remark
16.1.2 Implicit planar curves
16.1.3 Extension to implicit surfaces
16.2 Implicit function and meshing
16.2.1 Problem statement
16.2.2 Geometric mesh
16.2.3 General principle
16.3 Implicit curve meshing
16.3.1 Construction of a spatial covering-up
16.3.2 Meshing an implicit curve from a point cloud
16.3.3 Computational aspects of implicit curve meshing
16.4 Implicit surface meshing
16.4.1 Construction of a spatial covering-up
16.4.2 Mesh of an implicit surface defined by a point cloud
16.4.3 Surface mesh optimization
16.4.4 Computational aspects of implicit surface meshing
16.4.5 Examples of surface meshes
16.5 Extensions
16.5.1 Modeling based on implicit functions
16.5.2 Implicit domain meshing
17 Mesh modifications
17.1 Mesh (geometric) modifications
17.1.1 Popular geometric transformations
17.1.2 Local and global refinement
17.1.3 Type conversion
17.2 Merging two meshes
17.3 Node creation and node labeling
17.3.1 Vertex and element labeling
17.3.2 Node creation
17.3.3 Node construction and p—compatibility
17.3.4 Node labeling
17.3.5 Some popular finite elements
17.4 Renumbering issues
17.4.1 Vertex renumbering
17.4.2 Element renumbering
17.4.3 Application examples
17.4.4 Other renumbering methods
17.5 Miscellaneous
18 Mesh optimization
18.1 About element measurement
18.1.1 Element surface area
18.1.2 Element volume
18.1.3 Other measurements
18.2 Mesh quality (classical case)
18.2.1 Shape or aspect ratio
18.2.2 Other criteria
18.2.3 Simplicial element classification
18.2.4 Non simplicial elements
18.3 Mesh quality (isotropic and anisotropic case)
18.3.1 Efficiency index
18.3.2 Element quality
18.3.3 Optimal mesh
18.3.4 Remarks about optimality
18.4 Tools for mesh optimization
18.4.1 Optimization maintaining the connectivities
18.4.2 Optimization maintaining the vertex positions
18.4.3 Non-obtuse mesh
18.5 Strategies for mesh optimization
18.6 Computational issues
18.7 Application examples
18.7.1 Mesh appreciation
18.7.2 A few examples
19 Surface mesh optimization
19.1 Quality measures
19.1.1 Surface mesh quality (classical case)
19.1.2 Surface mesh quality (general case)
19.1.3 Quality of the geometric approximation
19.1.4 Optimal surface mesh
19.2 Discrete evaluation of surface properties
19.2.1 Intrinsic properties
19.2.2 Metric of the tangent plane
19.2.3 Computational aspects
19.3 Constructing a geometric support
19.3.1 Classical approaches
19.3.2 Modified approach, Walton's patch
19.3.3 Constructing the geometric support
19.3.4 Using the geometric support
19.4 Optimization operators
19.4.1 Geometric optimization
19.4.2 Topological optimization
19.5 Optimization methods
19.5.1 Shape optimization (classical case)
19.5.2 Size optimization (isotropic and anisotropic case)
19.5.3 Optimal mesh
19.6 Application examples
19.6.1 Surface mesh optimization examples
19.6.2 Mesh simplification
20 A touch of finite elements
20.1 Introduction to a finite element style computation
20.2 Definition and first examples of finite elements
20.2.1 Definition of a finite element
20.2.2 First examples of finite elements
20.3 About error estimation and convergence
20.3.1 Local (element) quantity and global quantities
20.3.2 Error estimation and convergence issues
20.3.3 Quadrature influence
20.3.4 Curved elements
20.4 Stiffness matrix and right-hand side
20.4.1 General expression of a stiffness matrix
20.4.2 General expression of a right-hand side
20.4.3 About the T3 triangle
20.4.4 About the linear T6 triangle
20.4.5 About the isoparametric T6 triangle
20.4.6 Element quantities and data structure
20.4.7 About integrals and quadratures
20.4.8 The global system
20.5 A few examples of popular finite elements
21 Mesh generation and adaptation (h-methods)
21.1 Control space (background mesh)
21.1.1 Definition of a background mesh
21.1.2 Use of a background mesh
21.2 H-adaptation by local modifications
21.2.1 Refinement of mesh elements
21.2.2 Element coarsening
21.2.3 R-method
21.2.4 Remarks about local methods
21.3 Global isotropic adaptation method
21.3.1 H-method based on a quadtree-octree approach
21.3.2 H -method based on an advancing-front approach
21.3.3 H-method based on a Delaunay-type method
21.3.4 Mesh optimization tools (isotropic case)
21.3.5 Remarks about global methods (isotropic)
21.4 Global anisotropic adaptation method
21.4.1 H-method based on a quadtree-octree approach
21.4.2 H-method based on an advancing-front approach
21.4.3 H-method based on a Delaunay-type method
21.4.4 Mesh optimization tools (anisotropic case)
21.4.5 Remarks about global methods (anisotropic)
21.5 Adaptation
21.5.1 General framework of a local adaptation method
21.5.2 General framework of a global adaptation method
21.5.3 Remarks about an adaptive scheme
21.6 Application examples
22 P-methods and hp-methods
22.1 P[sup(2)] mesh
22.1.1 Meshing a curve (review)
22.1.2 P[sup(2)] finite elements
22.2 P-compatibility
22.2.1 P-compatibility a priori
22.2.2 P-compatibility a posteriori
22.3 Construction of P[sup(2)] elements
22.3.1 Element 2-compatible
22.3.2 Other elements
22.3.3 Dealing with a surface element
22.3.4 Volumic case, example of the P[sup(2)] tetrahedron
22.4 Elements of higher degree
22.5 About p-methods and hp-methods
22.5.1 P and hp-methods
22.5.2 An adaptation scheme
23 Parallel computing and meshing issues
23.1 Partition of a domain
23.1.1 Overview of partitioning methods
23.1.2 Partitioning a posteriori
23.1.3 Partitioning a priori
23.2 Parallel meshing process
23.2.1 One-step process
23.2.2 Parallel adaptation loop
23.3 Parallel meshing techniques
23.3.1 Delaunay-type method
23.3.2 Quadtree-octree-iype method
23.3.3 Other methods ?
Bibliography
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W