Next: 6.4.3 Degenerate Point Sets Up: 6.4 Volume Tetrahedralization Previous: 6.4.1 Algorithm Overview

6.4.2 Point Location

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 two-dimensional 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 non-uniform 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 .

Criterion 6.2 (Minimum )   Let with corresponding be a complete set of all points which are located in a spherical search region in defined by a Delaunay triangle and a value . The point and the Delaunay triangle form a Delaunay tetrahedron, if and only if .

The scope of the possible values is numerically a delicate matter. The robust implementation applies an additional insphere test. Figure 6.20 shows the two-dimensional analogy. The normal distance of a point to the plane containing the base triangle (in two dimensions an edge) is . The point has and the point has a positive . The algorithm has to determine which of the two points and is the correct point. The correct triangle in the two-dimensional case is drawn with dashed lines. The various possible locations of a point are denoted with the corresponding values. The location of points with is shown by the dashed circle. The point is on a numerical critical location:

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.

Table 6.1: Runtime on an HP 9000-735/100Mhz
 quantity of ... CPU time points tetrahedra triangles (in sec) 103 535 1098 0.2 503 3016 6112 1.4 703 4323 8739 2.1 1003 6268 12635 3.3 1503 9494 19107 5.1 2003 12713 25557 6.8 2503 16076 32300 8.8 3003 19394 38967 11.1 4003 25969 52140 15.6 5003 32691 65605 19.7 10003 65927 132160 46.5 20003 132854 266133 92.0 30003 199613 399756 145.0 40003 266899 534405 207.0

Next: 6.4.3 Degenerate Point Sets Up: 6.4 Volume Tetrahedralization Previous: 6.4.1 Algorithm Overview
Peter Fleischmann
2000-01-20