Civil Engineering Reference
In-Depth Information
tetrahedra ABCD and CBAE are converted to three tetrahedra ABED, BCED and CAED.
As face ABC is also removed in the element swap process, the number of intersection with
PQ is reduced by one. Two of the three tetrahedra, namely, BCED and CAED, are not inter-
sected by PQ, and they can be removed from the
pipe
. Effectively, by a proper 2-3 element
swap, both the number of intersections and the number of tetrahedra in the
pipe
are reduced
by one. In principle, by means of a sequence of element 2-3 swaps on adjacent tetrahedra, a
pipe
with n intersections and n + 1 tetrahedra can be recovered in n swaps.
Let PQ be a missing boundary edge cutting through eight tetrahedra and seven faces, and
the
pipe
associated with edge PQ is shown in Figure 5.13; (1) CBAP on CBA; (2) ABCD on
CBA and BCD; (3) BCDE on BCD and BDE; (4) BEDF on BDE and EDF; (5) DEGF on EDF
and FEG; (6) FEGI on FEG and FGI; (7) FGHI on FGI and GHI; and (8) GHIQ on GHI.
Starting from the first two tetrahedra on the side of point P, CBAP and ABCD are converted
to tetrahedra CAPD, ABPD and BCPD, as shown in Figure 5.14a. Tetrahedra CAPD and
ABPD, which are not intersected by PQ, are deleted from the
pipe
, as shown in Figure 5.14b.
The number of tetrahedra and the number of intersections are reduced by one as face ABC
is also removed in the element swap process. More element swaps on adjacent tetrahedra are
done to remove the remaining six intersected faces BCD, BDE, DEF, FEG, FGI and GHI, as
shown in Figure 5.14c-h.
We would like to ask the following question: Can missing edges always be recovered by
merely element swaps? The answer is no. While element swap is an effective tool in recover-
ing many missing edges, there are cases that cannot be reduced by element swaps. Element
swap will lead to invalid elements of zero or negative volumes if the two adjacent tetrahedra
are not convex, as shown in Figure 5.15, such that diagonal DE does not intersect with com-
mon face ABC. George et al. (1991) proposed a scheme to remedy this situation. As shown
in Figure 5.16, ADCE is the adjacent tetrahedron of the non-convex assembly of tetrahedra
CBAP and ABCD, and I, J and K are, respectively, the intersection points on faces ABC,
ADC and ADE.
CPF is the extension of face CPB onto face ADC with CF cutting JD at R, so that any
point between J and R will be visible to P. Let's introduce a new point S between J and R to
divide tetrahedron ABCD into three tetrahedra ADBS, DCBS and CABS, and tetrahedron
ADCE into AEDS, DECS and CEAS, as shown in Figure 5.17. Intersection point I can now
be eliminated by performing 2-3 swap to elements CBAP and ABCS. The number of inter-
section points will be reduced if J and K are in the same sub-tetrahedron without cutting
any new faces created in the subdivision of tetrahedron ADCE by point S. In case intersec-
tion points J and K are in two sub-tetrahedra, PQ must cut one of the newly created faces to
generate an extra intersection point, say, L on face CSE, as shown in Figure 5.18.
Q
H
8
7
F
I
4
6
B
G
E
5
3
C
D
2
1
P
A
Figure 5.13
A missing edge cutting through eight tetrahedral elements.
