Generating a Bezier Curve by the de Casteljau Algorithm

​
order of the Bezier curve
4
the index u, 0 ≤ u ≤ 1
0.45
This Demonstration shows how to generate a Bezier curve by the de Casteljau algorithm. An
th
n
-degree Bezier curve is defined by
C(u)=
n
∑
i=0
B
i,n
(u)
P
i
, where
B
i,n
(u)=
n!
i!(n-i)!
n-i
i
u
(1-u)
, with
0≤u≤1
.
Consider
n
linked segments. For each, use a percentage index
u
to indicate a point at that percentage of the segment's length. Use these points to make
n-1
segments, and repeat using the same index. More formally, define a basis function:
B
i,n
(u)=
n!
i!(n-i)!
n-i
i
u
(1-u)
​​=
(n-1)!n
i!(n-i)!
n-i
i
u
(1-u)
​​=
(n-1)!
i!(n-i)!
[(n-i)+i]
n-i
i
u
(1-u)
​​=
(n-1)!
i!(n-i)!
(n-i)
n-i
i
u
(1-u)
+
(n-1)!
i!(n-i)!
i
n-i
i
u
(1-u)
​​=
(n-1)!
i!(n-i-1)!
n-i
i
u
(1-u)
+
(n-1)!
(i-1)!(n-i)!
n-i
i
u
(1-u)
​​=(1-u)
(n-1)!
i!(n-i-1)!
n-1-i
i
u
(1-u)
+u
(n-1)!
(i-1)![(n-1)-(i-1)]!
(n-1)-(i-1)]
i-1
u
(1-u)
​​=(1-u)
B
i,n-1
(u)+u
B
i-1,n-1
(u).
Denoting a general
th
n
-degree Bezier curve by
C
n
(
P
0
,
P
1
,⋯,
P
n
)
, we have
C
n
(
P
0
,⋯,
P
n
)=(1-u)
C
n-1
(
P
0
,⋯,
P
n-1
)+
uC
n-1
(
P
1
,⋯,
P
n
)
.
This follows from the recursive definition of the basis function.
Fixing
u=
u
0
and denoting
P
i
by
P
0,i
, this yields a recursive algorithm for computing the point
C(
u
0
)=
P
n,0
(
u
0
)
on an
th
n
-degree Bezier curve, that is,
P
k,i
(
u
0
)=(1-
u
0
)
P
k-1,i
(
u
0
)+
u
0
P
k-1,i+1
(
u
0
)
for
k=1,…,n
,
i=0,…,n-k
.
This is called the de Casteljau algorithm.

References

[1] L. Piegl and W. Tiller, The NURBS Book, 2nd ed., Berlin: Springer-Verlag, 1997 pp. 9–10, 23–24.

Permanent Citation

Shutao Tang
​
​"Generating a Bezier Curve by the de Casteljau Algorithm"​
​http://demonstrations.wolfram.com/GeneratingABezierCurveByTheDeCasteljauAlgorithm/​
​Wolfram Demonstrations Project​
​Published: November 7, 2014