Hjem til forsiden

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 p1(s,t) and p2(u,v)  be bicubic parametric surface, and assume that we know the exact implicit representation q2(x,y,z)=0 of p2. Then the intersection of p1and p2 can be expressed as

                    q2(p1(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 principleQuality of intersection topologyCommentAddressed in GAIA
TriangulationNo guarantee Will both miss and give extra branchesReference method
Lattice evaluationNo guarantee Will miss intersection branchesNo
RecursiveExact Topolgy produced depend on tolerances suppliedCombined with approximate implicitization
ExactExactCoordinate of points in exact arithmeticsThe AXEL library
Combined exact &numericExactCoordinate of points in exact floating point arithmeticSturm Harbicht sequences for topology of algebraic curves

Share

Published July 5, 2005