[metapost] Intersections of NURBs

[Laurence Finston]

Hello,

I hope nobody considers this question off-topic on the MF
and MP lists.

I'm trying to implement surface hiding in GNU 3DLDF in such
a way that it will work when using MetaPost output
(currently the only form).  All of
the forms of surface hiding I'm familiar with use raster
data, which won't work in this case.  Therefore, I've
decided to try to do it by "decomposing" objects until
(ideally) none intersect, and none of their projections
intersect.  For non-arbitrary objects, such as circles,
ellipses, cuboids, etc., the problem is straightforward,
albeit non-trivial.  Shapes defined by arbitrary curves are
a bigger problem.

I've decided to use NURBs (non-uniform rational B-splines)
instead of the B{\'e}zier curves used in MF/MP because the
former are projectively invariant, i.e., the results of 1)
projecting all of the points on the curve and 2) projecting
the control points and generating a curve from the
projections, are equivalent.  B{\'e}zier curves only have
the property of affine invariance, i.e., they are only
invariant under affine transformations such as rotation,
scaling, shifting, and shearing, but not under the
perspective transformation.  NURBs are similar to
B{\'e}zier curves but more complicated.  In addition to
control points, they use two sequences of real values:
"knots" and "weights".

"Decomposing" requires finding the intersections of
a given pair of objects.  None of the texts on NURBs I own
or have referred to goes into this topic.  In fact, in my
experience, computer graphics books tend to ignore the
important and fascinating topic of intersections.
With respect to a similar, and possibly related problem,
Piegl and Tiller, in _The NURBs Book_,  mention that
determining whether a point lies on a curve is difficult
when using a parametric representation (as one does with
B{\'e}zier curves and NURBs), but do not elaborate.

I've taken a look at Knuth's method of finding
intersections, but it appears to depend on the limited
precision whole-number arithmetic he uses, and is thus not
applicable to my more conventional approach using `floats'
or `doubles'.

I'm not expecting this to be easy, but any hints would be
much appreciated.

Laurence Finston