Edinburgh Parallel Computing Centre 3 Table of Contents

Version 1.0

Mesh Generation

Mark Filipiak

Edinburgh Parallel Computing CentreThe University of Edinburgh

Version 1.0

November 1996ecc

Version 1.0

Version 1.0

Table of Contents

1Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5

1.1Discretisation and mesh type . . . . . . . . . . . . . . . . . . .6

1.2Mesh characteristics . . . . . . . . . . . . . . . . . . . . . . . . . . .6

Structured meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9

2.1Boundary-fitted meshes. . . . . . . . . . . . . . . . . . . . . . . .9

2.2Problem solution on curved grids . . . . . . . . . . . . . .10

2.3Boundary fitting grids on a single block. . . . . . . . .11

2.4Algebraic grid generation: interpolation. . . . . . . . .11

2.4.1Transfinite interpolation (TFI). . . . . . . . . . . . 11

2.5PDE grid generation. . . . . . . . . . . . . . . . . . . . . . . . . .14

2.5.1Elliptic grid generation. . . . . . . . . . . . . . . . . . 14

2.6Implementation in 3D . . . . . . . . . . . . . . . . . . . . . . . .16

2.7Other methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

2.7.1Hyperbolic grid generation. . . . . . . . . . . . . . 17

2.7.2Parabolic grid generation. . . . . . . . . . . . . . . . 17

2.8Multiblock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17

2.8.1C, O, H grids . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.8.2Multiblock . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.9Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21

Unstructured Meshes . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

3.1Mesh requirements for the Finite Element Method23

3.2Mesh generation methods. . . . . . . . . . . . . . . . . . . . .24

3.2.1Decomposition and mapping . . . . . . . . . . . . 24

3.2.2Grid based methods . . . . . . . . . . . . . . . . . . . . 25

3.2.3Advancing front . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.4Delaunay triangulation . . . . . . . . . . . . . . . . . 31

3.2.5Other methods. . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2.6Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

Adaptive Meshing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

4.1Adaptive meshes. . . . . . . . . . . . . . . . . . . . . . . . . . . . .37

4.2Parallel mesh generation . . . . . . . . . . . . . . . . . . . . . .38

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .392345

Edinburgh Parallel Computing Centre3

Version 1.0

4Technology Watch Report

Version 1.0

1 Introduction

Continuous physical systems, such as the airflow around an aircraft, the stress con-

centration in a dam, the electric field in an integrated circuit, or the concentration of

reactants in a chemical reactor, are generally modelled using partial differential equa-

tions. To perform simulations of these systems on a computer, these continuum equa-

tions need to be discretised, resulting in a finite number of points in space (and time)

at which variables such as velocity, density, electric field are calculated. The usual

methods of discretisation, finite differences, finite volumes and finite elements, use

neighbouring points to calculate derivatives, and so there is the concept of a mesh or

grid on which the computation is performed.

There are two mesh types, characterised by the connectivity of the points. Structured

meshes have a regular connectivity, which means that each point has the same

number of neighbours (for some grids a small number of points will have a different

number of neighbours). Unstructured meshes have irregular connectivity: each point

can have a different number of neighbours. Figure 1 gives an example of each type of

grid. In some cases part of the grid is structured and part unstructured (e.g., in vis-

cous flows where the boundary layer could be structured and the rest of the flow

unstructured).

Figure 1: Structured mesh (left) and unstructured mesh (right).

In the rest of this chapter, the various discretisation methods are described, with their

mesh requirements. Chapter 2 describes the methods used to generate structured

meshes in simple domains (algebraic and elliptic methods) and the extension to com-

plex domans usng multblock. Chapter 3 descrbes methods used to generate

unstructured meshes, concentrating on the two main methods for producing triangu-

lar/tetrahedral meshes: advancing front and Delaunay triangulation. Chapter 4 gives

a very brief introduction to adaptive meshing.

Edinburgh Parallel Computing Centre5

Version 1.0

1.1 Discretisation and mesh type

The main discretisation methods are finite differences [8], finite volumes (which isequivalent to finite differences) [9] and finite elements [10]. To illustrate the methods,we consider the conservation form of the convection equation

ρ+ (ρU)=Swhereρ is the density,U is the velocity, andS is a source term. TheρU term is theflux ofρ.

The finite difference formulation approximates the derivatives using neighbouringpoints, e.g., for a regular, rectangular grid with spacingh in thex direction

ρ1≈--[ρ(xn+1)–ρ(xn)]h.

Although irregular gridscan be used for finite differences, regular grids are invariablyused. These lead to smple dfference schemes and effcent solvers (on vectormachines, for example). There can be problems with the finite difference scheme atcoordinate singularities for certain regular grids (e.g., spherical polar coordinate …… 此处隐藏：20958字，全部文档内容请下载后查看。喜欢就下载吧 ……