Quote:>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 |

|~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~|

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~