Civil Engineering Reference
In-Depth Information
more points on the circumsphere of a tetrahedron). However, exact integer arithmetic is not
the panacea to all these problems, and the situation of exactly co-spherical points and natural
degeneracy of
sliver
in DT are still not resolved with robust geometric predicates (Goliaz and
Dutton 1997). Hardware and compilers may also prevent the algorithm from functioning prop-
erly, and even though a right decision is arrived at for the sphere inclusion test, the connection
is not unique; moreover, we do not have a systematic way in joining up any number of points
on the surface of a sphere to produce a consistent triangulation, and
sliver
elements of zero or
nearly zero volume will still be formed. Nevertheless, the visibility or the positive volume test
appears to be simple and reliable in meshing domains for a wide range of point distributions.
5.2.2.3.2 Correction of the CORE
Inconsistency of the sphere inclusion test is to be supplemented and corrected by the visibil-
ity check or the positive volume test. As shown in Figure 5.3, a triangular face ABC is visible
to point P if
a
·
n
> 0, where
a
is a vector joining a point of triangle ABC to point P, and
n
is
a vector normal to the triangle. The volume of tetrahedron ABCP is given by
V(ABCP) = AP · (AB × AC) =
a
·
n
Poorly shaped tetrahedra can also be avoided at the same time if we insist that their vol-
ume ought to be greater than a certain threshold value. The condition that every triangular
facet on the boundary of the CORE is visible to P guarantees that the CORE is a single
connected piece. The visibility check, although simple, is a necessary and sufficient test to
ensure that the CORE is a star-shaped polyhedron with respect to the insertion point P. In
fact, we can adopt other inclusion rules as to which tetrahedra are to be removed by the
insertion point P to obtain different triangulations. In the extreme case, upon the introduc-
tion of point P, only one tetrahedron is deleted: the tetrahedron that contains P or the BASE.
Four new tetrahedra are created in the cavity by joining P to the four faces of the deleted
tetrahedron. Of course, by this simple rule, we are far away from the DT. Though we can
obtain a fast and valid triangulation of the given set of points, the tetrahedra so generated
are flat and almost degenerated. In summary, the visibility test ensures the validity of the tri-
angulation, and using higher-precision computations in the sphere inclusion test guarantees
that the resulting triangulation is as close to the required DT as possible.
5.2.2.4 Triangulation of the CORE
As all boundary facets of the CORE are visible to point P, the triangulation of the CORE
can be easily constructed by connecting P to each triangular facet on the boundary. This
P
n
C
a
A
B
Figure 5.3
Visibility test.
