Intersection algorithms in GAIA

One of the primary objectives of the GAIA II project has been to implement intersection algorithms for improving the quality and performance of CAD systems. In CAD there is no formal restriction of the degree rational parametric surfaces, however, the most used parametric surface is the bi-cubic rational parametric surfaces represented by NURBS – NonUniform Rational B-Splines.

The algebraic complexity of the intersection of two bi-cubic surfaces

A generic bicubic rational parametric surface has algebraic degree 18. Let p₁(s,t) and p₂(u,v) be bicubic parametric surface, and assume that we know the exact implicit representation q₂(x,y,z)=0 of p₂. Then the intersection of p₁and p₂ can be expressed as

q₂(p₁(s,t))=0.

This is algebraic curve in the parameterization of the surface of degrees (54,54), just to determine the correct topology of such a curve is a great challenge.

Classes of intersection algorithms

Intersction algorithm principle	Quality of intersection topology	Comment	Addressed in GAIA
Triangulation	No guarantee	Will both miss and give extra branches	Reference method
Lattice evaluation	No guarantee	Will miss intersection branches	No
Recursive	Exact	Topolgy produced depend on tolerances supplied	Combined with approximate implicitization
Exact	Exact	Coordinate of points in exact arithmetics	The AXEL library
Combined exact &numeric	Exact	Coordinate of points in exact floating point arithmetic	Sturm Harbicht sequences for topology of algebraic curves

Published June 7, 2005