[metapost] Intersections of NURBs

[Laurence Finston]

On Fri, 28 Jan 2005, Larry Siebenmann wrote:
>
> Nonintersection is what Knuth-Hobby intersection algorithm
> is about.  It *rigorously* establishes non intersection.
>

I'll have to look at it more carefully.  It's always a bit difficult
trying to understand Knuth's code out of context, and I've never found the
time to read _METAFONT:  The Program_ cover-to-cover.

>  > Shapes defined by arbitrary curves are
>  > a bigger problem.
>
> Are you defining surfaces in terms of nets of curves?
>

Not yet.  Currently, all of the internal data types
(C++ classes) that correspond to data types defined in the
3DLDF language that could be said to be surfaces, i.e.,
`Rectangle', `Reg_Polygon', `Ellipse', and `Circle',
are derived from `Path', with extra data members where
appropriate, e.g., `Points' for the center and the foci.

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

Please correct me if I'm wrong, but I think NURBs have the
convex hull property.  I believe that a NURB with all
weights equal to 1 and the knot sequence chosen
appropriately is equivalent to the B{\'e}zier curve with the
same control points.

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

Because in that case I'd have to project "all" the points on
the curve instead of just the control points.  This is, in
effect, how 3DLDF works now.

> Incidentally how does/will 3DLDF get PS output?

3DLDF writes moderately low-level MP code.  I say
"moderately", because it writes `draw', `fill', etc., rather
than `addto ... also'.  Currently, I don't see any reason to
write PS code directly.  I've never learned PostScript,
although I'm sure it would be useful to know it.  For the
kinds of things I can't do with MP, such as raster-based
processing, I plan to have 3DLDF write PNG (Portable Network
Graphics), either directly, or by using the GNU Plotutils.

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

I'll have to gird my loins and read through it.
I got the impression that upon each iteration, an additional
bit is set in a segment of memory, interpreted as a whole
number value.  But perhaps I just didn't understand what he
meant.

Thank you for your help.

Laurence