Curves in 3D - 3D Math Primer for Graphics and Game Development - page 673

It's helpful to write out all the b s in a triangular fashion, as shown in
Figure 13.12. Each intermediate point is the result of linearly interpolating
between two points on the row above.

b 0 b 1 b 2 b 3

ց ւ ց ւ ց ւ

b 0 b 1 b 2

ց ւ ց ւ

b 0 b 1

Figure 13.12
Hierarchical relationships in the
de Casteljau algorithm for a cubic curve

ց ւ

b 0

If we combine these recursive relationships with the basic linear inter-
polation formula, we obtain the de Casteljau recurrence relation.

De Casteljau Recurrence Relation

b i (t) = b i ,
b i (t) = (1 − t)[ b n−1 (t)] + t[ b n−1

i+1 (t)]. i

Listing 13.1 illustrates how the de Casteljau algorithm could be imple-
mented in C++ to evaluate a Bezier curve for a specific value of t. The
caller passes in the original control points in an array, which is also used as
a temporary working space as the operation is performed in place. Each it-
eration of the outer loop performs one round of interpolation, replacing the
points at one level with the points at the next higher numbered superscript.
This process is continued until there is one point remaining, the desired re-
sult p (t). This example is intended to illustrate how the algorithm works,
not how to do anything particularly fast or provide a clean interface.

V e c t o r 3 d e C a s t e l j a u (

i n t n , / / o r d e r o f t h e curve , t h e number o f p o i n t s

V e c t o r 3 p o i n t s [ ] , / / a r r a y o f p o i n t s . O v e r w r i t t e n , a s

/ / t h e a l g o r i t h m works i n p l a c e

f l o a t t / / p a r a m e t e r v a l u e we wish t o e v a l u a t e

) {

/ / P e r f o r m t h e c o n v e r s i o n i n p l a c e

w h i l e ( n > 1 ) {

−− n ;

/ / P e r f o r m t h e n e x t round o f i n t e r p o l a t i o n , r e d u c i n g t h e