Generation of Computational Mesh for Haemodynamics Analysis - Computational Hemodynamics: Theory, Modelling and Applications - page 162

Fig. 6.10 A triangular mesh based on Delaunay triangulation. Coloured circumcirlces highlight
the relationship between the triangle points and the absence of any external nodal points inside
the circumcircle

To produce Delaunay triangulations an algorithm to detect when a grid point is
within a triangle's circumcircle and an efficient data structure for storing triangles
and edges is required. An approach is to first mesh the boundary edges, then repeat-
edly add one node at a time inside the surface face; each time re-triangulating (or
redefining) the affected triangles locally to maintain the Delaunay criterion. In 3D
the Delaunay triangulation for 2D is extended naturally to three dimensions by con-
sidering the circumsphere ( circumscribing sphere ) associated with a tetrahedron.
For in-depth descriptions of this method, the reader is strongly encouraged to refer
to the classical paper by Shewchuk (2002), a review paper by Mavriplis (1997) and
a topic by de Berg et al. (2008).

6.2.6 Quadtree/Octree Subdivision

Mesh generation by the quadtree (2D geometries) or octree (3D geometries) method
is based on the divide-and-conquer principle. In quadtree, a 2D shape is recursively
subdivided into 4 smaller regions or quadrants, and these regions may be rectan-
gular or any arbitrary shape. Each smaller region is then subdivided until it meets
some criterion, e.g. size of cell smaller or the number of cells greater than a certain
value, or a homogeneous attribute. An example for a quadtree subdivision given
for 90 o bend is shown in Fig. 6.11 . The vertices of the quadtree structure are used
as nodal points, and the tree quadrants are divided into rectangular elements. The
quadtree cells intersecting the boundary must be displaced or wrapped in order to
coincide with the boundary.