Mesh Generation E-Book

Pascal Frey

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

Seitenzahl: 1412

Veröffentlichungsjahr: 2013

Beschreibung

The aim of the second edition of this book is to provide a comprehensive survey of the different algorithms and data structures useful for triangulation and meshing construction. In addition, several aspects are given full coverage, such as mesh modification tools, mesh evaluation criteria, mesh optimization, adaptive mesh construction and parallel meshing techniques. This new edition has been comprehensively updated and also includes a new chapter on mobile or deformable meshes.

Leseprobe

Contents

Introduction

Symbols and Notations

1 General Definitions

1.1 Covering-up and triangulation

1.2 Mesh, mesh element, finite element mesh

1.3 Mesh data structures

1.4 Control space and neighborhood space

1.5 Mesh quality and mesh optimality

2 Basic Structures and Algorithms

2.1 Why use data structures

2.2 Elementary structures

2.3 Basic notions about complexity

2.4 Sorting and searching

2.5 One-dimensional data structures

2.6 Two and three-dimensional data structures

2.7 Topological data structures

2.8 Robustness

2.9 Optimality of an implementation

2.10 Examples of generic algorithms

3 A Comprehensive Survey of Mesh Generation Methods

3.1 Classes of method

3.2 Structured mesh generators

3.3 Unstructured mesh generators

3.4 Surface meshing

3.5 Mesh adaptation

3.6 Parallel unstructured meshing

4 Algebraic, PDE and Multiblock Methods

4.1 Algebraic methods

4.2 PDE-based methods

4.3 Multiblock method

5 Quadtree-octree Based Methods

5.1 Overview of spatial decomposition methods

5.2 Classical tree-based mesh generation

5.3 Governed tree-based method

5.4 Other approaches

5.5 Extensions

6 Advancing-front Technique for Mesh Generation

6.1 A classical advancing-front technique

6.2 Governed advancing-front method

6.3 Application examples

6.4 Combined approaches

6.5 Extensions

7 Delaunay-based Mesh Generation Methods

7.1 Voronoï diagram and Delaunay triangulation

7.2 Constrained triangulation

7.3 Classical Delaunay meshing

7.4 Other methods

7.5 Isotropic governed Delaunay meshing

7.6 Extensions

8 Other Types of Mesh Generation Methods

8.1 Product method

8.2 Grid or pattern-based methods

8.3 Optimization-based method

8.4 Quads by means of triangle combination

8.5 Quads by means of a direct method

8.6 Hex meshing

8.7 Miscellaneous

9 Delaunay Admissibility, Medial Axis and Applications

9.1 Delaunay-admissible set of segments in 2

9.2 Delaunay-admissible set of segments in 3

9.3 Delaunay-admissible set of triangular faces

9.4 Medial axis

9.5 Mid-surface

9.6 Applications

10 Quadratic Forms and Metrics

10.1 Bilinear and quadratic forms

10.2 Distances and lengths

10.3 Metric-based operations

10.4 Metric construction

11 Differential Geometry

11.1 Metric properties of curves and arcs

11.2 Metric properties of a surface

11.3 Computational issues about surfaces

11.4 Non-linear problems

12 Curve Modeling

12.1 Interpolation and smoothing techniques

12.2 Lagrange and Hermite interpolation

12.3 Explicit construction of a composite curve

12.4 Control polygon based methods

12.5 Bézier curves

12.6 From composite curves to B-splines

12.7 Rational curves

12.8 Curve definitions and numerical issues

12.9 Towards a “pragmatic” curve definition?

13 Surface Modeling

13.1 Specific surfaces

13.2 Interpolation-based surfaces

13.3 Tensor product and control polyhedron

13.4 Triangular patches and Bézier triangles

13.5 Other types of patches

13.6 Composite surfaces

13.7 Explicit construction of a composite surface

14 Curve Meshing

14.1 Meshing a segment

14.2 Meshing a parametric curve

14.3 Curve meshing using a discrete definition

14.4 Re-meshing algorithm

14.5 Curves in 3

15 Surface Meshing and Re-meshing

15.1 Curve meshing (curve member of a surface)

15.2 First steps in surface meshing

15.3 A single patch

15.4 Multi-patches surface (patch-dependent)

15.5 Multi-patches surface (patch-independent)

15.6 Ill-defined multi-patches surface

15.7 Molecular surfaces

15.8 Surface reconstruction

15.9 Discrete surface (re-meshing process)

16 Meshing Implicit Curves and Surfaces

16.1 Review of implicit functions

16.2 Implicit function and meshing

16.3 Implicit curve meshing

16.4 Implicit surface meshing

16.5 Extensions

17 Mesh Modifications

17.1 Mesh (geometric) modifications

17.2 Merging two meshes

17.3 Node creation and node labeling

17.4 Renumbering issues

17.5 Miscellaneous

18 Mesh Optimization

18.1 About element measurement

18.2 Mesh quality (classical case)

18.3 Mesh quality (isotropic and anisotropic case)

18.4 Tools for mesh optimization

18.5 Strategies for mesh optimization

18.6 Computational issues

18.7 Application examples

19 Surface Mesh Optimization

19.1 Quality measures

19.2 Discrete evaluation of surface properties

19.3 Constructing a geometric support

19.4 Optimization operators

19.5 Optimization methods

19.6 Application examples

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.3 Error estimation and convergence

20.4 Stiffness matrix and right-hand side

20.5 A few examples of popular finite elements

21 Mesh Adaptation and H-methods

21.1 Control space (background mesh)

21.2 Adaptation by local modifications

21.3 Global isotropic adaptation method

21.4 Global anisotropic adaptation method

21.5 Adaptation

21.6 Application examples

22 Mesh Adaptation and P orHp-methods

22.1 P2 mesh

22.2 P-compatibility

22.3 Construction of P2 elements

22.4 Elements of higher degree

22.5 P-methods and Hp-methods

23 Moving or Deformable Meshing Techniques

23.1 Rigid body motion

23.2 ALE methods

23.3 Mesh deformation

23.4 Interface tracking

24 Parallel Computing and Meshing Issues

24.1 Partition of a domain

24.2 Parallel meshing process

24.3 Parallel meshing techniques

Bibliography

Index

First edition published in 2000 by Hermes Science Ltd Second edition published in Great Britain and the United States in 2008 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 Ltd 6 Fitzroy Square London W1T 5DX UK

www.iste.co.uk

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

www.wiley.com

© ISTE Ltd, 2008© Hermes Science Ltd, 2000

The rights of Pascal Jean Frey 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 Cataloging-in-Publication Data

Frey, Pascal Jean.

  [Maillages. English]

Mesh generation application to finite elements / Pascal Jean Frey, Paul-Louis George. -- 2nd ed.

     p. cm.

  Includes index.

  ISBN 978-1-84821-029-5

  1. Finite element method. 2. Numerical grid generation (Numerical analysis) 3. Triangulation. I.

George, Paul-Louis. II. Title.

  TA347.F5F6913 2008

  620.001′51825--dc22

2007046234

British Library Cataloguing-in-Publication Data

Introduction

Mesh generation techniques are widely employed in various engineering fields including those related to physical models described by partial differential equations (PDE). Numerical simulations of such models are intensively used for design, dimensioning and validation purposes. One of the most frequently used methods, among many others, is the finite element method (FEM). In this method, a continuous problem (the initial PDE model) is replaced by a discrete problem that can actually be computed thanks to the power of currently available computers. The solution to this discrete problem is an approximate solution to the initial problem whose accuracy is based on the various choices that were made in the numerical process.

The first step (in terms of actual computation) of such a simulation involves constructing a mesh of the computational domain (i.e., the domain where the physical phenomenon under interest occurs and evolves) so as to replace the continuous region by means of a finite union of (geometrically simple and bounded) elements such as triangles, quadrilaterals, tetrahedra, pentahedra, prisms, hexahedra, etc., based on the spatial dimension of the domain. For this reason, mesh construction is an essential pre-requisite for any numerical simulation of a PDE problem. Moreover, mesh construction could be seen as a bottleneck for a numerical process in the sense that a failure in this mesh construction step jeopardizes any subsequent numerical simulation.

Mesh construction in general and more precisely for numerical simulation purposes involves several different fields and domains. These include (classical) geometry, so-called computational geometry and numerical simulation (engineering) topics coupled with advanced knowledge about what is globally termed computer science. The above classification in terms of disciplines which can interact in mesh construction for numerical simulation clearly shows why this topic is not so straightforward. Indeed, people with a geometrical, a computational geometry or a numerical background may not have the same perception of what a mesh (and, a fortiori, a computational mesh) should be, and subsequently do not share a common idea of what a mesh construction method could be.

To give a rough idea of this problem, we mention, without in any way claiming to be exhaustive, some commonly accepted ideas about meshes based on the background of those considering the issue.

From a purely geometrical point of view, meshes are mostly of interest for the properties enjoyed by such or such geometrical item, a triangle for instance. In this respect, various issues have been investigated regarding the properties of such an element including aspect ratios, angle measures, orthogonality properties, affine properties and various related constructions (centroids, circumcenters, circumcircles, incircles, particular (characteristic) points, projections, intersections, etc.).

A computational geometry point of view mainly focuses on theoretical properties about triangulation methods including a precise analysis of the corresponding complexity. In this respect, Delaunay triangulation and its dual, the Voronoi’ diagram, have received much attention since nice theoretical foundations exist and lead to interesting theoretical results. However, triangulation methods are not necessarily suitable for general meshing purposes and must, to some extent, be adapted or modified.

Mesh construction from a purely numerical point of view (where, indeed, meshes are usually referred to as triangulations or grids) tends to reduce the mesh to a finite union of (simply shaped) elements whose size tends towards 0: “ Let be a triangulation where h tends to 0, then …, ” where is provided in some way or other (with no further details given on this point). The construction of is no longer a relevant problem if a theoretical study is envisaged (such as a convergence issue for a given numerical scheme).

In contrast to all the previous aspects, people actually involved in mesh construction methods face a different problem. Provided with some data, the problem is to develop methods capable of constructing a mesh (using a computer) that conforms to the needs of "numerical" and more generally "engineering" people. With regard to this, the above subscript h does not vanish, the domain geometry that must be handled could be of arbitrary complexity and a series of requirements may be demanded based on the subsequent use of the mesh once it has been constructed. On the one hand, theoretical results about triangulation algorithms (mainly obtained from computational geometry) may not be so realistic when viewed in terms of actual computer implementation. On the other hand, engineering requirements may differ slightly from what the theory states or needs to assume.

As a brief conclusion, people involved in “meshing” must make use of knowledge from various disciplines, mainly geometry and computation, then combine this knowledge with numerical requirements (and computational limitations) to decide whether or not an a priori attractive aspect (for a particular discipline) is relevant in a meshing process. In other words, good candidates for mesh construction activities must have a sound knowledge in various disciplines in order to be able to select from these what they really require for a given goal.

Fortunately, we should point out that meshing things are becoming increasingly recognized as a subject of interest in its own right, not only in engineering but also at universities as well. In practice the subject is being addressed in several places all over the world, and a numerous people are spending a great deal of time on it. A few specialized conferences and workshops do exist and papers on meshing technologies can be found in various journals. Currently a few books1 entirely (or substantially) devoted to meshing technologies are available.

Purpose and scope

The scope of this book is multiple and so are the potential categories of intended readers. As a first remark, we like to think that the theoretical background that is strictly necessary to understand the book is anything but specialized. We are confident that a reasonable knowledge of basic geometry, a touch of computational geometry and a good guess of what a numerical simulation is (for instance, some basic notions about the finite element method) provide a sufficient background for the reader to profit from this material. With regard to this, one of our objectives has been to make most of the presentations self-contained.

One issue underlying some of the discussions developed in the book was what material the reader might expect to find in such a book. A tentative answer to this point has led us to incorporate some material that could be judged trivial by readers who are already familiar with some meshing methods, yet we believe that its inclusion may well prove useful to less experienced readers.

We have introduced some recent developments in meshing activities, even if they have not necessarily been well validated (at least to the industrial standard), so as to allow advanced readers to initiate new progress based on this material.

It might be said that constructing a mesh for a given purpose (academic or industrial) does not strictly require knowing what the meshing technologies are. Numerous engineers confronted daily with meshing problems, as well as graduate students facing the same problem, have been able to complete what they need without necessarily having a precise knowledge of what the software package they are familiar with actually does. Obviously, this point of view can be refuted and clearly a minimum knowledge of the available meshing technologies is a key to making this mesh construction task more efficient. Finally, following the above observations, the book is intended for both academic (educational) and industrial purposes.

Synopsis

Although we could have begun by a general purpose introduction and led on to a presentation of classical methods, followed by a discussion of advanced methods, specialized topics, etc., we chose to structure the book in such a way that it may be read sequentially. Relevant ideas are introduced when they are strictly necessary to the discussion, which means that the discussion about simple notions is made easy while when more advanced discussions are made, the more advanced ideas are given at the same time. Also, some almost identical discussions can be found in several sections, in an attempt to make each section as self-contained as possible.

The book contains 24 chapters. The first three chapters introduce some general purpose definitions (Chapter 1) and basic data structures and algorithms (Chapter 2), then classical mesh generation methods are briefly listed prior to more advanced techniques (Chapter 3). The following chapters provide a description of the various mesh generation methods that are in common use. Each chapter corresponds to one type of method. We include discussions about algebraic, PDE-based or multi-block methods (Chapter 4), quadtree-octree based methods (Chapter 5), advancing-front technique (Chapter 6), Delaunay-type methods (Chapter 7), mesh generation methods for implicitly defined domains (Chapter 16) and other mesh generation techniques (Chapter 8) not covered by the previous cases. Chapter 9 deals with Delaunay-admissible curve or surface meshes and then discusses medial axis construction along with the various applications that can be envisaged based on this entity. Prior to a series of five chapters on lines, curves and surfaces, a short chapter concerns the metric aspects that are encountered in mesh generation activities (Chapter 10). As previously mentioned, Chapters 12 to 16 discuss curves and surfaces while Chapter 11 recalls the basic notions regarding differential geometry for curves and surfaces. One chapter presents various aspects about mesh modification tools (Chapter 17), then, two chapters focus on optimization issues (Chapter 18 for planar or volumic meshes and Chapter 19 for surface meshes). Basic notions about the finite element method are recalled in Chapter 20 before looking at a more advanced mesh generation problems, namely how to construct adapted, mobile or deformable meshes (Chapters 21, 22 and 23). Parallel aspects are discussed in Chapter 24. To conclude, an index is provided to the readers.

Acknowledgements

This work was carried out at the Gamma project, INRIA-Rocquencourt and was contributed to by many people in many ways. The authors would like to thank some of these people here. Friends and colleagues at INRIA, Frric Hecht, Patrick Laug, Eric Saltel and Maryse Desnous (who helped us for most of the figures that illustrate the discussion) were a great source of support and provided much of the technical material and illustrations for this work. Their comments and suggestions contributed greatly to its technical content.

The authors are especially indebted to Frédéric Noël(Université Joseph Fourier and Laboratoire des Sols Solides et Structures, Grenoble) who took the responsibility for the chapters devoted to curve and surface definitions and meshing. Bruce Simpson (Waterloo University, Ontario, Canada) must be thanked for his generous and significant contribution to this book in checking the consistency of the discussion. Mark Loriot (Distène, France) kindly accepted to help us with the part devoted to partitioning methods. Frédéric Eichelbrenner (ibid) helped us with surface meshing methods and Philippe Pébay (INSA, Lyon), through his PhD work, helped us for the chapter about Delaunay admissibility and medial axis construction. To finish, we would like to thank Frédéric Cazals (INRIA, Sophia Antipolis) for his help on the fundamentals of data structures and basic algorithms.

In addition to these people, several contributors were always willing to help us on various topics: Laurent Francez (Distène), Loïc (CNAM-INRIA), Éric Séveno (previously at INRIA), Rachid Ouatchaoui (EDF-INRIA) as well as Houman Borouchaki (UTT).

The first edition of this book is a translation of “Maillages. Applications aux éléments finis”, published by Hermès Science Publications, Paris, 1999. The translation was carried out by the two authors with the valuable help of Richard James whom we would like to thank here.

This second edition includes various corrections, improvements, a fully updated index together with a new chapter about mobile and deformable meshes due to Pascal Frey, currently Full Professor at the Université et Marie Curie.

Finally, let us mention, at this time, two websites devoted to meshing technologies and a website offering thousands of surface meshes for downloading:

http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html

http://www.andrew.emu.edu/user/sowen/mesh.html

http://www-c.inria.fr/gamma/download/

1 Probably the very first significant reference about mesh generation is the book by Thompson, Warsi and Mastin, [Thompson et al. 1985], authored in 1985, which mainly discussed structured meshes. A few years after, in 1991, a book by George, [George-1991], was written which aimed to cover both structured and unstructured mesh construction methods. More recently, a book authored in 1993 by Knupp and Steinberg, [Knupp, Steinberg-1993] together with a book by Liseikin, [Liseikin-2000], provided an updated view of structured meshes. In 1998, a book fully devoted to Delaunay meshing techniques, [George, Borouchaki-1997], appeared. Among books that contain significant parts about meshing issues, one can find the book authored by Carey in 1997, [Carey-1997].

Thus, it is now possible to find some references about mesh technology topics. In this respect, one needs to see the publication of the Handbook of Grid Generation, edited by Thompson, Soni and Weatherill, [Thompson et al. 1999], which, in about 37 chapters by at least the same number of contributors, provides an impressive source of information. To conclude, notice the publication of another collective work, “Maillage et Adaptation”, [George-2001], in the MIM (Mécanique et Ingénierie des Matériaux) series published by Hermes, Paris, together with a concise vulgarization book, “le maillage facile”, [Frey, George-2003]. More recently, the Encyclopedia of Computational Mechanics, edited by Stein, de Borst and Hughes, [Stein et al. 2004], offered a chapter on mesh generation.

Symbols and Notations

Notations

d

refers to the spatial dimension

set of integers, set of reals

Ω

refers to a closed geometric domain of

d

∂Ω

refers to the (discretized) boundary of Ω

Γ (Ω)

refers to the boundary of Ω

Γ, ∑

refers to a curve, a surface

γ, σ

refers to the parametrization of a curve, a surface

refers to a triangulation or a mesh

refers to a set of vertices

Const

refers to a constraint (a set of entities)

Conv

()

refers to the convex hull of

(Δ,

H

)

refers to a control space

K

refers to a mesh element

S

K

V

K

refers to the surface area, the volume of element

K

K

shape quality of mesh element

K

d

AB

, d(A,B)

(Euclidean) distance between

A

and

B

Euclidean length of segment

PQ

ι

ab

(normalized) length of edge

AB

Symbols

∇

gradient operator

Hessian tensor

|

a

|

absolute value

integer part or restriction

||·||

Euclidean length of a vector

[

a, b

]

a closed interval

〈

u, v

〉

dot product of two vectors

( · Λ ·)

cross product of two vectors

t

u

u

transposed (also

u

t

)

Abbreviations

ALE

Arbitrary Lagrangian Eulerian

BRep, F-Rep

Boundary Representation, Function Representation

CAD

Computer Aided Design

CSG

Constructive Solid Geometry

MAT

Medial Axis Transform

FEM

Finite Element Method

PDE

Partial Derivative Equation

NURBS

Non Uniform Rational B-Splines

LIFO

Last In First Out

FIFO

First In First Out

BST

Binary Search Tree

AVL

Adelson, Velskii and Landis tree

Chapter 1

General Definitions

Before going further, it seems important to clarify the terminology and to provide some basic definitions together with some notions of general interest. First, we define the covering-up of a bounded domain, then we present the notion of a triangulation before introducing a particular triangulation, namely the well-known Delaunay triangulation.

A domain covering-up simply corresponds to the naive meaning of this word and the term may be taken at face value. On the other hand, a triangulation is a specific covering-up that has certain specific properties. Triangulation problems concern the construction, of a covering-up of the convex hull of a given set of points. In general, a triangulation is a set of simplices, triangles in two dimensions, tetrahedra in three dimensions, with certain properties. If, in addition to a set of vertices, the boundary of a domain (more precisely a discretization of this boundary whose vertices are in the above set) is specified or, simply if any set of required edges (faces) is provided, we encounter a problem of constrained triangulation. In this case, the expected triangulation of the convex hull must contain these required items.

In contrast, the notion of a mesh may now be specified. Given a domain, namely defined by a discretization of its boundary, the problem comes down to constructing a triangulation that accurately matches this specific domain. In a way, we are dealing with a constrained triangulation but, now, we no longer face a convex hull problem and, moreover, the mesh elements are not necessarily simplices.

After having established triangulation and mesh definitions, some other aspects are discussed, including a suitable element definition (as an element is the basic component of both a triangulation and a mesh), finite element definition as well as mesh data structure definition which are the fundamental ingredients of any further processing (such as using a finite element method). In addition, we introduce some definitions related to certain data structures which are widely used in mesh construction and mesh optimization processes. To conclude, we propose measures of mesh quality and of mesh optimality.

Obviously this chapter cannot claim to be exhaustive. In fact, more specific ideas will be introduced and discussed as required throughout the book.

1.1 Covering-up and triangulation

Definition 1.1r is a simplicial covering-up of if the following conditions hold

(HO) The set of element vertices in r is exactly .

(H1), where K is a simplex.

(H2) The interior of every element K in r is non empty.

(H3) The intersection of the interior of two elements is an empty set.

Here is a natural definition. With respect to condition (H1) (where while not strictly necessary, we restrict ourselves to simplicial elements), one can see that is the open set corresponding to the domain that means, in particular, that . Condition (H2) is not strictly necessary to define a covering-up, but KeTr it is nevertheless practical with respect to the context and, thus, will be assumed. Condition (H3) means that element overlapping is proscribed.

Similarly, we will consider conforming coverings-up, referred to as triangulations.

Definition 1.2r is a conforming triangulation or simply a triangulation of if r is a covering-up following Definition (1.1) and if in addition, the following condition holds:

(H4) the intersection of two elements in r is either reduced to

Figure 1.1Conformal triangles (left-hand side) and non-conformal triangles (right-hand side). Note the vertex located on one edge in this case.

Remark 1.1For the moment, we are not concerned with the existence and possibly uniqueness of such a triangulation for a given set of points. Nevertheless, a theorem of existence will be provided below and, based on some specific assumptions, the particular case of a Delaunay triangulation will be described.