Introduction - Finite Element Mesh Generation - page 6

based on Poisson's equation with a source term, mapping and removal of points and genera-
tion of random points with different densities were developed. Moreover, a touch on the
three-dimensional problems primarily by the mapping techniques has also received quite
some attention.
On the other hand, there was also substantial progress in many auxiliary techniques
associated with the finite element mesh generation, namely, the node renumbering schemes
for the reduction of matrix profile in the resolution of a system of linear equations (Cuthill
1972; Collins 1973; Akhras and Dhatt 1976; Lai et al . 1996; Lai 1998; Esposito et al .
1998; Kaveh and Bondarabady 2002; Fujisawa et al. 2003; Lim et al. 2006, 2007; Boutora
et al . 2007; Wang et al. 2012), how boundary points and a desired point density for differ-
ent regions are prescribed, the data input formats for mesh generation, etc. Data input for
finite element mesh generation in batch mode and interactive mode was developed, and the
latter, after years of evolution, can now be regarded as a proper model building CAD sys-
tem. Sparked off by the review of Thacker (1980), unstructured mesh generation thrived in
the early 1980s mainly driven by the development of the three popular unstructured mesh
generation schemes, namely, the Delaunay triangulation, AFT and Octree decomposition.
The theoretical basis of Delaunay triangulation was established a long time ago by Dirichlet
(1850), Voronoi (1908) and Delaunay (1934), and an efficient and robust construction algorithm
by point insertion was only developed in 1981 by Bowyer and Watson. However, Cavendish
(1974), Lawson (1977) and Cavendish et al. (1985) were among the earliest to employ the
method formally for 2D and 3D finite element mesh generation. Delaunay triangulation will
only give the convex hull of the given point set, and for finite element mesh generation, geo-
metrical and topological constraints on the boundary have to be enforced. Conforming and
fully constrained Delaunay triangulations were studied, respectively, by Baker (1989b), Chew
(1989) and George et al . (1990, 1991). Mesh generation over curved surfaces by means of para-
metric co-ordinates and anisotropic metric tensor to specify the size and shape of the elements
was presented by Borouchaki and George (1996). Generation of anisotropic meshes in three
dimensions by Delaunay triangulation coupled with AFT was proposed by Frey et al . (1998).
Delaunay triangulation algorithms by parallel processing were developed by Blelloch et al.
(1999), Chrisochoides and Nave (2003) and Lo (2012a,b), and algorithms for Delaunay trian-
gulation of highly non-uniform distribution of large point sets were put forward by Lo (2013a).
The essence of AFT is not where mesh generation is started, whether it is from the bound-
ary or radiating from an interior point, but the partition of the problem domain into a
meshed zone and an unmeshed zone clearly delineated by the generation front, which is the
common moving boundary between the zones. While the meshed and unmeshed parts can
take any flexible arbitrary shape and form, and each of which may consist of several dis-
connected pieces, the frontal process allows us to focus on element generation at the front,
which is one dimension less than the problem domain, and to pay no more attention to the
meshed zones in which the mesh has already been generated. Mesh generation over arbitrary
planar domains by AFT was presented by Lo (1985); in three dimensions by Lohner and
Parikh (1988), Peraire et al . (1988) and Lo (1991b,c) and over surfaces by Lo (1989a), Lau
and Lo (1996) and Lee (1999). Apart from direct mesh generation of simplicial elements on
2D and 3D surfaces, the advancing-front (ADF) concept can also be applied to many mesh-
related operations such as the generation of quadrilateral meshes (Zhu et al . 1991a; Lee and
Lo 1994; Owen et al . 1999), hexahedral elements (Blacker and Stephenson 1991; Owen
and Saigal 2000), combined Delaunay-ADF approach (Borouchaki et al . 2000a), surface
intersection (Lo 1995), ellipse and sphere packing (Lo and Wang 2005c,d) and merging of
tetrahedral and hexahedral meshes (Lo 2012c, 2013c).
Octree decomposition (Yerry and Shephard 1984) as a method for finite element mesh
generation was the direct extension of the Quadtree (Yerry and Shephard 1983) in two to