## 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