[metapost] Re: [help-3dldf] Intersections of NURBs
Laurence Finston
lfinsto1 at gwdg.de
Sat Jan 29 11:01:25 CET 2005
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
More information about the metapost
mailing list