Combined exact and numeric intersection methods
In the combined methods exact arithmetic is used for determining the topology of the intersection tracks, numeric algorithms are used for approximating the geometry of the intersection tracks.
The approach for the combined methods is to combine the rational parametric description of one surface p1(s,t) , with the algebraic representation of the other surface q2(x,y,z)=0. Thus the problem is converted to a problem of finding the topology of an algebraic curve f(s,t)=q2(p1(s,t))=0 in the parametrization of the first surface.
A limited number of critical points
The approach is based on finding critical point, points where either
For any value in the first parameter direction of f(s,t) there will be a limited numer of such critical points. There are also a finit number of rotations of f(s,t) that will have have more than one critical point. f(s,t) is rotated to ensure that for a given value there will be only one critical point.
Projection to first parameter direction
The problem is project to a polynomial in the first parameter varaible of f(s,t) by:
To ensure the approach to work the root computation has to use extended precision to ensure that we reproduce the number of roots predicted by the Sturm-Habicht sequences.
Reconstruction of topology of the algebraic curve
From the above information the topology of the algebraic curve in the domain of interest can be constructed.
The algorithms have been implemented using symbolic packages.