6.4.3.2 Cocircular Point Sets

A cocircular point set (Def. 5.3) usually forms the intersection of two cospherical point sets as described in Section 5.4. Thereby, a facet is defined by the cocircular point set which forms the interface between the LSPBs of the two cospherical point sets. This facet does not possess a unique Delaunay Triangulation. The presence of such degenerate cases further complicates the tetrahedralization of the LSPB. When processing the second queue adjacent triangles must be taken into account to avoid facet connectivity inconsistencies (Fig. 6.28).

Figure 6.28: (a) One adjacent triangle to merge (b) Of two adjacent triangles only one can be merged correctly (c),(d) No adjacent triangles exist

The implementation generally aims to merge with adjacent triangles when choosing the fourth point for the construction of a tetrahedron. In theory such a degree of freedom exists due to the existence of several equal $\lambda _{i}$. In practice under finite precision arithmetics a small deviation $\varepsilon$ from the minimal $\lambda_{\min}$ (Crit. 6.2) must be tolerated to allow a consistent merge with an adjacent triangle. The adjacent triangles in Fig. 6.28-b can be distinguished by calculating and maximizing normal distances of points to triangles. For each fourth point candidate from $\tilde{P}_{c,i}$ the normal distance to adjacent triangles is computed. The candidate which has maximal positive distance to all other adjacent triangles wins.

These techniques ensure a consistent tessellation in most cases. However, without further enhancements to the algorithm a consistent facet connectivity cannot be achieved in all cases due to the existence of untetrahedralizable polyhedra or twisted prisms (Section 5.5). For the advancing front style Delaunay algorithm it is useful to distinguish a general untetrahedralizable polyhedron and an untetrahedralizable cavity formed by Delaunay triangles. The modified advancing front algorithm will not create or encounter a general non-Delaunay twisted prism cavity. This follows from the fact that the advancing front consists of Delaunay triangles only. Thus, such a case may only occur if the facets from the input form a Schönhardt polyhedron. It will be transformed or refined by the surface preprocessor, because the triangles do not fulfill the Delaunay criterion. The question remains how to deal with the Delaunay twisted prism case, of which it can be guaranteed that it is formed by cospherical vertices.

Lemma 6.3   If an untetrahedralizable pocket is formed by Delaunay triangles, its vertices must form a cospherical point set.

Proof 6.3   The Delaunay Triangulation of any point set as the dual of the Voronoi diagram must exist. Assuming a point set with a unique Delaunay Triangulation (no cospherical point set), a Delaunay triangle composed of any three points from the set must be contained in the tetrahedralization. Thus, it is not possible to form an untetrahedralizable pocket with a subset of the Delaunay triangles from the tetrahedralization.

Figure 6.29: A twisted prism with cospherical vertices and three cocircular point subsets. It can be converted into a convex polyhedron or into an untetrahedralizable polyhedron while keeping the vertices cospherical. Thus, in all cases all triangles satisfy the Delaunay criterion.

Figure 6.29 shows a twisted prism which is formed by a cospherical point set $P_{c,i}$. Hence, all its surface triangles are Delaunay triangles. No correct fourth point can be chosen for any of its surface triangles to perform a correct merge with the adjacent triangles. By rotation of the upper three vertices relative to the lower three vertices two variations of the prism can be constructed while the vertices remain cospherical (Fig. 6.29). Hence, all versions of the prism satisfy the Delaunay criterion and can occur during the formation of the advancing front. Without rotation three subsets of cocircular points are formed on each side of the prism. Recall the problem of facet connectivity which was the motivation for the examination of the twisted prism. While the first type in the figure, a convex polyhedron, poses no difficulties except that a bad sliver element will be created, the other two types seem a dramatic dead end for the advancing front Delaunay tetrahedralization engine. But in practice for very small rotation angles the three versions of the prism cannot even be distinguished numerically. This leads to the idea to find an algorithm which treats all cases in the same way as can be dealt with the harmless convex polyhedron type. Therefore one should observe the relationship between slivers and the twisted prism. As shown in Fig. 6.29 an additive or subtractive combination of slivers with one prism type always results in another type. A convex prism can be formed by attaching slivers to the sides of the untetrahedralizable prism. Hence, the mesh topology and facet connectivity can be kept consistent elegantly for all cases if one allows the creation of slivers with negative, zero, or positive volume (orientation). For such a robust algorithm it is indifferent whether the volume of an extremely flat sliver tetrahedron appears to be exactly zero, positive, or negative.

After the volume tetrahedralization an adaptation step which is responsible for geometrical quality and slivers must guarantee the removal of all zero and negative volume slivers. Various Delaunay sliver types were discussed in Section 5.7. The type of sliver which will be created here in the context of the twisted prism is one with vertices from a cospherical point set. Such a sliver can be removed by a local transformation without modifying the points. The Delaunay property is thereby maintained.

The implementation of the tetrahedralization had to be extended for such sliver elements of zero or negative volume. The tetrahedralization of the LSPB may produce negative sliver elements when it merges with adjacent triangles which are already attached to tetrahedra. If adjacent triangles are not yet attached to tetrahedra, e.g. boundary triangles, the creation of slivers is avoided. Instead the implementation of the tetrahedralization engine possesses the power to flip triangles on the fly.

An important advantage is that no intersection tests are required to check for such cases. The test if an identical triangle exists (Lemma 6.1) is extended for cocircular point sets. If at least one not yet merged triangle exists with vertices from a cocircular point set which has the opposite orientation of the base triangle, zero or negative sliver elements are required. This becomes clear if one considers that the tetrahedralization of the LSPB occurs in a single step. Hence the plane spanned by the cocircular point set as part of the cospherical point set is either entirely triangulated or possesses no triangles at all. Without going further into detail it can roughly be said that all triangles from the triangulation of the (coplanar) cocircular point set are identically oriented.

In practice, one realizes that zero or negative volume elements are hardly required and in most cases the tetrahedralization of the LSPB can be directly fitted to the adjacent triangle constraints.