Under exact arithmetics degenerate cases result in a compound of points
with identical
. The fourth vertex cannot
anymore be determined by minimizing
(Crit. 6.2).
Given a set of points
with
the original algorithm
results in overlapping tetrahedra and crossed edges.
Several two-dimensional situations are depicted in Fig. 6.24.
Figure 6.25 shows an error prone situation with a three-dimensional
cospherical point set.
![]() |
![]() |
If one wants to avoid the costly implementation of adaptive precision
algorithms and floating point filters
[161,48,54,11], one cannot rely
on a solution for exactly cospherical points , but has to
detect and treat approximately cospherical points
with corresponding
from an
algorithmic point of view.
At first must be a robust detection of
which is a crucial
task and cannot be achieved by a simple epsilon region where
.
Inconsistencies due to points that lie close to the border of the epsilon
region would be inherent. Numerically they might appear at one time
inside of the epsilon region and at another time outside of it.
Therefore, an adaptive epsilon region has been implemented which involves a
sorting algorithm.
The solution is to treat the points
as an isolated
tetrahedralization sub-problem forming a single step in the overall
modified advancing front algorithm.
Thereby the tetrahedralization technique for the sub-problem
is performed by a local instance of the modified advancing front
algorithm with a specific alteration described in the following
paragraphs. A local instance of the algorithm means that a second queue is
built to hold the local advancing front of the tetrahedralization of the
sub-problem. An ortho-product point distribution consists of a large number
of cospherical point subsets which are regularly stacked.
The global advancing front for such an example is shown in
Fig. 6.27. One can clearly observe how each subset is treated in
a single step from a global point of view.
The local second queue can only provide the frame for the entire solution
to the problem of cospherical point sets.
Another specific alteration of the tetrahedralization algorithm is required.
The enhancement is at first explained for the ideal case of exact
cospherical points .
The local boundary of the point set is convex (Fig. 6.24-d, convex
LSPB).
The special tetrahedralization of this sphere is constructed in the
following way. Consider a tetrahedralization with a convex boundary.
A tetrahedron can be created by linking a point located anywhere outside
the tetrahedralization to any triangle of the boundary that has a positive
minimum distance to that point. Regardless which triangle of the
boundary (with positive minimum distance) is taken the created tetrahedron
cannot penetrate the existing tetrahedralization.
If this single point is not only linked to one triangle, but to all
triangles of the convex boundary that have positive minimum distance to the
point, the result is again a tetrahedralization with a convex boundary.
The tetrahedralization can be expanded point by point while keeping the
temporary boundary convex.
The gain from such a method can be immediately seen in Fig. 6.25.
If the boundary would have been kept convex during the generation of the in
the figure depicted tetrahedron, the error prone situation would have been
avoided. The creation of a new tetrahedron could not lead to penetrations.
If the points are located on the perimeter of a sphere, the order in which the points are added to the tetrahedralization will not matter. Any point will be outside of the tetrahedralization of the other points. Also, any tetrahedralization of such points will be a Delaunay Triangulation. Thus, the convex LSPB can be tetrahedralized in this way with a slightly altered advancing front algorithm.
Starting with a base triangle a fourth point from the set of cospherical points is chosen to generate a tetrahedron. The first tetrahedron of the sphere forms a temporary convex boundary to which the other points of the sphere are added one after another. The temporary boundary is kept convex by ``looking back'' from each fourth point of the last generated tetrahedron to link it to all triangles with a positive minimum distance and thereby creating several tetrahedra in one step.
Once the LSPB is completely tetrahedralized, the ``looking back''
algorithm becomes unnecessary and it is returned to the normal
tetrahedra growth process. Note that ``looking back'' and checking the
minimum distance to the triangles is only required for triangles which
belong to the tetrahedralization of the LSPB.
As expected the implementation uses a temporary second higher priority
queue for the advancing front within the sphere.
Once the set is encountered and processed no later penetrations
are possible.
The algorithm is generalized to tetrahedralize the points
which possess general locations not exactly on the perimeter of a sphere.
They do not necessarily form a convex Delaunay boundary.
The
criterion (Crit. 6.2) is applied for each
generated tetrahedron. The point location must take all points in the
search region into account (not only points from the subset
). If the criterion cannot be satisfied by a point of
the subset
with a small tolerance
, the
tetrahedron will not be created. The temporary boundary to which the points
are added thus can contain non-convex regions which will
be specially marked. If a point is being linked to all triangles with
positive minimum distance such marked triangles are excluded.