Civil Engineering Reference
In-Depth Information
5.4.4 3D conforming DT
The idea of boundary protection can also be extended to three or higher dimensions, in which
nodes are inserted to the missing geometrical quantities until they appear in the DT of the
points. In 3D, objects are bounded by closed surfaces of triangular facets. Unlike the bound-
ary recovery of 2D domains, whose boundaries are composed of only line segments and points
can be inserted on the boundary edges without much issue of convergence, in 3D, the bound-
ary of the domain consists of edges and triangular faces (Rand and Walkington 2009).
Similar to the boundary recovery of 3D objects presented in Section 5.3, boundary edges
are first recovered, followed by the boundary triangular faces. If we follow the procedure
of boundary recovery in 2D by simply inserting nodes to the missing edges until they are
recovered in the DT, this process may fail by not converging as more new missing boundary
edges are created at the same time. As shown in Figure 5.52, nodes C and D are inserted in
order to recover edge AB; however, elongated boundary line segments are formed as a result,
which may not be present in the new DT with additional points C and D. It is very likely
that the process may not converge as more new missing boundary edges are formed than the
number of edges being recovered.
5.4.4.1 Recovery of boundary edges
In the recovery process, we have to control the number of missing edges being formed as
boundary edges are recovered. The bisection of the longest edges described in Section 8.4.2
ensures that relatively long edges are not generated in the division process. Moreover, the
bisection process will terminate in a finite step, and the minimum quality of the boundary
triangles is guaranteed. As shown in Figure 5.53, edge AB is divided only if it is the longest
edge shared by the triangles. In case AB is not the longest edge, other edges connected to the
triangles have to be divided first. As AB is not the longest edge of triangles ACB and ABH,
before AB is divided, points P and Q are introduced to divide edges BD and BG, which are
the longest edges shared, respectively, by triangles BCD and BDE and triangles BFG and
BGH, as shown in Figure 5.53a. As shown in Figure 5.53b, point R is inserted to divide BC,
Boundary triangles
B
D
Elongated lines
may not be present
in the Delaunay
triangulation
C
A
Figure 5.52
Edge recovery by inserting nodes on the missing edges.
F
G
Longest
edge shared
by triangles
F
G
Q
E
E
Q
B
B
P
P
D
ST
D
H
H
R
A
Longest edge
shared by triangles
A
C
(b)
(a)
C
Figure 5.53
Edge recovery by bisection of the longest edges: (a) AB is not the longest edge; (b) neighbouring
edges are first subdivided.
