🚀 go-pugleaf

> I recently had a conversation with a very mathematically oriented freind in 
> California, in which he mentioned that it would be possible to evaluate a 
> Bezier spline with *NO* multiplies using a "diffrence table"

Howdy, Woody.

There are a number of ways to do splines without multiplies or floating
point.  The simplest is the recursive subdivision trick that's most
commonly used; sample code is appended.  Forward differencing also
works (and is mathematically equivalent for certain interval sizes,
but without the call overhead of the recursive subdivision.)

Standard graphics texts illustrate these procedures; I believe Foley
and van Dam (I'm sure I've butchered the name; I'll look it up when I
get in to school tomorrow.)

The advantage of the recursive subdivision method is you can compute
and check the flatness of the curve at any point.  Note that the
shifts in the following code can be eliminated (actually done up
front), since the splines are always drawn at the same depth, but
since X is so slow anyway, the performance difference is negligible.
(Why doesn't X have a spline primitive?)

It is also possible to use general conics as the decomposition primitive
rather than lines; there are Siggraph papers on this . . .

XPoint splinepoints[2000], *spp ;
void rdrawspline(x1, y1, x2, y2, x3, y3, x4, y4, l)
long x1, y1, x2, y2, x3, y3, x4, y4 ;
int l ;
{
   long x12, x23, x34, x123, x234, x1234 ;
   long y12, y23, y34, y123, y234, y1234 ;

   if (l < 5) {
      x12 = (x1 + x2) >> 1 ;
      x23 = (x2 + x3) >> 1 ;
      x34 = (x3 + x4) >> 1 ;
      x123 = (x12 + x23) >> 1 ;
      x234 = (x23 + x34) >> 1 ;
      x1234 = (x123 + x234) >> 1 ;
      y12 = (y1 + y2) >> 1 ;
      y23 = (y2 + y3) >> 1 ;
      y34 = (y3 + y4) >> 1 ;
      y123 = (y12 + y23) >> 1 ;
      y234 = (y23 + y34) >> 1 ;
      y1234 = (y123 + y234) >> 1 ;
      rdrawspline(x1, y1, x12, y12, x123, y123, x1234, y1234, l+1) ;
      rdrawspline(x1234, y1234, x234, y234, x34, y34, x4, y4, l+1) ;
   } else {
      spp->x = x4 >> 8 ;
      spp->y = y4 >> 8 ;
      spp++ ;
   }
}
void drawspline(x1, y1, x2, y2, x3, y3, x4, y4) /* crude hack for now */
long x1, y1, x2, y2, x3, y3, x4, y4 ;
{
   spp = splinepoints ;
   spp->x = x1 ;
   spp->y = y1 ;
   spp++ ;
   rdrawspline(x1<<8, y1<<8, x2<<8, y2<<8, x3<<8, y3<<8, x4<<8, y4<<8, 0) ;
   XDrawLines(display, windowId, gc, splinepoints, spp-splinepoints,
                                                          CoordModeOrigin) ;
   Move(x4, y4) ;
}