Intersection Algorithms - Computer Graphics and Geometric Modeling - page 567

Figure 13.18. An approximation to the

osculating circle.

(1) has the same complexity but better accuracy than using the tangent vector
direction,
(2) is simpler than using parabolic approximations to the curve but not quite as
accurate, and
(3) is as reliable as continuation methods but is more general.

This still leaves open the question as to whether one has chosen small enough
steps so as to find all parts of the intersection curves. Therefore, the methods need an
add-on for loop detection such as is described in [SedM88], [SeCK89], [Hohm91], and
[MaLe98]. This also applies to finding the start points. Unfortunately, it is very hard
to set tolerances correctly.
The problem of terminating points was encountered in our discussion of the
Barnhill-Kersey algorithm where we had to make a special case out of finding those
points and dealing with them. Finally, the problem with singular points is that the
Newton-Raphson iteration method involves solving linear equations and the matrices
for these equations usually have very bad condition numbers at the singular points,
which means that one loses all accuracy. The iteration may not converge or may miss
parts of the intersection curves.
[KrPP90] describes a hybrid algorithm that is basically a marching algorithm but
uses algebraic methods to make sure that no part of the intersection is missed. It
applies to the intersection of an algebraic and a rational parametric surface. The key
point was being able to detect all the “significant” points on the intersection curve.
Those are the boundary points, turning points (where the normal vector to the curve
is parallel to the u- and v-axis), and singular points (where the first partials vanish).

13.5.3 Surface Homotopy Method

The problem of finding intersections of implicit surfaces can be thought of as a special
case of the more general problem of solving systems of polynomial equations. One
much-studied technique that is used is called the homotopy method . It has also been
called the homotopy continuation method or simply a continuation or embedding
method . The idea is to find the solutions to a related set of simpler equations first and
then to deform these equations and their solutions into the given ones. A simple
example, presented in [PraG86], considers the problem of finding the solutions to the
equations