Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!snorkelwacker!apple!kchen
From: kchen@Apple.COM (Kok Chen)
Newsgroups: comp.lang.postscript
Subject: Re: Evaluation of Splines
Message-ID: <38061@apple.Apple.COM>
Date: 24 Jan 90 03:29:05 GMT
References: <17739@rpp386.cactus.org>
Organization: Apple Computer Inc., Cupertino, CA
Lines: 37

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.