[metapost] Intersections of NURBs

[Larry Siebenmann]

 > I'm trying to implement surface hiding in GNU 3DLDF
 > ...
 > Therefore, I've decided to try to do it by "decomposing" 
 > objects until (ideally) none intersect, and none of their 
 > projections intersect. 

Nonintersection is what Knuth-Hobby intersection algorithm 
is about.  It *rigorously* establishes non intersection.

 > Shapes defined by arbitrary curves are
 > a bigger problem.

Are you defining surfaces in terms of nets of curves?

 > 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.

Not if you use Knuth-Hobby binary search approach and 
b'eziers (of any degree).  That could make preferring NURBs to 
bezier an expensive luxury if replacements for the de 
Castaljau convex hull property are still lacking in the NURBs 
world. 

More reasonable might be to use only bezier objects in 3D
and project to 2D for display. Why would that be 
insufficient for 3DLDF?  

Incidentally how does/will 3DLDF get PS output?

 > 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'.

That may make Knuth's code useless.  But the concepts work in 
floating point too.

Laurent S.