[metapost] Intersections of NURBs

Laurence Finston lfinsto1 at gwdg.de
Sat Jan 29 11:20:00 CET 2005

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

Thank you for your help.


More information about the metapost mailing list