From: douglas@cs.scarolina.edu (David Douglas)
Subject: Re: Quadratic Bezier curve
Organization: USC  Department of Computer Science
Date:  6 Sep 92 21:17:45 GMT

Meessen@slig.ucl.ac.be  (Christophe Meessen) writes:

>Does anyone know of an incremental algorithm using to draw quadratic Bezier
>curves ? It could exist because Apple use quadratic Bezier to define their
>True Type outlined fonts.

>Idem for Cubic Bezier curve. As far as I know there isn't any but I want to
>be shure of that too.

>I'm speaking of incremental algorithm, not the Bezier curve dividing
>algorithm
>called the 'Casteljalou' algorithm ( sorry if misspelled ).
>Could someone give me the reference of the article where he describe the
>method.

>Thanks.

>Bien cordialement,

>                           Christophe MEESSEN


I assume that you're referring (then again, maybe not, but this is what
I'm familiar with :-) to a Bezier curve generated by blending a list
of points together, where any point on this curve may be given by

            _____
           |     |
            \
B   (u)  =   >      p  B   (u)
 i,n        /        i  i,n
           |_____|

where

0 <= u <= 1

and
                   i        n - i
B    (u) = C(n,i) u  (1 - u)
  i,n

and

              n!
C(n,i) = -------------
          i! (n - i)!


and  n  is the point count  minus 1.

(as taken from the book  Geometric Modeling  , by Michael E. Mortenson,
 ISBN 0-471-88279-8)


When you apply the above formula, you get a set of polynomials, one
polynomial for each point in the list of points to be blended.  One way
to generate points on the curve, without repeatedly evaluating the
appropriate polynomial for each new value of  u  , is to use a method
known as forward differencing.  In other words, in forward differencing,
you assume that you are going to add a fixed value (increment) each time
you increase the value of  u  .  So, let's say that X represents that
increment, and F(p) represents the result of forward-differencing a
polynomial  p  -- i.e.,

F(p) = p(u + X) - p(u)

where  u  is the polynomial  p's main variable.  The new polynomial that
results from forward-differencing the given polynomial will have a degree
(highest-order exponent) which is 1 less than the degree of the given
polynomial.  So, eventually, when you repeatedly forward-difference
a polynomial, you get a polynomial which is a constant -- the polynomial's
main variable has been eliminated.

(Please note that the above forward-differencing requires one to "symbolically"
manipulate the polynomial, not just apply the polynomial to the current
value of  u  plus the value of X.)

Now, let's say that the given polynomial is represented by g(u), and has
a degree of 3 -- for instance,

 3       2
u  +  2 u  +  3 u  +  4


Let h(u) represent the result of forward-differencing g(u), and

let i(u) represent the result of forward-differencing h(u), and

let j(u) represent the result of forward-differencing i(u).

Since g(u) is a degree 3 polynomial, that means that h(u) is degree 2, i(u) is
degree 1, and j(u) is degree 0 (i.e., a constant).

Next, let G = g(0), H = h(0), I = i(0), and J = j(0) -- in other words,
evaluate all the polynomials at the starting value of  u  that you want
to use.  G  is the starting value (polynomial result) that you want to use;
to get the rest, simply add the forward-difference result to your current
value -- add H to G, then add I to H, and finally add J to I.

Or, to put it another way:

Repeat N times (where forward-difference value is 1/N):
    G = G + H
    H = H + I
    I = I + J


This can be generalized to a polynomial of degree n -- each involved
polynomial's new value is simply its old value plus the CURRENT value of
the polynomial's forward-difference polynomial:

Repeat N times (where forward-difference value is 1/N, and p    is
                                                            i+1

                (initially) the result of evaluating polynomial p  's
                                                                 i

                 forward-difference polynomial):

    p  = p  +  p
     0    0     1

    p  = p  +  p
     1    1     2

    p  = p  +  p
     2    2     3

    . . . . . .

    p    = p    +  p
     n-1    n-1     n



where p   is the final (constant) polynomial resulting from repeatedly
       n

forward-differencing the polynomial p.  Note that the above additions
have to be done in the order specified -- otherwise, you might add in
a value which has already been updated for use in the NEXT loop iteration.


The nice thing about using this method is that you can pre-calculate
all the final starting coefficients (p  ,  p  ,  p  ,  ... p )  for each
                                      0     1     2         n

point's polynomial and perhaps simply store them in a "constant" array
in your program -- each time you want to draw points on a new curve, simply
make a copy of each polynomial's coefficients, and follow the above
addition-based method of updating the coefficients, instead of repeatedly
evaluating the polynomials for each new value of u.  For more efficiency,
first multiply each polynomial's starting coefficients by the corresponding
point's value, THEN use the above addition-based method to update the
coefficients.  (This also means that you'll need a working-copy for each
component of your point -- in your case, perhaps one each for X and for
Y -- for 3-D situations, another one also for Z.)



In case you're wondering, I'm using the above method myself for faster
generation and display of Bezier and B-Spline surfaces for point grids
of different sizes (basically the same as generating points on an individual
curve, except that now you have a curve for each row/column of points, and
you blend corresponding points on each curve to generate points on the
surface).  I ended up writing a polynomial-handling library (in C)
specifically designed to make building, evaluating, and forward-differencing
polynomials easier to do, then built the blending-function routines on top
of this library.


If you have any questions about my response or even about the source code
I've put together, just ask.  What I wrote above makes sense to me; how well
it makes sense (or even how useful it is) to you or to someone else, though,
could be quite a different matter -- so if you need anything clarified,
let me know.  Hope this helps!

Regards,


David

|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
|  David Douglas                              |
|  Graduate Computer Science program          |
|  University of South Carolina               |
|  Columbia, S.C.  29208                      |
|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|
|  E-mail:  douglas@usceast.cs.scarolina.edu  |
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~