rokicki@Neon.Stanford.EDU (Tomas G. Rokicki) (01/24/90)
> 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) ; }
woody@rpp386.cactus.org (Woodrow Baker) (01/24/90)
In article <1990Jan24.035540.1182@Neon.Stanford.EDU>, rokicki@Neon.Stanford.EDU (Tomas G. Rokicki) writes: > 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 [ code deleted for brevity] Thanks! I really appreciate this. Cheers Woody