[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
meant.
Thank you for your help.
Laurence
More information about the metapost
mailing list