Civil Engineering Reference
In-Depth Information
derived from the required element size and shape quality as additional constraints in mesh
generation. In other words, for mesh generation, algorithms are as important as geometrical
computations (Edelsbrunner 1987), except, of course, for the Voronoi tessellation or the
duality of Delaunay triangulation, which is perhaps the only available interplay relationship
between geometry and topology in the connection of a set of spatial points arbitrarily distrib-
uted in space. The minimum angle, which is a valid shape measure of triangular elements, is
guaranteed in two-dimensional Delaunay triangulations. Based on Delaunay triangulation,
some bound on the smallest interior angle can be established for two-dimensional triangu-
lar meshes conforming to a given boundary of line segments. Yet, there is no analogous valid
shape measure for tetrahedral elements, which is guaranteed in three-dimensional Delaunay
triangulations, and as a result, Delaunay triangulations may not be the most appropriate
for numerical computations. Nevertheless, in mesh generation, it is really a crucial matter to
have the first valid mesh, which can always be enhanced, modified and optimised through
various transformations to turn it into a mesh apt for different purposes.
1.7 HISTORICAL DEVELOPMENT
The research on finite element mesh generation was formally started perhaps as early as the
beginning of the 1970s (Mackerle 2001), and a comprehensive review of the finite element
mesh generation schemes developed before 1980 was presented by Thacker (1980). In line
with the advance of the finite element method, the irregular computational grid became
increasingly popular for two reasons: (i) they allow points to be situated on curved boundar-
ies of irregularly shaped domains and (ii) they allow points to be distributed at the interior
of the domain with variable nodal spacing.
Co-ordinate transformation was an early attempt to map a regular reference domain
onto a geometrically irregular computational physical domain with a possibility of smooth
transition in element size. The finite difference method could also be applied to computa-
tional grids constructed based on co-ordinate transformation. The grids could be smoothed
such that each interior point ought to be at the position determined by the average of the
co-ordinates of its neighbours. In terms of mechanical analogy, the optimal grid should cor-
respond to the equilibrium configuration of a system of springs between grid points. This
idea of putting a node at the centroid of the surrounding polygon is in line with Laplace
smoothing widely used in mesh optimisation up to these days. The spring analogy for the
minimisation of energy has diverse applications nowadays in r-refinement (Li et al
.
2001;
Mosler and Ortiz 2007) and relocation of nodes by large displacements (Lin et al
.
2014).
Finite element interpolation as a means of mesh generation was presented by Zienkiewicz
and Phillips (1971) in which a curved domain is represented by a super-element, which could
be further divided into smaller elements following the element reference co-ordinates. The
blending function interpolation developed for local refinements to minimise the energy of
the system is related to the r-refinement procedure that we are using today. Decomposition
into simpler subregions, which is so intuitive as a means of mesh generation, was developed
in the early days for the generation of structured meshes. Removing points from a fine grid
generated by co-ordinate transformation and mapping a uniformly spaced zigzag boundary
onto a curvilinear grid were two ideas to generate meshes of non-uniform element sizes.
Before Delaunay triangulation became widely used, finite element meshes were con-
structed by joining points randomly generated using heuristic connection rules. The drag
method proposed by Park and Washam (1979) was perhaps the predecessor of the more
sophisticated extrude and sweep methods that we are still using for mesh generation. The
importance of gradation meshes was duly recognised, and various mesh generation methods
