Hjem til forsiden

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

  • ∇f(s,t)=0
  • ∂f(s,t)/∂(s)=0

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:

  • Computing the discriminant R(s ) of f(s,t) with respect to t, and finding the real root of  R(s), α1,...,αr. Sturm-Habicht sequences here supplies an exact number of real root in the interval of interest.
  • Then for each αi, i=1,...,we compute the real roots of f(αi,t), βi,j, j=1,...,si,.
  • For every αi and βi,j  compute the number of half brancehsto the right and left of the point (αi,βi,j).

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.



Published June 7, 2005