Curve and Surface Intersection Problems


In many applications, we need to find the points (curves) where two curves (surfaces) intersect, for example in constructing a countour map to graphically represent a prescribed surface o hypersurface, in computing silhouettes, in performing Boolean operations on solid bodies, in constructing smooth blending curves and surfaces, in finding offset curves and surfaces, etc.

A good (surface) intersection algorithm should have the following properties: Although presently there is no single algorithm which is optimal with respect to all four of these characteristics, there are many available algorithms.

Tipically, a numerical algorithm is efficient, but is not fully robust and so may fail in certain cases. Furthermore, the accuracy a numerical method can deliver varies with the surface degree, with the local surface geometry at the intersection curve, and with the angle at which the local surface intersect. Algorithms based on exact arithmetic, on the other hand, are fully robust and accurate, but are normally slow. The difficulty of the intersection problem, and the type of algorithm which best suits it, depends also on the general form of the curves or surfaces we are dealing with (implicit, explicit, parametrized), along with their particular properties (special or free-form).

A CCI (Curve/Curve Intersection) or SSI (Surface/Surface Intersection) problem can be approached with a variety of different techniques, including numerical, analytic, geometric, and algebraic methods, and using various methods such subdivision, tracing, and discretization. While the classic algorithms of the first generation are mostly based on just one method, more recently the tendency is to combine two or more methods into a multi-step method or so called hybrid- algorithm. The idea is to preserve the advantages of each one, but to eliminate their disadvantages if possible.

In our research activity we dealed with the NURBS SSI problem; we experimented some known approaches in literature and finally, as our best result for NURBS, we proposed a modified version of the marching method given in Barnhill, Farin, Jordan, Piper "Surface/surface intersection" CAGD (1987), specialized and optimized for NURBS surfaces. The balance between robustness and efficiency, an open question in SSI algorithms, was the main contribution of that work. This proposal is the SSI algorithm used in the xcbool system to compose solid bodies in the xcmodel system. Follows some graphic representations of the output of our SSI algorithm.

Glass/Glass intersection
First Glass domain
Second Glass domain
Bottle/Bottle intersection
Bottle domains

In the following figures we consider the bottle/plane intersection computed by our SSI algorithm. They compare the intersection between the two well-parametrized surfaces (fig.1) with the intersection between the same surfaces, in which the bottle surface is badly parametrized; in fact it is built as a revolving surface with a badly parametrized circular trajectory curve (fig.2). In the second case our algorithm presents an increased computational cost due to the fact that the solution for the parametric domain shown in fig.2 is given by a less smooth curve than in the first case (see fig.1). In this situation the marching phase encounters problems in the spans of higher curvature making it impossible to find all the intersection points to the required tolerance.

Fig.1 Fig.2

This our experience where working with badly parametrized curves or surfaces can be disadvantageous was the motivation to deal with the problem of parametric NURBS curve (surface) reparametrization. This consists in changing the current parameter of a curve with another parameter using a reparametrization function. It should be noted that the shape of the curve remains unchanged during this process; only the way the curve is described is altered. Follows an example.

NURBS periodic curve of 3 degree with its control points.

drawing in dots relating to the initial parametrization.

drawing in dots relating to a reparametrization.

As well known, the mathematical nature of the intersection problem is very simple when one plane curve o surface is given implicitly while the other is given in parametric form. In view of this, if both curves or surfaces are given in parametric form that is the more useful rapresentation in CAGD, it is natural to try to convert one of them to implicit form. In the literature, this idea, which comes from algebraic geometry is called implicitization. Because of its algebraic complexity, implicitization for curves or surfaces via parametric elimination can usually be done only with the help of formula manipulation such as Mathematica. In addition, for high polynomial degree, the algebraic method leads to significant numerical problems.

For example to intersect curves of degree n we need the expansion of a determinant leading to an equation of degree n^2, whose zero are to be found. Thus the available software for finding zeros of polynomials has an essential influence on the robustness, accuracy and efficiency of the algorithm. Because of the associated numerical problems, at the moment of aour research, results using known algorithms for n>=5 have not yet been obtained.

Recently we have proposed a suitable realization of the fast fraction free algorithm proposed in Bini, Gemignani, "Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation", LAA (1998), for the triangulation of a Bezout matrix with integer entries. This algorithm has been applyed successfully to the rational Bezier CCI problem working with great accuracy and avoiding the need for symbolic computation.

As already noted, using double precision arithmetic, there is an upper limit to the degree of the curves to be intersected. So our proposal, for planar curves of degree >5, uses the GNU Multiple Precision arithmetic library, which provides optimized tools to perform floating point arithmetic with arbitrarily high precision.

CCI example; the two curves have respectively 5 and 8 degrees.

The next steps are to extend our approach for planar curve of any degree and to other intersection problems in CAGD, from ray/surface intersection, that is the main computational problem in a ray-tracing algorithm, to surfaces/surfaces intersection.

References