Civil Engineering Reference
In-Depth Information
ii. Owing to the finite precision arithmetic, the triangulation facets on the boundary of
the cavity have to be verified with the visibility check and corrected before they are
connected to the inserted point to form tetrahedra.
iii. The triangulation of the insertion polyhedron should be trivial. However, the adja-
cency relationship of the tetrahedra has to be established, which will be frequently
referred to throughout the triangulation process.
5.2.2.1 Determination of the CORE
When a new point P is inserted in a DT, we have to find the insertion CORE or the poly-
hedron of all the tetrahedra whose circumsphere contains the point P. A simple method to
determine these non-Delaunay tetrahedra is to scan through all the existing tetrahedra in
the triangulation for those whose circumsphere contains the point P. However, a more effi-
cient approach is to start with the tetrahedron that contains the inserted point P and find
the others by means of the adjacency relationship. By the lemma of Delaunay, the boundary
of the CORE is given by the common faces of a pair of tetrahedra for which one is positive
and the other is negative to the sphere inclusion test.
The tetrahedron that contains the insertion point P is referred to as the BASE, which is an
integral part of the CORE. It seems that finding a tetrahedron whose circumsphere contains
P is easier than finding the BASE. Nevertheless, it does not always work in case a wrong
decision is made in the sphere inclusion test due to numerical errors. The difficulty has been
explained in terms of a 2D example, as discussed in Section 3.5.4.
5.2.2.2 Search for the BASE
In principle, we would like to start searching for the BASE from a tetrahedron as close to
the newly inserted point P as possible. When there is no better clue as to where the point P is
with respect to the existing tetrahedra in the triangulation, we can only arbitrarily start the
search from the last constructed tetrahedron. This is the general situation of Delaunay point
insertion that point P is independent of the current triangulation; however, in case insertion
(interior) points are created in relation to the tetrahedra in the triangulation as in some local
refinement scheme, there is no need to search for the BASE.
5.2.2.2.1 Steps in locating the BASE
1. Start the search from the last tetrahedron constructed, T.
2. Compute the volume co-ordinates of point P relative to tetrahedron T = T(P
1
P
2
P
3
P
4
).
The volume co-ordinates of P with respect to tetrahedron T are given by
VPPPP
V
(
)
,
VPPP P
V
(
)
,
L
=
234
L
=
134
1
2
V
(
PPPP
V
)
,
=
VPPPP
V
(
)
,
12
4
13
2
L
=
L
3
4
where V = V(P
1
P
2
P
3
P
4
) is the volume of tetrahedron T, as shown in Figure 5.2.
3. If L
1
, L
2
, L
3
and L
4
are all positive or zero, then tetrahedron T contains point P; other-
wise, determine how to update tetrahedron T moving towards point P. Check how
many volume co-ordinates are negative.
