Page 23 - Geometric Modeling and Algebraic Geometry

1 The GAIA Project 17
NURBS surfaces approximating low degree algebraic surfaces are intersected. Such
approximating NURBS surfaces are frequently bi-cubic and are thus much more
challenging to intersect that the algebraic surfaces they approximate. Approximate
implicitization is used to find the approximate algebraic degree of the surfaces, and
consequently simplifies the intersection problem significantly.
The high-level reference documentation of the software has already been pro-
duced in doxygen and is available on the web. Other papers on numeric intersection
algorithms from the project are [5, 14, 54, 55, 56].

1.7.3 Algebraic methods

The problems encountered in CAGD are sometimes reminiscent of 19th century
problems. At that time, realizing the difficulties one had working in affine instead of
projective space, and over the real numbers instead of the complex numbers one soon
shifted the theoretical work towards projective geometry over the complex numbers.
In fact, it is still in this situation that the modern intersection theory from algebraic
geometry works best:

• Bisection through a Multidimensional Sturm Theorem. A variant of the clas-
sical Sturm sequence is presented for computing the number of real solutions of
a polynomial system of equations inside a prescribed box. The advantage of this
technique is based on the possibility of being used to derive bisection algorithms
towards the isolation of the searched real solutions.
• Algorithms for exact intersection. Algorithms using Sturm–Habicht based
methods have been implemented and are available at Axel - Algebraic Software
Components for gEometric modeLing.
Papers on exact intersection methods from the project are [15, 30].

1.7.4 Combined algebraic numeric methods

The approach for the combined methods is to combine the rational parametric de-
scription of one surface p 1 (s, t), with the algebraic representation of the other sur-
face q 2 (x, y, z)=0. Thus the problem is converted to a problem of finding the
topology of an algebraic curve q 2 (p 1 (s, t)) = 0 in the parameterization 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 or ∂f(s, t)/∂s =0. For any value in the
first parameter direction of f(s, t) there will be a limited number of such critical
points. There is also a finite number of rotations of f(s, t) that will 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 variable 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 .. The