[metapost] Re: [help-3dldf] Intersections of NURBs

[Laurence Finston]

On Fri, 28 Jan 2005, L. Nobre G. wrote:

> On Fri, 28 Jan 2005, Laurence Finston wrote:
>
> > I hope nobody considers this question off-topic on the MF
> > and MP lists.
>
> I don't but I leave to you the posting of this reply on the MF and MP
> lists.

I'll risk it.  If the consensus is that it doesn't belong, I'll stop
posting to them.

>
> > Shapes defined by arbitrary curves are
> > a bigger problem.
>
> Do you mean "arbitrary surfaces"?
> If the awswer is "no", stop reading.

Yes, surfaces and solids, too.  However, I will also allow objects such as
curves and polylines.  I haven't decided yet how to handle `pens', i.e.,
whether the dimensions of the `pen' are added to those of the objects.
Currently, `pens' can be transformed in three dimensions, but the
transformations are converted to two-dimensional ones upon output.  `pens'
thus only "exist" in the x-y plane of projection.  I would like to
implement 3D pens, i.e., `pen_sphere' and `pen_cuboid' (which will be
transformable), but it will be awhile before I'm able to work on this.

>
> > "Decomposing" requires finding the intersections of
> > a given pair of objects.
>
> Supposing one has found one point where two arbitrary parametric surfaces
> of degree greater then 2 intersect I'd go for a "continuation method" to
> run over the intersection curve. It is somewhat similar to
> numerically solving a differential equation (or finding a contour line).

Thanks for the hint.

>
> > 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'.
>
> One can cast floats and doubles into limited precision...

They already are.  It's the whole number part that makes it difficult to
adapt Knuth's algorithms.  At a later date, I'd like to use a library for
higher-precision arithmetic, as Nelson Beebe suggested.  I've also been
considering using the GNU Scientific Library, but I haven't had a chance
to work on this yet.

>
> > I'm not expecting this to be easy, but any hints would be
> > much appreciated.
>
> I don't know NURBS but, maybe, there is a standard way to
> calculate the polyhedric control surface of surface-NURBS.
> If this polyhedric control surface exists, calculating the intersection of
> two arbitrary surfaces reduces to finding the piece-wise linear
> intersection of two polyhedric surfaces and then `converting' this
> polyline to a line-NURBS. Maybe, this convertion is possible and maybe, it
> produces the correct intersection. Well, maybe, maybe...
>

Thanks again.  I'm currently reading up on NURBs curves.  I've read a
little bit about surfaces, but I'm taking it one step at a time.  I
think a reasonable first step would be to find the intersection
of two NURBs of power 3 with four control points and that have a single
intersection.

Laurence