
An efficient data structure for point bucketing is crucial to quickly
locate the fourth vertex among all mesh points which completes a triangle
from the queue to form a Delaunay tetrahedron.
The currently processed triangle which was taken from the queue is called a
base triangle. The advancing front holds Delaunay triangles, hence
any base triangle satisfies the Delaunay criterion.
A local region around the base triangle needs to be searched for to find
the correct fourth point. The border of this region is defined by a sphere
containing the circumcircle of the base triangle. The radius of the
sphere will be increased as long as the sphere does not contain other
points. A sketch for the twodimensional case is depicted in
Fig. 6.18 where an edge corresponds to the base triangle.
It is evident that one sphere must exist which does not hold any other
points due to the Delaunay property of the base triangle. In fact, the way
the region around the base triangle is examined resembles closely the
Delaunay sphere criterion. The size of the sphere is increased so that
exactly one other point (than the three points of the base triangle) is
located on the perimeter of the sphere. This point is the seeked fourth
vertex of the tetrahedron. It is evident that the tetrahedron must satisfy
the Delaunay criterion, because its circumsphere does not contain any other
point. For one base triangle two spheres exist that correspond to a
tetrahedron on each side. The algorithm will only attach a tetrahedron to
the front side of the base triangle as previously explained. It will
therefore increase the size of the sphere into the direction of the normal
vector of the base triangle. This is expressed by a signed increase of
the normal distance between the center of the sphere
and the base triangle. The normal distance can be positive or negative.
The point denotes the circumcenter of the base triangle and
its unit length normal vector. The smallest sphere is characterized by
. A negative denotes a sphere which covers a larger
area on the back side than on the front side of the triangle.
The spherical search region fits into a cubic search region which can always be aligned with the bounding box (Fig. 6.18). This allows for an efficient nonuniform point bucketing scheme to locate points within the search region. All points are stored and maintained at all times in a point bucket octree [142]. Any rectangular area aligned with the bounding box can be searched by traversing the tree data structure.
The gradual increase of the size of the search region does not cost much performance. If the sphere is too small no points will be located inside the search region and the effort of traversing the octree is minimal. The case when exactly one point (the fourth vertex of the tetrahedron) is found, is ideal. Usually, the search region will contain several points. In such a case the size of the sphere defining the search region will not be reduced until only a single point is contained. Instead is computed from which is the center of the sphere defined by the point and the base triangle (Fig. 6.19). is the location vector of one of the three vertices of the base triangle.
From the collection of points the correct fourth point can be chosen by minimizing .

A more flexible algorithm allows boundaries which do not form a closed surface. This generalization is implemented as follows. If no fourth vertex can be found after gradually increasing the search region up to the size of the bounding box, the base triangle will be converted and stored as a boundary triangle. In this way new boundary triangles can be generated during the tetrahedralization process at locally convex regions of the mesh point distribution. Figure 6.21 shows an example of an open surface description and a snapshot of the meshing process. Figure 6.22 depicts the complete boundary including the generated boundary triangles after tetrahedralization.
The octree search and the criterion introduce the logarithm into the overall time complexity where is the number of tetrahedra. For randomized point distributions the number of tetrahedra grows approximately linear with the number of points (Fig. 6.23). The algorithm runs in optimal time. The performance is given in Tab. 6.1.