Meshing, Geometric Modeling and Numerical Simulation 1 E-Book

Houman Borouchaki

• Herausgeber: John Wiley & Sons
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 691

Veröffentlichungsjahr: 2017

Beschreibung

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.

Leseprobe

Table of Contents

Cover

Dedication

Title

Copyright

Foreword

Introduction

Chapter 1: Finite Elements and Shape Functions

1.1. Basic concepts

1.2. Shape functions, complete elements

1.3. Shape functions, reduced elements

1.4. Shape functions, rational elements

Chapter 2: Lagrange and Bézier Interpolants

2.1. Lagrange–Bézier analogy

2.2. Lagrange functions expressed in Bézier forms

2.3. Bézier polynomials expressed in Lagrangian form

2.4. Application to curves

2.5. Application to patches

2.6. Reduced elements

Chapter 3: Geometric Elements and Geometric Validity

3.1. Two-dimensional elements

3.2. Surface elements

3.3. Volumetric elements

3.4. Control points based on nodes

3.5. Reduced elements

3.6. Rational elements

Chapter 4: Triangulation

4.1. Triangulation, definitions, basic concepts and natural entities

4.2. Topology and local topological modifications

4.3. Enriched data structures

4.4. Construction of natural entities

4.5. Triangulation, construction methods

4.6. The incremental method, a generic method

Chapter 5: Delaunay Triangulation

5.1. History

5.2. Definitions and properties

5.3. The incremental method for Delaunay

5.4. Other methods of construction

5.5. Variants

5.6. Anisotropy

Chapter 6: Triangulation and Constraints

6.1. Triangulation of a domain

6.2. Delaunay Triangulation “Delaunay admissibility”

6.3. Triangulation of a variety

6.4. Topological invariants (triangles and tetrahedra)

Chapter 7: Geometric Modeling: Methods

7.1. Implicit or explicit form (CAD), starting from an analytical definition

7.2. Starting from a discretization or triangulation, discrete → continuous

7.3. Starting from a point cloud, discrete → discrete

7.4. Extraction of characteristic points and characteristic lines

Chapter 8: Geometric Modeling: Examples

8.1. Geometric modeling of parametric patches

8.2. Characteristic lines of a discrete surface

8.3. Parametrization of a surface patch through unfolding

8.4. Geometric simplification of a surface triangulation

8.5. Geometric support for a discrete surface

8.6. Discrete reconstruction of a digitized object or environment

Chapter 9: A Few Basic Algorithms and Formulae

9.1. Subdivision of an entity (De Casteljau)

9.2. Computing control coefficients (higher order elements)

9.3. Algorithms for the insertion of a point (Delaunay)

9.4. Construction of neighboring relationships, balls and shells

9.5. Localization problems

9.6. Some formulae

Conclusions and Perspectives

Bibliography

Index

End User License Agreement

List of Tables

Chapter 1: Finite Elements and Shape Functions

Table 1.1. The diagram of the basis monomials for a degree of 5. We find the monomials up to the degree of 5 complemented (last line) by some monomials of degree 6, whence the monomial u

3

v

3

(which is added to the classic monomials of the serendipity elements due to the symmetry imposed in our definition)

Chapter 3: Geometric Elements and Geometric Validity

Table 3.1. First edge of a quadrilateral from degree 2 to 5

Table 3.2. First edge for a triangle of degree 3

Table 3.3. First edge of a triangle of degree 3

Table 3.4. First edge of a quadrilateral from degree 2 to 5

Chapter 4: Triangulation

Table 4.1. The number of topologically possible triangulations

List of Illustrations

Chapter 1: Finite Elements and Shape Functions

Figure 1.1. Joseph Louis Lagrange (1736–1813)

Figure 1.2. The three princes of Serendip

Chapter 2: Lagrange and Bézier Interpolants

Figure 2.1. Pierre Bézier in 1958

Chapter 3: Geometric Elements and Geometric Validity

Figure 3.1. Schema of the vectors involved in the three control coefficients of the first edge of the second-degree triangle. From left to right: N

200

, N

110

and N

020

Figure 3.2. Schema for the vectors involved in the four control coefficients of the first edge of the second-degree quadrilateral. From left to right: N

00

, N

10

, N

20

and N

30

Figure 3.3. Schema for the vectors involved in the central control coefficient N

11

of the second-degree quadrilateral

Figure 3.4. Paul de Faget De Casteljau

Figure 3.5. The principle of geometric subdivision of an edge into two parts is also applicable to a Jacobian polynomial. On the left is the initial edge [A

200

A

020

] and its control point P

110

. On the right are the two pieces with the control points obtained after the subdivision of the node A

110

Figure 3.6. Schema of the vectors involved in the four control coefficients of the first edge of the rational triangle of degree 2. From left to right N

300

, N

210

, N

120

and N

030

. See the difference with respect to Figure 3.1, the classic second-degree triangle

Figure 3.7. Schema of the vectors participating in the central control coefficient, N

111

, of the rational second-degree triangle.

Figure 3.8. Schema of the vectors involved in the five control coefficients of the first edge of the second-degree rational quadrilateral. From left to right, M

00

, M

10

, M

20

then, below, M

30

and M

40

Figure 3.9. Schema of the vectors involved in the central control coefficients of the second-degree, rational quadrilateral. From top to bottom: M

11

, M

21

and M

22

Chapter 4: Triangulation

Figure 4.1. On the left, an elementary topological flip. On the right, an elementary geometric flip

Figure 4.2. The topological configurations for an edge with five elements

Figure 4.3. For the recurrence relation about the number of topological triangulations which are possible for a polygon

Figure 4.4. Divide and conquer. On the left: the step of fusion in two dimensions – effectively triangulate or find the two edges (extremes) of the convex hull. On the right: step of fusion to construct the convex hull in three dimensions – find the ridged edge and then triangulate between the two convex subhulls

Figure 4.5. Localization problem. On the left: the principle of the algorithm that makes it possible to find the solution by starting from an element K

0

. On the right, a pathological situation where a cycle is set up

Chapter 5: Delaunay Triangulation

Figure 5.1. Boris Delaunay (1890–1980) and Gueorgui Voronoï (1868–1908)

Figure 5.2. The duality between the Voronoï diagram (on the left) and the Delaunay triangulation (on the right)

Figure 5.3. Delaunay’s general lemma, written in French (using words, without using mathematical formulae) and published in 1934

Figure 5.4. On the left: the Delaunay criterion is symmetrical. On the right: the proof by contradiction

Figure 5.5. Insertion of the point P. The basis can be resumed as the triangle (P2P5P8). The cavity is formed by the triangles traced in unbroken lines (except those sharing the vertex P7). The external faces of the cavity are denoted by F1, F2, ..., F7. The ball, composed of the elements traced in dotted lines, is obtained by joining the point P to the faces (edges, here, in two dimensions) F

i

Figure 5.6. The incremental method using flipping. To the left, the basis is reduced to a single triangle cut into three. In the middle, an initial flip, that of the edge [P

2

P

5

]. To the right, the final result, when all the flips have been carried out

Figure 5.7. The incremental method using flipping. Characterization of the external, flipable d-face

Figure 5.8. The ellipse centered at X and some of its points (denoted P)

Chapter 6: Triangulation and Constraints

Figure 6.1. Listing of the elements of the pipe of [α, β]. To the right, the ball of α and its triangle [α, P

1

, P

2

] whose edge [P

1

, P

2

] is intersected by the segment [α, β], and which, thereby, is the first triangle of the pipe

Figure 6.2. To the left, the beginning of the pipe. In the middle, taking into account the first point of intersection, I

1

, with the creation of the two red edges and associated triangles. On the right, taking into account the second point of intersection, I

2

, with the creation of two blue edges and the corresponding triangles

Figure 6.3. On the left, the triangles of the pipe of [α, β]. On the right, the first flip (in red) that allows us to reduce the size of the problem and another flip (in blue) that has no apparent effect

Figure 6.4. Top left: three triangles share a vertex, we delete it. Top right, the same case with four triangles (which necessarily form a convex polygon). Bottom left: fusion of I

1

on α. Bottom right: flipping the edge [I

1

, 6] to reduce the number of triangles incident on I

1

Figure 6.5. On the left: the first pipe elements with the first two intersections I

1

andI

2

. On the right, the triangulation obtained by duplication the vertex I

1

Figure 6.6. To the left: the triangles of the pipe of [α, β], To the right: the vertices of the “high rise” outline of [α, β] and the formation of the triangle [α, β, P

k

]

Figure 6.7. An example of a non-simple polygon, whose border edges are in this order: [α, 1], [1, 3], [3, 1], [1, β], [β, 4], [4, 2] and [2, α]

Figure 6.8. Schönhardt polyhedron(1). Take a large potato and a knife. Cut the potato into a prism. One cut (horizontal) to flatten the bottom and another cut to flatten the top. Three slices (vertical) to obtain a triangle on the top (and bottom). The prism is constructed. It has two triangular faces and three quadrilateral faces. Illustrations by Peha

Figure 6.9. Schönhardt polyhedron (2). On the left, it is possible to cut the prism into three tetrahedra, respecting the constrained edges. On the right: no solution. This is a Schönhardt polyhedron that is non-triangulable as it is

Figure 6.10. Locally convexifying a configuration. On the left: the vertex P is such that the flip between K

1

and K

2

is impossible. Consequently, we introduce the point M to construct a tetrahedron neighboring K

1

that can be flipped. On the right: the situation involves a set of tetrahedra incident at P and a series of points M

j

is constructed to allow the flips

Figure 6.11. Delete the shell of edge [a, b] (on the left) intersected by [α, β] using a flip (in the center) or using a Steiner point by breaking (for example, with the midpoint Q) and moving from Q to find P(on the right)

Figure 6.12. The face of the constraint [α, β, γ] and two tetrahedra intersected on the common face [a, b, c]. The points P

1

to P

6

, intersections of the edges [α, β, γ] with these tetrahedra

Figure 6.13. On the left: the segment [α, β] and its diametral disc . In the middle: a triangle whose circumcircle is empty and, thus, Q

1

is not in conflict with [α, β]. On the right: a triangle such that Q

1

is in conflict with [α, β], while Q

2

and Q

3

are not

Figure 6.14. On the left we have the initial configuration, the two segments [1, 2] and [1, 3], broken by introducing diverse midpoints. The configuration obtained exactly reproduces the same pattern with the two segments [1, 12] and [1, 13]. To the right: we break the segment [1, 2] by introducing the point P

r

which is the projection of [3] on [1, 2]

Figure 6.15. On the left: the initial configuration corresponding to a cluster of segments with acute angles between two consecutive segments and the first division points. On the right: the creation of a protective circle

Figure 6.16. Some minimal model configurations. On the left: the simplest case, in the center: border with two connected components, on the right: border with three connected components

Figure 6.17. Cut a torus and unfold it

Chapter 7: Geometric Modeling: Methods

Figure 7.1. Ambiguous situations, at least three solutions are plausible, but the solution on the right will involve an intersecting curve

Figure 7.2. On the left: the signs of f in two neighboring cells. In the center: a finer analysis. On the right: the refined curve

Figure 7.3. Different types of polygons constructed from predefined patterns based on the number and respective position of the points of intersection between the desired surface and the edges of a box. In these cases, we have only one component of the surface present in the box, in other words the portion of the surface separates the vertices of opposing signs

Figure 7.4. The 15 predefined motives based on the number and respective position of points of intersection between the desired surface and the edges of a box. In these cases, we have one or more surface components present in the box, each portion of the surface separating the vertices with opposite signs. Let us note that the polygons found were, if necessary, decomposed into triangles and certain solutions remain ambiguous

Figure 7.5. Ambiguous situations, two solutions are plausible for this case where one face of a cell has four intersections

Figure 7.6. The three types of solutions, no intersections or a polygon, which is necessarily a triangle, or a quadrilateral depending on the number of points of intersection between the desired surface and the edges of a tetrahedral cell. Let us note that there is no ambiguity in the case where there are four points of intersection

Figure 7.7. Division of the nodes of the tree with the trace of the segments of the support based on the configuration present. On the left: in red, the configuration formed by the trace of the segments of the support in a leaf. On the right, the corresponding division with, in blue, the reinterpreted new traces and the definition of the triangles

Figure 7.8. Patterns for conformity. Above: the case of a quadrilateral with the two possible situations. Below: case of a triangle with two possible situations again

Figure 7.9. Hausdorff band for distance δ

Figure 7.10. On the left: Hausdorff band for the distance δ. On the right: the cone associated with a vertex

Figure 7.11. The convex polygon associated with the region

Figure 7.12. On the left: the definition for the element sharing an edge with a given triangle k′. On the right: the computation of the Hausdorff distance

Figure 7.13. Continuity between neighboring patches, k

1

and k

2

, with the three possible situations depending on whether the common edge, [α, β], is shared by two quadrilaterals, two triangles or one triangle and one quadrilateral

Figure 7.14. Continuity between neighboring patches, the concerned control points for continuity across the edge [α, β]. Above: the control triangles for the triangle–triangle case and the colinearity condition for the quad-quad case. In the middle: the colinearity condition is replaced by the coplanarity of the control triangles. Bottom: the triangle-quad case, with the control triangles

Figure 7.15. Unfolding based on the Laplace operator, K, and K′

Figure 7.16. Isometric unfolding, K, and K′ (returning to the earlier figure)

Figure 7.17. Isometric unfolding, the first two adjacency levels (red then blue) of the “central” triangle

Figure 7.18. Partial simulation of the medial axis considering the insertion of the centers of the circumscribed balls. The insertion of O

1

, the center of the ball of K

1

will break the edge [α, β] as the element K

2

will be in the cavity of O

1

, this edge will therefore be invalid (and it is pointless to simulate the insertion of O

2

). The insertion of O

1

, the center of the ball of K

1

, and that of O

3

, the center of the ball of K

3

, will not break the edge [α, γ], which is therefore considered to be valid

Figure 7.19. Some examples of probable and improbable holes. On the left: the edges in red indicate a surface boundary, that is the boundary of a hole. We observe some “small” holes and a larger hole (in size or in the number of edges). On the right: the “small” holes have been fixed or have disappeared (see the triangle in blue and its neighborhood, which shows that the hole with three edges that was initially detected, does not correspond to the solution triangle. The large hole has also been fixed, which may be more debatable

Figure 7.20. Some examples of holes of small size. On top: a visible hole with three edges and the face [α, β, γ] exists, that can fix the hole. On the right: this face does not exist, but by correcting the edge of the hole we find two faces that correspond to this new edge. Bottom: a visible hole with four edges and the two solutions found in the faces of the tetrahedra

Figure 7.21. Choosing a face whose two edges are two consecutive sides of the hole. The best choice is guided by the angular error (calculated at β and estimated at α and at γ to assess the face [α, β, γ], on the left.), the dihedral angles for the two edges of the side studied, between the neighboring face and the tested face, and, again, the angles of the analyzed faces

Figure 7.22. Some examples of correspondence between two consecutive sections. On the left: the two sections are “identical” and define the ribbon of the surface to be triangulated. In the middle: the section S

2

has two components and its projection in the plane of S

1

give two components, one of which has no intersection. This therefore has to do with the beginning of a branch of the surface. On the right: the section S

2

has two components and its projections in the plane of S

1

defines the region to be triangulated, which also has two components and reveals two additional points of intersection, which, in order to triangulate the surface, will be duplicated

Figure 7.23. Variation of the angle θ

Chapter 8: Geometric Modeling: Examples

Figure 8.1. A constrained parametric patch and its domain of parameters

Figure 8.2. The quaternary tree associated with the geometric support of the contours

Figure 8.3. The identification of the domain and the balancing of the tree

Figure 8.4. The conforming triangulation of the domain of parameters and its image on the patch defining the geometric support of this patch

Figure 8.5. A geometric support of the White House and a close-up

Figure 8.6. A geometric support of the White House and a close-up for a finer accuracy

Figure 8.7. Uniform mesh and geometric mesh (angle 8

◦

, gradation 1.25)

Figure 8.8. Discrete model of a ventilator, with an enlargement

Figure 8.9. Uniform mesh and geometric mesh of the fan

Figure 8.10. The discrete model of a connecting rod and the discrete model of a car

Figure 8.11. The sharp edges and corners identified initially (on top). The extension of the sharp lines and the reclassification of certain corners (bottom)

Figure 8.12. The discrete model of the connecting rod with the sharp edges that were detected shown in red

Figure 8.13. Details of the identification of the sharp edges at the level of the door-handle

Figure 8.14. Above: the sharp edges detected. On the bottom: the model with these edges shown in red

Figure 8.15. A mechanical part, the starting element and the neighboring rings of the unfolding process

Figure 8.16. Progress of the unfolding process, viewed at several iterations

Figure 8.17. The discrete academic model, the starting element and the neighboring rings

Figure 8.18. The resulting unfolding with the map of constraints

Figure 8.19. The discrete matrix of a mechanical part, the starting element and the neighboring rings

Figure 8.20. The first discrete, stamping matrix: unfolding and map of constraints

Figure 8.21. The discrete matrix of a complex mechanical part, the starting element with the neighboring rings and the zone of interest enlarged

Figure 8.22. Second discrete stamping matrix: unfolding, map of constraints and enlargement of the zone of interest

Figure 8.23. A discrete geological layer presenting faults and neighboring rings relative to the starting element (in the middle, in red)

Figure 8.24. The unfolding of the layer by closing up the faults

Figure 8.25. A discrete mask and its unfolding with the map of constraints

Figure 8.26. The uniform meshes of the domain of parameters (above) and their application (projection) on the mask (below)

Figure 8.27. The discrete model of a globe of Earth, with seams and neighboring rings relative to the starting element (in the center, in red)

Figure 8.28. The sphere unfolded or spread out flat

Figure 8.29. The raw information of the model of this head results from a marching-cube method (left) with its inevitable “staircases” and the denoising of this information using a low-pass filter

Figure 8.30. The simplified discrete models obtained for different Hausdorff distances

Figure 8.31. The initial model of

Yoda

and the discrete models obtained for different simplification rates

Figure 8.32. An enlargement at the level of the head of the initial model and the discrete models obtained for different simplification rates

Figure 8.33. From top to bottom: the discrete models of a brain, the cranial bone and the corresponding cranium. From left to right: the raw data (marching-cube), a fine discrete model, then simplified

Figure 8.34. Localization of cerebral activity

Figure 8.35. On the left: the initial (raw) discrete model that is used to define the third-degree patches shown in Figure 8.36. On the right: the discretization of the corresponding geometric support

Figure 8.36. Third-degree patches constructed from an initial model

Figure 8.37. The initial discrete model of a steering rod presenting sharp edges with (left) and without (right) the trace of the edges of the faces

Figure 8.38. Third-degree patches constructed from the initial model

Figure 8.39. The geometric support for the steering rod, with (on the left) and without (right) the trace of the edges of the faces

Figure 8.40. Discrete initial model for an aeroplane (on top) and the discretization of its geometric support (bottom)

Figure 8.41. Enlargement of the initial model (left column) and an enlargement of the support (right column)

Figure 8.42. Statue type objects, with three classic examples. A model of the famous “Happy Buddha”, 500,000 points, a model of statue “Lucy”, 14 million points, and a model of Michelangelo’s “David”, 28 millions points

Figure 8.43. Some enlargements of the Happy Buddha model, the head and one of the feet on the base of the statue

Figure 8.44. An enlargement showing the triangulation of the head of the Lucy model

Figure 8.45. Some enlargements of the model of David – the head and a foot on the base of the statue

Figure 8.46. Anatomical objects: on the left – a model of a “hip”. On the right – a model of a “hand”

Figure 8.47. Enlargement of the hip and hand models

Figure 8.48. Mechanical objects. From left to right, the “tot” model, the “sip” model, the “rob”, model and the “boo” model. The edges in red are the boundary edges. The points in yellow are the lost points

Figure 8.49. Mechanical objects – enlargements. From top to bottom and left to right: the “tot”’model, the “sip” model, then the “ rob” model, and the “boo” model

Figure 8.50. Enlargements of mechanical objects along with the map of angular defaults

Figure 8.51. From top to bottom: the initial point cloud, the 3D reconstruction, the textured, discrete model with reflected light and this textured model with geometric curvatures

Figure 8.52. Above: a part of the point cloud. Below: the 3D reconstruction with the horizontal characteristic lines

Figure 8.53. 3D reconstruction of the whole model (street over a length of 300 m)

Chapter 9: A Few Basic Algorithms and Formulae

Figure 9.1. Evaluation of the midpoint for a curve of degree 4, is the solution. We construct the four corresponding to the chosen value of t, then the three , then the two and finally, the single , which is the desired solution

Figure 9.2. Evaluation of the point (, , ) for a triangular patch of degree 3, on the left. Evaluation of the point (, ) for a quadrilateral patch of degree 3, on the right.

Figure 9.3. Evaluation of the point (, ) for a quadrilateral patch of degree 3 with the same method of writing as in algorithm [9.6]. On the left, the subdivision at u, on the right, the subdivision of this subdivision at v. The inset: the subpatch, bottom-left, resulting from the refinement of the initial patch

Figure 9.4. Turning around the vertex, in one direction or the other direction depending on the next element considered. The figure indicates the starting triangle, denoted by Start and the local numbering of the vertices

Figure 9.5. Localization problem. On the left: the principle of the algorithm makes it possible to find the solution starting from an element k

0

. We are looking at an academic case, where all goes smoothly and we can move without difficulty from one element to another until convergence. On the right: the seven regions defined by the edges of a triangle

Figure 9.6. Localization problem. On the left, the point P is within the triangle [123], three positive areas; in the middle, a negative area; on the right: two negative areas and, thus, two choices to continue the pathway

Figure 9.7. Localization problem. The point P was declared to be inside the triangle [123], P

c

like P

calcul

, while it is within the triangle [243], P

e

like P

exact

Figure 9.8. Localization problem. Apart from the top left, the point P is separated from the starting element by an empty zone and the pathway comes across the boundary. For the two cases other than the solution on the bottom right, the box contains other vertices and we may find other starting elements which, through the pathway, leads to the solution. On the other hand, on the bottom right, the box (towards P) is empty of vertices and thus of potential seeds. The idea of encoding the elements (and not the vertices) in the boxes results from this

Guide

Cover

Table of Contents

Begin Reading

Pages

C1

2

3

4

5

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

G1

G2

G3

e1

For Anahita, Amitisse and Hilda

Geometric Modeling and Applications Set

coordinated byMarc Daniel

Volume 1

Meshing, Geometric Modeling and Numerical Simulation 1

Form Functions, Triangulations and Geometric Modeling

Houman Borouchaki

Paul Louis George

First published 2017 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2017

The rights of Houman Borouchaki and Paul Louis George to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2017948827

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-78630-038-6

Foreword

The “Geometric Modeling and Applications” series is made up of five volumes of research on geometric modeling. The act of geometric modeling is an age-old one. To look at a few key points in its history: geometrists in antiquity devoted themselves to it, though, of course, it had a different form from that which we know today; Descartes, in the mid-17th Century, worked on partitioning of planes; and Voronoï established concepts relating to this toward the end of the 19th Century.

But geometric modeling, as we understand it now, can be considered to be linked to the use of computers, especially since this tool has become ubiquitous. We are tempted to fix the scientific recognition of this activity to the date of the “First Conference on Computer Aided Geometric Design”, which took place in March 1974 at the University of Utah. This was organized by R. Barhnill and R. Riesenfeld, whose presentations may be found in the book “Computer Aided Geometric Design, Academic Press, 1974”, which clearly associates geometric modeling with the computer.

Since then, many detailed and high-quality books have been published in this field. One of the pioneering works was, undoubtedly, that authored by D. Faux and M. Pratt, “Computational Geometry for Design and Manufacture, Ellis Horwood Publishers, 1979”. Some books went through several editions, taking note of the advances made in research in the field. In this context, bringing out a new general book on the subject would mark no significant scientific progress.

Moreover, for any objet or entity that is to be modeled, there is no single geometric model. Instead, there are several geometric models, each being adapted to the processes to be carried out. For example, the model to finely analyze the shape of an object is necessarily different from models that are used for mechanical computations on this same object. We have, therefore, chosen to focus on specific points of research in fields that we find particularly important. Thus, the five references given here, written by specialists, bring you up to date on advances in research in five domains:

“

Constraints and geometric modeling

”, by

Dominique Michelucci, Pascal Schreck

and

Pascal Mathis

, looks at geometric problems that can be approached by describing the constraints, geometric or more complex, that a solution must verify, rather than directly giving the geometric definition of such a solution.

“

Geometric modeling of fractal forms CAD

”, by

Christian Gentil, Dmitry Sokolov and Gilles Gouaty

, discusses the definition of fractal forms: this formalism makes it possible to reuse smooth forms of geometric models that are classic today to define forms that have not yet been explored till present.

“

Meshing, geometric modeling and numerical simulation

”, in two volumes, by

Houman Borouchaki and Paul-Louis George

, details methodologies advanced for the construction of meshes and geometric modeling for numerial simulation with applications, especially in mechanics.

“

Geometric and Topological Mesh Feature Extraction for 3D Shape Analysis

”, by

Jean-Luc Mari, Franck Hétroy-Wheeler and Gérard Subsol

, studies the analysis of three-dimensional-meshed shapes via the extraction of characteristics, both geometric and topological. The fields of application are also detailed to illustrate the transdisciplinary nature of this work.

“

Relevant Triangulations and Samplings for 3D Shapes

”, by

Raphaëlle Chaine and Julie Digne

, discusses sampling, meshing and compression of free forms from a large quantity of real data from a virtual, interactive deformation process.

These are books that present recent research. The reader can find, in the general books on geometric modeling that were mentioned before, elements to fill any gaps they may have and to enable them to read the books in this series.

Happy reading.

Marc DANIEL

Introduction

Triangulations and, more precisely, meshes, with the subtle difference that separates these two entities, lie at the heart of any number of problems that arise from varied scientific disciplines. A triangulation or a mesh is a discrete representation, using simple geometric elements (triangle, quadrilateral, tetrahedron, etc., any arbitrary polygon or polyhedron), of a domain that may be an object or a region of which we want a discrete, spatial description. There are, thus, many applications, including numerical simulations of any kind of physical problem, though not restricted to these. In particular, a discrete representation of a (volumetric) object or a surface may simply be seen as a geometric modeling problem as is. This book adopts a double point of view, as indicated by its title, and we will look both at the use of meshes in numerical simulations (the finite element method, especially) with, of course, the underlying constraints, as well as the use of these meshes for the (discrete) modeling of geometry.

The literature on triangulations and meshes may be classified in two chief categories: one more purely mathematical and geometric, the other more oriented toward industrial applications (numerical simulations) with, of course, though not always, relations between these categories.

The first point of view is covered by the computation geometry community, which studies (among others) Delaunay triangulations in all cuts, definitions, properties, construction algorithms and the complexity of these algorithms. They also study some applications of these triangulations. Nonetheless, relatively recently, mesh generation problems are also being studied, but under a more theoretical angle, generally relating to situations that allow for the use of Delaunay triangulations for which robust construction methods as well as interesting geometric properties have been known for a long time. This (somewhat monotheistic) philosophy necessarily imposes limits on the nature of the problems worked (workable). The first reference book on these subjects is that of Preparata and Shamos [Preparata, Shamos-1985] published in 1985. This was followed by several others, among which we cite two by Edelsbrunner [Edelsbrunner-1987] and [Edelsbrunner-2001], that of Yvinnec and Boissonnat [Boissonnat, Yvinec-1997], by Dey [Dey-2007] and winding up the list with the book by Cheng et al. [Cheng et al. 2012], which was published in 2012. With a few exceptions, the orientation chosen by these references is not always guided by the preoccupations of mathematicians, engineers and the world of numerical simulation in general.

It is this very need for numerical simulations, in particular (and historically) in solid or fluid mechanics, that has led to the emergence of a “meshing” community among mathematicians and engineers. Without fear of contradiction, we can state that the very first book on meshes that was seen from this point of view is that of Thompson et al. [Thompson et al. 1985], which was also published in 1985. This book essentially discusses structured meshes or grids1 while the first truly generalist book, discussing all types of meshes, structured or not, is that by George [George-1991], which dates back to 1991. Over the years and with the evolution of computers and methods as well as the increasingly complex nature of the meshes to consider, other books have been published. Let us mention books by George and Borouchaki [George, Borouchaki-1998], published in 1997, which revisits meshing methods based on Delaunay algorithms; by Carey [Carey-1997], also in 1997, which gives a very pedagogic presentation of methods; by Topping and co-authors [Topping et al. 2004], in 2004, cited in order to be exhaustive; by Frey and George [Frey, George-2008], in 2000, with a second edition in 2008, which returns to the general view and incorporates newly appeared techniques; by Löhner [Löhner-2008], in 2002, with a second edition that came out in 2008, which abounds in innovative details; up to the recent book by Lo [Lo-2015], published in 2015, which, among others, sheds new light on some problems. In this context, we may wonder what motivated the writing of this book. We will attempt to answer this question (and also try, by doing so, to arouse the reader’s curiosity).

The first observation is that the few books on this subject are already either a little old or rather classic in the way they discuss the approaches and the methods concerning the many questions linked to meshes. The second remark is that, evidently, new questions have appeared relatively recently, e.g. everything related to (finite) elements or patches of higher degrees, metrics and their links to interpolation errors, geometric modeling by meshes, numerical simulation via advanced methods (adaptation of meshes) and so on. This remark immediately calls forth another: we will resolutely adopt a double point of view by considering finite elements (or the constitutive elements of a mesh) as geometric patches and vice versa, thus establishing a link between the Lagrange world of finite elements and the Bézier world of CAD. This choice, as we will see, noticeably changes the manner in which we perceive the problems and, consequently, the manner in which we try to find solutions. In this spirit, this book in two volumes, beyond a set of subjects that we may qualify as classic (and, thus, essential), approaches many subjects that are very recent or even completely novel. Moreover, and this may be more surprising (and certainly rare), some methods (which we find in the literature) have been deliberately left out as they were deemed to not be of great interest and, a contrario, some methods are described in a manner that is, at the very least, nuanced and even critical. Indeed, it seemed pertinent to share our perception, even though this is subjective, up to a point, of these methods, perhaps to prevent the reader from going down paths that we think are dead ends. Having specified this, this book provides the necessary basis for a course on meshes and related problems at the masters level and it may serve as a technical reference for engineering students in science and, more generally, engineers using numerical simulations. We will give a brief description of the content of the chapters in both volumes.

Volume 1:

We first give a chapter-wise overview of the first volume of this book. In the first three chapters, this volume introduces the basic concepts related to finite elements seen through their shape functions either as finite elements or as patches. In addition to the classic expression via Lagrange polynomials (complete, reduced or rational) (Chapter 1), we give the equivalent formulation based on Bézier forms (Chapter 2), which makes it possible to easily find the conditions for the geometric validity of these finite elements (or patches) whether they are straight or curved and whatever their degree (Chapter 3). Triangulation problems are the subject of the next three chapters, where we specify vocabulary and the basic concepts that make it possible to describe the different construction methods for any triangulation (Chapter 4), Delaunay triangulation (Chapter 5) as well as the triangulation (of a domain) with constraints (Chapter 6). In the next two chapters, we use the concepts introduced earlier to discuss the vast problem of geometric modeling of a domain in its various aspects. Geometric modeling, from our point of views (meshes and numerical simulations), consists of construction of a discrete representation from a continuous representation and vice versa. Different methods are described in Chapters 7, while Chapter 8 gives several significant examples for the application of these methods. Chapter 9 brings together some basic algorithms and formulae related to finite elements (patches) and triangulations, to persuade the reader to go beyond a theoretical viewpoint, to a practical viewpoint, which we believe is essential.

Volume 2:

We share the contents of Volume 2 [Borouchaki-2018] of this book in advance. This volume (finally) approaches mesh problems and begins with a detailed description of the concept of metric, a concept which will be seen to be fundamental in all that follows. The first two chapters, Chapters 1 and 2, thus focus on metrics. We introduce the concept of metric, we demonstrate their properties and their relations with the geometry of elements of a mesh and how to control interpolation errors during the resolution of a problem (by finite elements). The construction methods of meshes and their optimization are the focus of the following five chapters: Chapter 3 (mesh for a curve), Chapter 4 (simplicial meshes), Chapter 5 (non-simplicial meshes), Chapter 6 (meshes of higher degree) and Chapter 7 (optimizing meshes). We will then discuss the large subject of the adaptation of meshes, controlling the solutions via error estimates and corresponding interpolation metrics in Chapter 8. The use of a dose or a certain dose of parallelism (based on its multiple forms) is seen through Chapter 9. Chapter 10 illustrates, using concrete examples, a series of applications of the methods and methodologies introduced and described through the different chapters of both volumes of this book. As in Volume 1, the final chapter, Chapter 11, gives practical observations on some of the algorithms from Volume 2, especially how to use and manipulate metrics.

Finally, at the end of this second volume, we sketch out future prospects.

Acknowledgments.

We are especially grateful to two then-doctoral students who willingly helped in developing this book. Nicolas Barral helped us through his expertise with Maple to resolve systems that we encountered during the construction of Serendipity elements. Victorien Menier is the author of most of the figures that illustrate this book. We also wish to thank Peha for his magnificent free-hand images, illustrating the impossibility of triangulating certain polyhedra without adding internal vertices. And, of course, we would also like to thank everyone in the common Inria2 and UTT3, Gamma3 team: researchers, engineers and doctoral students, whose work contributed to the development and consolidation of various subjects discussed in this book.

1

. The grid-type meshes are generated by solving partial derivative equations, for example elliptical equations. It must be noted that other, more recent books on this theme, followed this pioneering work, but have not been mentioned here.

2

. Institut National de Recherche en Informatique et en Automatique.

3

. Université de Technologie de Troyes.