Civil Engineering Reference
In-Depth Information
MG and the quality of the elements rather than on the boundary conditions, which leads to a
semi-constrained boundary MG problem in which only geometrical conformity is required or
simply an open boundary without any constraints. Various methods (Viceconti et al. 1998) will
be presented in this chapter and in Chapter 8 targeted for these two situations with appropriate
measures to address the specific needs for these two problem types.
5.2 DELAUNAY TRIANGULATION (3D)
5.2.1 Introduction
The fundamentals of the DT have been discussed in Section 3.5. As the DT of 3D points is
one of the most useful techniques in the triangulation of general 3D domains subject to vari-
ous boundary requirements, the generation of tetrahedral elements by DT has been proved
to be one of the fastest and reliable means in producing FE meshes of different characteris-
tics. Since the insertion algorithm is known to be robust, efficient and versatile, a detailed
implementation of the insertion algorithm of 3D points will be described in Section 5.2.2.
Most of the steps are just simple extensions from the 2D situation, except in the determi-
nation of the adjacency relationship of the new tetrahedra formed inside the CORE with
respect to those outside the CORE. A rotation scheme has to be employed to establish the
adjacency relationship of the tetrahedral elements without much searching and matching.
For clarity and easy reference, some of the concepts presented in Chapter 2 are repeated here
in the context for 3D applications.
5.2.2 The insertion algorithm
For the construction of DT in three or higher dimensions, point insertion algorithm is the most
popular, and many interesting methods have been proposed (Bern et al. 1994; Borouchaki
and Lo 1995; Borouchaki and George 1996; Cortis and Friesner 1997; Boissonnat et al.
1998; Attali and Boissonnat 2004; Lo and Wang 2005d; Devillers and Teillaud 2011). For
a set of 3D points, the initial triangulation is a cuboid consisting of five or six Delaunay
tetrahedra large enough to contain all the given points, as shown in Figure 5.1. The DT is
achieved by inserting points one by one into the initial triangulation. Each cycle of point
insertion can be divided into three steps.
i. For a newly inserted point, identify all the tetrahedra whose circumsphere contains the
point in its interior. The cavity left behind upon removal of these tetrahedra forms a
star-shaped insertion polyhedron (CORE).
Points to
be inserted
Figure 5.1
Initial triangulation of five tetrahedra.
