Civil Engineering Reference
In-Depth Information
the boundary surface. The following algorithm presents the main ideas of a constrained
boundary recovery procedure.
Algorithm: 3D-constrained DT
Step 1: Take the given polyhedron as input. Set the original triangular facets on the
boundary as constraints.
Step 2: Perform Delaunay insertion for points on the boundary of the polyhedron.
Step 3: Carry out local element swaps to recover boundary edges.
Step 4: Carry out local element swaps to recover boundary facets.
Step 5: Insert Steiner points to missing boundary edges/faces.
Step 6: Remove Steiner points on boundary edges.
Step 7: Remove Steiner points on boundary facets.
Step 8: Delete tetrahedra outside the model to obtain the final tetrahedral mesh.
5.3.3.2.1 Step 1: Restrained edges and faces
This step is trivial; the triangles on the boundary surface are properly recorded as restricted
boundary to be retrieved in the recovery process, and the boundary edges of a triangulated
surface can easily be extracted, as described in Section 2.5.8.
5.3.3.2.2 Step 2: Initial DT
An initial DT (the convex hull) of the boundary points is created by the 3D Delaunay inser-
tion kernel presented in Section 5.2.2.
5.3.3.2.3 Step 3: Recovering missing edges by element swaps
If any boundary edge is missing, it is not an edge of a tetrahedron in the DT, and such an
edge will intersect with at least one face in the triangulation. Usually, longer edges will cut
through more tetrahedra and are, in general, more difficult to recover. The missing line seg-
ment along with the associated intersected tetrahedra is called a
pipe
in the paper (George
et al. 1991), though the assembly looks more like a
brochette
. Our task is to recover edge
PQ by 2-3 element swaps, and the basic idea is to swap a pair of tetrahedra to three tetra-
hedra about the common face intersected by the missing edge so as to reduce intersections.
Consider adjacent tetrahedra ABCD and CBAE in a
pipe
intersected by the missing edge
PQ on three faces ABE, ABC and ABD, as shown in Figure 5.12. By a 2-3 element swap,
D
D
D
Q
Q
C
Q
C
Delete tetrahedra
BCED and CAED
from the
pipe
A
A
A
B
B
B
P
E
P
E
P
E
Figure 5.12
Swap tetrahedra ABCD + CBAE to ABED + BCED + CAED.
