Page 218 - Basic Structured Grid Generation

Unstructured grid generation 207

as it is created. Here we give the algorithmic steps of the AFT followed by a test-case
example.
The basic steps of the algorithm are as follows:

1. Set up the initial grid generation front, a set of oriented line-segments connecting
selected nodes on the boundary (in the direction of the orientation). Interpolate grid-
cell parameters for all the nodes in the front. Any nodes in the current position of
the front are called active.
2. Select the shortest side in the front, with length l.Avalue of δ is obtained by
averaging the interpolated values of δ corresponding to the two nodes.
3. Compute the position of an ‘ideal’ point K ideal on the perpendicular bisector of this
side such that an equilateral triangle is formed with K ideal as vertex.
4. Construct a circle with centre at K ideal and radius r given by the empirical formula

r = 0.8 ∗ δ ,where

0.55 ∗ l if δ< 0.55 ∗ l


δ = δ if 0.55 ∗ l δ 2.0 ∗ l
2.0 ∗ l if δ> 2.0 ∗ l,

and δ takes its local value. This formula helps to avoid the creation of highly
distorted triangles and to ensure geometrical compatibility.
5. Find the active nodes that lie within this circle, and list them in terms of their
distance from K ideal . The closest would be the best candidate for the third vertex
of the next triangular element.
6. If there are no such active nodes, the validity of the equilateral triangle with K ideal
as a vertex must be checked. This requires that:

• The point K ideal does not lie inside another triangular element.
• The sides of the new element do not intersect any of the existing sides of the
active front.
If the triangle is not valid, look for an active node giving a triangle with the best
shape.
7. If step 6 fails, re-order the front, take the second shortest active side, and go to
step 3.
8. If step 5 or step 6 succeeds, generate a new triangular cell and update the front
(from which the chosen shortest side has been deleted). In the case of step 6 being
successful with K ideal as a vertex (which then becomes one of the active nodes of
the new front), interpolate the grid generation parameter for this new point.
9. If the updated front is ‘non-empty’, go to step 3 and repeat the procedure. Continue
until there are no edges left in the front. Thus all edges have become passive instead
of active, and the computational domain has been completely triangulated.

As a simple example, we consider the simply-connected two-dimensional domain
shown in Fig. 8.23, consisting of a square ABDC from which a semi-circle has been
removed. The background grid consists of the two triangles ACD, ABD, and grid
generation parameters on the background grid are specified to be δ = 1, s = 1,
n x = 1, n y = 0, at each point A, B, C, D. Here we show a simple step-by-step method
of grid generation.