Description
P1 (120 points). The purpose of this project is to design a Matlab program to plot a
cubic B´ezier spline curve given by a sequence of de Boor control points.
Recall that a cubic B´ezier spline F(t) (in R
2 or R
3
) is specified by a list of de Boor
control points (d0, d1, . . . , dN ), with N ≥ 7, and consists of N − 2 B´ezier cubic segments
C1, . . . , CN−2, such that if the control points of Ci are (b
i
0
, bi
1
, bi
2
, bi
3
), then they are determined
by the following equations:
For C1, we have
b
1
0 = d0
b
1
1 = d1
b
1
2 =
1
2
d1 +
1
2
d2
b
1
3 =
1
2
b
1
2 +
1
2
b
2
1 =
1
4
d1 +
7
12
d2 +
1
6
d3.
The curve segment C2 is given by
b
2
0 =
1
2
b
1
2 +
1
2
b
2
1 =
1
4
d1 +
7
12
d2 +
1
6
d3
b
2
1 =
2
3
d2 +
1
3
d3
b
2
2 =
1
3
d2 +
2
3
d3
b
2
3 =
1
2
b
2
2 +
1
2
b
3
1 =
1
6
d2 +
4
6
d3 +
1
6
d4.
1
For i = 3, . . . , N − 4, the curve segment Ci
is specified by the “one third two third rule:”
b
i
0 =
1
2
b
i−1
2 +
1
2
b
i
1 =
1
6
di−1 +
4
6
di +
1
6
di+1
b
i
1 =
2
3
di +
1
3
di+1
b
i
2 =
1
3
di +
2
3
di+1
b
i
3 =
1
2
b
i
2 +
1
2
b
i+1
1 =
1
6
di +
4
6
di+1 +
1
6
di+2.
This generic case is illustrated in Figure 1. di−1
di
di+1
di+2
bi−1
2
bi
1
bi
2
bi+1
1 bi
0
bi
3
Ci
Figure 1: Computing B´ezier control points from de Boor control points
The curve segment CN−3 is given by
b
N−3
0 =
1
2
b
N−4
2 +
1
2
b
N−3
1 =
1
6
dN−4 +
4
6
dN−3 +
1
6
dN−2
b
N−3
1 =
2
3
dN−3 +
1
3
dN−2
b
N−3
2 =
1
3
dN−3 +
2
3
dN−2
b
N−3
3 =
1
2
b
N−3
2 +
1
2
b
N−2
1 =
1
6
dN−3 +
7
12
dN−2 +
1
4
dN−1.
2
Finally, CN−2 is specified by
b
N−2
0 =
1
2
b
N−3
2 +
1
2
b
N−2
1 =
1
6
dN−3 +
7
12
dN−2 +
1
4
dN−1
b
N−2
1 =
1
2
dN−2 +
1
2
dN−1
b
N−2
2 = dN−1
b
N−2
3 = dN
Observe that
b
i+1
0 = b
i
3
, 1 ≤ i ≤ N − 3.
Using the above equation, the cases N = 5, 6 are easily adapted from the general case:
compute the control points for C1, C2, . . . , CN−4, CN−2, and CN−3. When N = 4, use the
formulae for C1 and CN−2 = C2 with
b
1
3 = b
2
0 =
1
4
b1 +
1
2
b2 +
1
4
b3.
(1) Implement a Matlab program to plot a cubic spline specified by a sequence of de Boor
control points (for N ≥ 5). Make use of a function that allows you to specify the control
points by clicking on the mouse (screen input).
(2) Referring back to the interpolation problem defined in the notes (and the slides), can
you explain why the linear system giving d1, . . . , dN−1 in terms of the data points x0, . . . , xN
and d0 and dN (N ≥ 4) is:
7
2
1
1 4 1 0
.
.
.
.
.
.
.
.
.
0 1 4 1
1
7
2
d1
d2
.
.
.
dN−2
dN−1
=
6×1 −
3
2
d0
6×2
.
.
.
6xN−2
6xN−1 −
3
2
dN
.
Beware that the N in the interpolation problem is not the same N as in (1)!
P2 (80 points). The purpose of this project is to implement the subdivision version of
the de Casteljau algorithm for approximating a B´ezier curve by a polygonal line.
Given a cubic B´ezier curve C specified by its control points (b0, b1, b2, b3), for any t, the
de Casteljau algorithm constructs points
b
1
0
, b1
1
, b1
2
b
2
0
, b2
1
b
3
0
,
3
using the equations
b
1
i = (1 − t)bi + tbi+1 i = 0, 1, 2
b
2
i = (1 − t)b
1
i + tb1
i+1 i = 0, 1
b
3
i = (1 − t)b
2
0 + tb2
1
i = 0.
This process is conveniently depicted as follows:
0 1 2 3
b0 = b
0
0
b
1
0
b1 = b
0
1
b
2
0,
b
1
1
b
3
0
b2 = b
0
2
b
2
1
b
1
2
b3 = b
0
3
Then, the point C(t) is given by
C(t) = b
3
0
.
The cubic curve is tangent to the line segment (b
2
0
, b2
1
) at b
3
0
; see Figure 2.
It turns out that the two sequences of points
ud = (b0, b1
0
, b2
0
, b3
0
)
and
ld = (b
3
0
, b2
1
, b1
2
, b3)
are also control points for the curve C; see Figure 2.
Thus, we can iterate the above method using the control points in ud and ld, to obtain
a sequence of four control polygons, and if we iterate this process n times, we obtain 2n
control polygons which linked together yield a polygonal line that approximates very closely
the segment of B´ezier curve C(t) for t ∈ [0, 1]. Usually, we perform subdivision for t = 1/2.
This method is called the subdivision version of the de Casteljau algorithm.
(1) Implement the subdivision version of the de Casteljau algorithm in Matlab, for a
cubic specified by its control points (b0, b1, b2, b3). Your program should take as input the
control polygon (b0, b1, b2, b3) and the number of times n that your program subdivides.
Try various control polygons, and for each one, show of the result of subdividing at least
(six times n = 1, 2, . . . , 6).
Make use of a function that allows you to specify the control points by clicking on the
mouse (screen input).
4
b0
b1
b2
b3
b1
0
b1
1
b1
2
b2
0 b2
1 b3
0
Figure 2: de Casteljau subdivision
(2) Given a B´ezier curve C of degree m specified by its control points (b0, b1, . . . , bm), for
any t, the de Casteljau algorithm constructs points b
k
i
in m stages
b
1
0
, b1
1
, . . . , b1
m−2
, b1
m−1
b
2
0
, b2
1
, . . . , b2
m−2
.
.
.
b
m−1
0
, bm−1
1
b
m
0
.
If we write b
0
i = bi
for i = 0, . . . , m, then the b
k
i
are given by the following equations:
b
k+1
i = (1 − t)b
k
i + tbk
i+1 k = 0, . . . , m − 1, i = 0, . . . , m − k − 1,
and as in the case m = 3, the point on the curve is
C(t) = b
m
0
.
As in the case of cubic curves, the two sequences of points
ud = (b0, b1
0
, . . . , bm−1
0
, bm
0
)
and
ld = (b
m
0
, bm−1
1
, . . . , b1
m−1
, bm)
5
are also control points for the curve C, so we can iterate the above method using the control
points in ud and ld, and we obtain a subdivision method that yields a polygonal line that
approximates very closely the segment of B´ezier curve for t ∈ [0, 1].
Implement the subdivision version of the de Casteljau algorithm in Matlab, for a B´ezier
cutrve of degree m specified by its control points (b0, b1, . . . , bm). Your program should take
as input the control polygon (b0, b1, . . . , bm), and the number of times n that your program
subdivides.
Try various control polygons, and for each one, show of the result of subdividing at least
six times (n = 1, 2, . . . , 6).
Make use of a function that allows you to specify the control points by clicking on the
mouse (screen input).
TOTAL: 200 points.
6
