woody@rpp386.cactus.org (Woodrow Baker) (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"
Can anyone shed some light on exactly what he is talking about, and point
me to some reasonably clear explaination of how to accomplish the
computation of the table? I currently have a very simple minded Bexier
drawing routine, written in 'C' that I'n not altogether happy with. I've
distilled it down to 3 multiplies, but would like to get rid of them.
code follows:
/*
compute the coefficents for the 3rd order
cubic parametric equations that make up a Bezier
cubic spline
*/
computcof()
{
xd=x[1]-x[2]; /* factor out common expressions for */
yd=y[1]-y[2]; /* more speed and effeciency */
xd1=3*x[0];
yd1=3*y[0];
coeff[ax]=3*xd+x[3]-x[0];
coeff[ay]=3*yd+y[3]-y[0];
coeff[bx]=-3*(x[1]+xd)+xd1;
coeff[by]=-3*(y[1]+yd)+yd1;
coeff[cx]=3*(x[1]-x[0]);
coeff[cy]=3*(y[1]-y[0]);
}
/*
sets up and draws the spline. f is a flag that
determines whether to erase or draw the spline
*/
dospline(x0,y0,x1,y1,x2,y2,x3,y3,f)
int x0,y0,x1,y1,x2,y2,x3,y3,f;
{
x[0]=x0;
y[0]=y0;
x[1]=x1;
y[1]=y1;
x[2]=x2;
y[2]=y2;
x[3]=x3;
y[3]=y3;
computcof();
drawspline(f);
}
/*
draws splines
*/
drawspline(f)
int f;
{
float t;
int x1,y1,p;
for (t=0;t<1;t=t+.01)
{
x1=(((coeff[ax]*t)+coeff[bx])*t+coeff[cx])*t+x[0];
y1=(((coeff[ay]*t)+coeff[by])*t+coeff[cy])*t+y[0];
if(f==0)
{
SETPIX(x1,y1,1,0); /* put dot down */
}
else
{
SETPIX(x1,y1,1,3); /* erase dot */
}
};
}
I'm sure that this can be speeded up dramatically, if the multiplies
in drawspline can be removed, and the entire thing can be integerized.
Any help would be appreciated:
Cheers
Woody
kchen@Apple.COM (Kok Chen) (01/24/90)
woody@rpp386.cactus.org (Woodrow Baker) writes: >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" >Can anyone shed some light on exactly what he is talking about, and point >me to some reasonably clear explaination of how to accomplish the >computation of the table? Take a look at "forward differencing" in most graphics books (remember the weird numbers at the bottom right hand corners of logarithm tables? Same principle. Look at Bell's book on difference equations for the gory details. I *think* it was Bell. Too many decades ago...) A simple introduction to it can be, for example, found on page 328 of Newman and Sproull's "Principles of Interactive Computer Graphics." Since the fourth derivative of a cubic Bezier vanishes, the forward difference approximation can yield the *precise* solution (modulo errors due to finite arithmetic) with 3 forward differences. While you are at it, take a look at the "recursive subdivision" method for Beziers too. It, too, requires no multiplications. Also, take a look at Knuth's volume D of his "Computers and Typesetting" book for a pretty good insight to what you can do with Bernstein polynomials. Any of the existing well-used methods should be perhaps an order of magnitude faster than the C code that was posted. So, what does this have to do with PostScript? Could it be Woody is trying to write a PostScript interpreter that runs faster than the slooowwww printers he has been complaining about? :-) :-) Regards, Kok Chen kchen@apple.COM, kk6dp Apple Computer, Inc.
larry@csccat.UUCP (Larry Spence) (01/24/90)
In article <17739@rpp386.cactus.org> woody@rpp386.cactus.org (Woodrow Baker) writes: >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" >Can anyone shed some light on exactly what he is talking about, and point >me to some reasonably clear explaination of how to accomplish the >computation of the table? > >... a bunch of C code ... > Forget the forward differencing. Try this: . . x0 y0 moveto x1 y1 x2 y2 x3 y3 curveto stroke . . This IS the PostScript newsgroup, Woody! Sorry, I couldn't resist. -- Larry Spence larry@csccat ...{texbell,texsun,attctc}!csccat!larry
woody@rpp386.cactus.org (Woodrow Baker) (01/24/90)
In article <38061@apple.Apple.COM>, kchen@Apple.COM (Kok Chen) writes: > > So, what does this have to do with PostScript? Could it be Woody > is trying to write a PostScript interpreter that runs faster than the > slooowwww printers he has been complaining about? :-) :-) > Where can I find a ref to the recursive subdivision. I noticed it in Crispin Goswells code, which I got off a local BBS. It is a PS interpreter written of Sun's, in 'C' from Rutherford Labs, in England. I didn't want to plagerize his code, and would like to find a ref to the algorythm. > > Regards, > > Kok Chen kchen@apple.COM, kk6dp > Apple Computer, Inc. Much thanks. No, I'm not working on a postscript interpreter. I am, however working on a spline drawing program similar to A&L, and Illustrator, that does not require MS windows, and is a much smaller subset of A&L and Illustratir I just need a simple draw spline, move spline in real time routine. The code posted is what I am currently using, and it is SLOW and very non-optimal. I will grab some of these references and look them over. As an additional question, who knows about the "consortium" of font vendors that are reported to be pushing for font control legislation? Apparently there was an article in info world, and I'd like a pointer to it.