Page 22 - Geometric Modeling and Algebraic Geometry

16 T. Dokken
1.7 Intersection algorithms

In the GAIA II project phase the work on the reference method, see 1.7.1, continued
from the assessment phase was completed. Further a completely new recursive in-
tersection code has been developed addressing industrial CAD-type problems. Two
more research oriented intersection codes have been developed: A pure symbolic
code and a combined symbolic numeric code. See Table 1.1 for a short overview.

1.7.1 The reference method

The reference method is based on intersecting triangulations that approximate sur-
faces. This can be used for getting a fast impression of the possible existence of
intersection or self-intersections. However, as the approach is sampling based, there
is no guarantee that all intersections are found, the triangulations intersected can
easily produce an incorrect topology of the intersection in near singular and singular
cases, and even false intersection branches might be found. The development of the
reference method has been important to allow think3 to develop the new user inter-
faces, and experiment with these before the software from the combined recursive
and approximate implicit intersection code was available in its first versions.

1.7.2 Combined recursive and approximate implicitization intersection
method

The combined recursive and approximate implicitization intersection was an ex-
tremely ambitious implementation task, the challenges of the implementation and
approach is discussed in [20]. The ambition has been to address the very complex
singular and near singular intersections. The aim was also Open Source distribution.
Consequently a completely new intersection kernel had to be developed to ensure
that we do not have any copyright problems. A major challenge with respect to self-
intersections is the complexity of cusp curves intersecting self-intersection curves.
The traditional approaches for recursive subdivision based intersection algorithms
do not work properly in these cases. Thus when starting to test the code we entered
unknown territory. By the end of GAIA II we could demonstrate that the approach
works, but the stability of the toolkit was not at an industrial level. However, stabi-
lization work on the code has continued after the GAIA II project.
Recursive intersection codes traditionally use Sinha’s theorem that states that for
a closed intersection loop to exist in the intersection of two surfaces then the nor-
mal fields of the surfaces have to overlap inside the loop. Consequently if there is
no overlap of the normal fields of two surfaces they can not intersect in a closed
loop. However, in singular intersections normal fields will overlap. In near singular
intersections even deep levels of subdivision often do not separate the normal fields.
In the GAIA II program code we have used approximate implicitization for sepa-
rating the spatial extent of the surfaces, and for analyzing the possibilities of closed
intersection loops by combining an approximate implicitization of one surface with
the parametric representation of the other surface. This is a very efficient tool when