Page 299 - Computational Fluid Dynamics for Engineers

9.7 Unstructured Grids 289

the solution of Partial Differential Equations in fluid dynamics. The advantage
of structured grids is the simplicity and the straightforward treatment of the
grid in the solution formulation. The disadvantages are the mesh generation
constraints for complex configurations. Unstructured grids can be generated
faster on most complex domains. Mesh refinement can be done without diffi-
culties, locally and adaptively. Storage of the grid data (it requires information
on which node is neighbor to which) takes far more memory than that of a
structured grid, and therefore hinders parallelization of computer codes.

9.7.1 Delaunay Triangulation
In structured grids, the connections between points are defined automatically
given the (i,j, k) ordering. Such ordering does not exist in unstructured grids.
Therefore, connections between points, in addition to the position of points, have
to be defined by an unstructured grid method. Delaunay triangulation methods
use a particularly simple criterion for connecting points to form conforming,
non-intersecting elements. The geometrical construction has been known for
many years, but was used only recently for CFD grid generation. The geometri-
cal criterion provides only a mechanism for connecting points. The task of point
generation must be considered independently. Grid generation by Delaunay tri-
angulation involves therefore two distinct problems: point connection and point
creation.
In 1850, Dirichlet proposed a method for decomposing systematically a given
domain, in arbitrary space, into a set of packed convex regions [7]. For a given
set of points P, the space is subdivided into regions in such a way that each
region is the space closer to a point P than to any other point. This geometrical
construction of tiles is known as the Dirichlet tessellation. The tessellation of a
closed domain results in a set of non-overlapping convex regions called Voronoi

—*

Fig. 9.17. Voronoi diagram and Delaunay
triangulation (dashed line triangles) of a
set of points.