[metapost] Re: Intersections of NURBs

[Larry Siebenmann]

Hi Laurence F.,

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

If urged, I can agree to identify an ellipse with the planar
Jordan region it bounds, thus viewing an ellipse as a planar
surface. But I am still sorely confused.  What about
2-dimensensional surfaces in R^3? -- Spheres in R^3 rather than
circles; or ellipsoids in R^3 rather than ellipses;  etc. ???

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

There are difficulties in general with extending the convex hull 
property to NURBS.  Maybe they can be overcome.
They arise roughly because a projective transformation T of "the
plane" is not a well defined self-mapping if the plane but rather
of the projectively extended plane

       RP^2 = R^2 \cup {projective line at infinity}

Indeed T respects R^2 and the line at infinity presisely if T is
affine!

Here is a simplest example where a difficulty arises.  I stand
before an (infinite) blackboard and project bezier curves on the
blackboard from my eye onto the (infinite) floor.  Consider in
particular the bezier cubic bb with its controll trilateral
A--B--C--D on the blackboard thus:


               B o-------------o C
                /               \
     -  -  -  -/ -  -  -  -  -  -\ -  -  - H   horizon of floor
              /        x          \        projected to blackboard     
             /   x            x    \
            /                       \
           / x                     x \
          /                           \     (paper = blackboard)
         /x                           x\
        /                               \
       /                                 \
    A o                                   o D

Notice that here the bezier cubic curve does *not* protrude above
the horizon H cut out on the blackboard by the horizontal plane
through my eye, whereas the control polygon does so protrude. Now
let me project from my eye onto the infinite floor both the bezier
cubic and the the four control points.  Note that the 2 control
points B and C slightly above the horizon project to two points
B' and C' on the floor that lie far behind my back. Thus the
convex hull of A',B',C',D' does NOT contain the projection of the
bezier curve.  The two intersect just in the two points A' and
D'. In other words, the de Casteljau convex hull property fails
in general for projections as it is usually stated -- at least if
any bezier is, as I seem to recall a special case of NURBS.

It is true that something useful can be said.  The projection of the
*full* convex hull of Cvx(A,B,C,D) does clearly contain the
projection of the bezier cubic bb.  In the present example this
tells us that bb lies in the projection of the filled quadrangle A,
BB, CC, D where BB is the intersection of A--B with the horizon line
H on the blackboard and CC is defined similarly.  This is useful
information.  But there are several possible positions with respect
to the horizon line H that have to to be considered to make this
discussion usefully general -- positions with respect to H of the
control points and of the bezier curve. Thus I have been making
optimistic noises about making a single simple projection manageable
for Knuth's non-intersection machinery.  But there is worse news:- a
general projective transformation is not an elementary eyeball
projection as considered here, but rather a composition of several.

If someone has seen a well-develloped system of estimates for
NURBS suitable to replace the de Casteljau convex hull 
property, please speak up!

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

I was implicitly suggesting that objects be left in some
to-be-develloped affine 3DMP format and the 2D display tasks be
farmed out to some cross-platform 3D==>2D display application with a
role analogous to that of a DVI-viewer or of Distiller + Acrobat
Reader. The viewer application would only have to deal with simple
projections with center an eyeball in R^3. But it would indeed have
have to deal with "surface hiding" and hence a modicum of
intersection theory. 3 dimensional reality is more affine than
projective; thus it is useful to study dimension 3 by affine (and
even orthogonal) methods; that's the basic reason for my suggestion.

Cheers

Laurent S.