Page 302 - Computational Fluid Dynamics for Engineers

292 9. Grid Generation

(a) (b) (c)
Fig. 9.19. Application of Delaunay triangulation to the generation of unstructured grid
in the space between two concentric ellipses; (a) construction of the convex hull and initial
Delaunay triangulation; (b) Construction after removal of convex hull points; (c) Final
Delaunay triangulation of points from a structured background grid.

Fig. 9.19a yields the triangulation shown in Fig. 9.19b. Although Fig. 9.19b
represents a valid triangulation of the points that define the two concentric
ellipses, these triangles span the entire region and are inappropriate for any
form of analysis. It is necessary therefore necessary to create more points inside
the domain.
The additional points for connection by the Delaunay algorithm can be cre-
ated by a variety of different techniques. For example, in the case of the two
ellipses, a structured background grid can be generated and the set of points then
connected together to form the grid, as shown in Fig. 9.19c. Another method
is the creation of points by grid superposition and successive subdivisions. The
basic idea is to superimpose a regular grid over the domain. The regular grid
can be generated using a data structure that allows point density in the regular
grid to be consistent with point spacing at the boundary. In general, this ap-
proach results in good spatial discretization in the interior of the domain, but
in the vicinity of boundaries the grid quality can be poor. Many other tech-
niques for point insertion can be found in the extensive literature available on
unstructured grids, see [11].

9.7.2 Advancing Front Method
Another very popular family of triangle and tetrahedral grid generation algo-
rithms is the advancing front, or moving front method. One contributor to this
method is Rainald Lohner [12]. In this method, the tetrahedra are built progres-
sively inward from the triangulated surface. An active front is maintained where
new tetrahedra are formed. Figure 9.20 is a simple two-dimensional example of
the advancing front, where triangles have been formed at the boundary. As the
algorithm progresses, the front will advance to fill the remainder of the area
with triangles. For each triangle edge on the front, an ideal location for a new
third node is computed. Also determined are any existing nodes on the front
that may form a well-shaped triangle with the edge. The algorithm selects either