Unit 8: Numerical Methods

Chapter 40: Interpolation

Section 40.5: Bezier curves

Copyright

Copyright * 2001 by Addison Wesley Longman, Inc.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America.

Initializations

> restart;

> with(linalg):
with(plots):
with(plottools):
read(`C:/Program Files/Maple 6.01/pvac.txt`):

Warning, the protected names norm and trace have been redefined and unprotected

Warning, the name changecoords has been redefined

>

Definition 40.1

Given the points , and the corresponding vectors P = i + j , the associated th degree Bezier curve is given by

R P

where the coefficients in the square bracket are the binomial coefficients " choose ", and .

(Texts such as [1] accent the first e , while texts such as [2] don't. In either event, the author has always heard the name pronounced with three syllables, as Bez-ee-ay.)

>

Example 40.9

The cubic Bezier curve associated with the points has the general form

R = 1 P P P + 1 P

where the binomial coefficients evaluate to , respectively. In fact, using Maple, we have

> for k from 0 to 3 do
binomial(3,k);
od;

>

for the four binomial coefficients "3 choose ", where .

The four points

> p[0] := [0,0];
p[1] := [-1,2];
p[2] := [7,3];
p[3] := [5,0];

>

determine the cubic Bezier

> R := evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k],k=0..3));

>

Maple's evalm command accepts the lists and converts them to the vectors P .

Expanding the parentheses in R gives

> `R` = map(simplify,R);

>

which is graphed as the solid curve in Figure 40.10.

> for k from 0 to 3 do
d||k := disk(p[k],.1,color=black);
od:
pp1 := plot([R[1],R[2],u=0..1],color=green):
pp2 := plot([[p[0],p[1]],[p[2],p[3]]], color=red, linestyle=2):
pp3 := textplot({[.4,.3,`p0`],[-1,2.3,`p1`],[7.1,3.3,`p2`], [4.7,.3,`p3`]}):
display([d||(0..3),pp||(1..3)], scaling=constrained, labels=[x,y], labelfont=[TIMES,ITALIC,12], xtickmarks=9, ytickmarks=3);

>

The two intermediate points and are called control points , and influence the shape of the Bezier curve. To see the effect of these points on the shape of the curve, examine the following animation in which the two control points move horizontally along two parallel lines. Thus, the four points from which to construct the Bezier curve are

> p[0];
p[1] := [t,2];
p[2] := [6-t,3];
p[3];

>

The associated Bezier curve, now parametrized by , with , is then

> Rt := evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k],k=0..3));

>

and the desired animation is given by

> X := unapply(Rt[1],t):
Y := unapply(Rt[2],t):
F1 := t-> plot([X(t),Y(t), u = 0..1], color = green):
F2 := t-> plot({[[t,2],[0,0]],[[6-t,3],[5,0]]}, color = red):
F3 := z-> display([disk(subs(t=z,p[1]),.1,color=black), disk(subs(t=z,p[2]),.1,color=black)]):
F := t-> display([F1(t),F2(t),F3(t)]):
ff := display([seq(F(-1+k*8/50), k = 0..50), seq(F(-1+(50-k)*8/50),k=1..49)], insequence = true):
display([ff,d0,d3],scaling=constrained, xtickmarks=9, ytickmarks=3);

>

The red line segments connecting with , and with appear to be tangent to the Bezier curve at the endpoints of the curve. Indeed, a computation shows

R ' = 3 ( P P )

and

R ' ( P P )

Indeed, differentiating to obtain R ', we have

> `R'` := map(diff,R,u);

>

Evaluating R ' at the endpoints gives

> subs(u=0,op(`R'`));
subs(u=1,op(`R'`));

>

and the obvious vector arithmetic gives for 3 ( P P ) and 3 ( P P ) the vectors

> evalm(3*([-1,2]-p[0]));
evalm(3*(p[3]-[7,3]));

>

so that lines connecting the first and second points, and the third and fourth points, must necessarily be tangent to the Bezier curve. In effect, the curve appears to be a flexible rod with red "handles" attached at the ends. As the red "handles" are manipulated, the rod flexes and assumes the shape of the Bezier curve.

>

Constructing a Cubic Bezier Curve

The four points

> p[0] := [1,5];
p[1] := [4,7];
p[2] := [5,12];
p[3] := [9,4];

>

determine the cubic Bezier curve

> R := map(simplify,evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k],k=0..3)));

>

which, along with the four points, is graphed in Figure 40.11.

> for k from 0 to 3 do
d||k := disk(p[k],.1,color=black);
od:
f1 := display([d||(0..3),plot([R[1],R[2],u=0..1],color=black)], scaling=constrained, xtickmarks=9, ytickmarks=3, labels=[x,y], labelfont=[TIMES,ITALIC,12]):
pp:=textplot({[1.4,4.9,`p0`],[4.4,7,`p1`],[5.4,12,`p2`],[9.3,4.2,`p3`]}):display([f1,pp]);

>

To understand how the control points and influence the shape of the Bezier curve, draw line segments connecting consecutive pairs of points . Then using vector notation, and for , let Q describe the segment connecting with . Thus, we let

Q describe the segment connecting with

Q describe the segment connecting with

Q describe the segment connecting with

In addition, for each fixed value of in the interval , Q , is a single point on the respective line segment.

We can therefore connect

the points Q and Q with the line segment Q

and

the points Q and Q with the line segment Q

Finally, for each fixed value in the interval , Q and Q are points which can be connected with the line segment Q .

As varies from 0 to 1, the corresponding point on the line segment Q traces the Bezier cubic, shown in cyan, in Figure 40.12. The line segments Q and Q are shown in red, and the line segment Q is shown in blue.

> a1 := [11/5,29/5]:
a2 := [22/5,9]:
a3 := [33/5,44/5]:
a4 := [77/25,177/25]:
a5 := [132/25,223/25]:
a6 := [99/25,977/125]:
b1 := plot([[p[0],p[1]],[p[1],p[2]],[p[2],p[3]]], color = black, thickness=3):
b2 := plot([[a1,a2],[a2,a3]],color=red):
b3 := plot([a4,a5],color=blue):
b4 := disk(a6,.1,color=black):
b5 := textplot({[1,4.5,`p0`], [4,6.5,`p1`], [5,12.5,`p2`], [9,3.5,`p3`]}):
b6 := textplot({[2.2,5,`Q1`], [4,9,`Q2`], [7.1,8.8,`Q3`], [2.6,7.2,`Q4`], [5.3,9.1,`Q5`]}):
f1 := display([d||(0..3),plot([R[1],R[2],u=0..1],color=cyan)]):
f2:=display([b||(1..6),f1],view=[0..10,3..13], xtickmarks=5, ytickmarks=5, labels=[x,`y `], labelfont=[TIMES,ITALIC,12]):
f3 := arrow([2.4,9],[3.8,8],.07,.2,.3,color=black):
f4 := textplot([2.1,9.2,`Q6`]):
display([f||(1..4)]);

>

Analytic representations of the line segments Q = P ( P P ), , are

> Q[1] := evalm(p[0] + u*(p[1]-p[0]));
Q[2] := evalm(p[1] + u*(p[2]-p[1]));
Q[3] := evalm(p[2] + u*(p[3]-p[2]));

>

where, in each case, . Analytic representations of the line segments

Q = Q ( Q Q ),

are

> Q[4] := map(simplify,evalm(Q[1] + u*(Q[2]-Q[1])));
Q[5] := map(simplify,evalm(Q[2] + u*(Q[3]-Q[2])));

>

Finally, the analytic representation of the line segment Q = Q ( Q Q ) is

> Q[6] := map(simplify,evalm(Q[4] + u*(Q[5]-Q[4])));

>

For each fixed value of in the interval there is a single point on the line segment Q . That point is a point on the Bezier cubic, as we can see by comparing Q to the vector R

> print(R);

>

which gave the Bezier curve by its definition.

Consequently, we can now see how the Bezier curve might have been discovered. Idly drawing four points on a scrap of paper, a doodler could have connected with solid lines, the consecutive pairs of points, then connected with dashed lines, the midpoints of the black line segments, and connected, with dotted lines, the midpoints of the dashed lines. If, say, the quarter points were similarly connected, and the one-third points likewise connected, etc., it is not hard to believe that the inspired doodler would have seen that the Bezier curve is the envelop of all the dotted lines.

The following animation shows the succession of red and green line-segments which generate the cubic Bezier curve.

> F1 := t -> plot(subs(u=t,[convert(Q[1],list),convert(Q[2],list)]), color=red):
F2 := t -> plot(subs(u=t,[convert(Q[2],list),convert(Q[3],list)]), color=red):
F3 := t -> plot(subs(u=t,[convert(Q[4],list),convert(Q[5],list)]), color=red):
F4 := t -> disk(subs(u=t,convert(R,list)),.1, color=black):
F5 := t -> plot([R[1],R[2],u=0..t], color=green):
F6 := t -> display([F||(1..5)(t)]):
F7 := display([seq(F6(k/30),k=0..30)], insequence=true):
display([F7,b1,b5]);

>

The Cubic Bezier Spline

From Section 40.4, the natural cubic spline interpolating the points

> p[0] := [0,0];
p[3] := [4,7];
p[6] := [7,2];
p[9] := [10,5];

>

is

> Y := spline([0,4,7,10],[0,7,2,5],x,3);

>

with graph shown in Figure 40.13.

> plot(Y,x=0..10, color=black, labels=[x,y], labelfont=[TIMES,ITALIC,12], xtickmarks=6, ytickmarks=8, scaling=constrained);

>

Both from this graph, and from the theory developed in Section 40.4, we know this spline has a continuous second derivative. However, if we wish to change the shape near one of the four interpolated points, we would have to recompute the complete spline. A small local change in the shape of the curve requires the recalculation of all the coefficients of all the component polynomials making up the spline.

Alternatively, we can interpolate the given points with three Bezier cubics by introducting control points such as

> p[1] := [2,2];
p[2] := [1,6];

>

between and ; introducing control points such as

> p[4] := [5,1];
p[5] := [8,-1];

>

between and ; and introducing control points such as

> p[7] := [8,5];
p[8] := [12,-3];

>

between and . Then, three separate cubic Bezier curves can be constructed between and , and , and between and . In fact, these three Bezier curves are given by

> R1 := map(simplify,evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k],k=0..3)));
R2 := map(simplify,evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k+3],k=0..3)));
R3 := map(simplify,evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k+6],k=0..3)));

>

Each Bezier segment is independent from the others. This is clear even from an attempt to graph them. The parameter ranges between 0 and 1 for each of the curves. The location of the graphs of these three segments is "built-into" the representation of each segment.

Figure 40.14 shows these three Bezier curves, along with the control points, and the "handles" at the ends of the Bezier segments, is given below. The middle segment is graphed in cyan.

> F8 := plot([R1[1],R1[2],u=0..1],color=black):
F9 := plot([R2[1],R2[2],u=0..1],color=cyan, linestyle=2):
F10 := plot([R3[1],R3[2],u=0..1],color=black):
F11 := seq(disk(p[k],.15,color=black),k=0..9):
F12 := plot([[p[0],p[1]], [p[2],p[3]], [p[3],p[4]], [p[5],p[6]], [p[6],p[7]], [p[8],p[9]]], color=red, linestyle=2):
pp:=textplot({[.5,-.5,`p0`],[2.1,1.5,`p1`],[1,6.4,`p2`],[4.5,7,`p3`], [5,.5,`p4`],[8.5,-1,`p5`],[7.5,2,`p6`],[8,5.5,`p7`],[12.5,-3,`p8`], [10.5,5,`p9`]}):
display([F||(8..12),pp], scaling=constrained, labels=[x,`y `], labelfont=[TIMES,ITALIC,12], xtickmarks=7, ytickmarks=5);

>

We have lost continuity of the derivative. The three Bezier curves form a continuous spline, but not necessarily a differentiable one. We have lost some degree of smoothness, but have gained "local control." Thus, if control point is changed, only the first segment would be affected. The remaining portion of the interpolating spline would not have to be recalculated. We can see this analytically if we change to

> p[2] := [1,t];

>

in an attempt to vary through a range of values. The influence of is felt only by R , which, in terms of , becomes

> Rt := map(simplify,evalm(add(binomial(3,k)*(1-u)^(3-k)*u^k*p[k],k=0..3)));

>

The following animation shows the complete spline responding to variations in control point . For maximal visual impact, set the animation control to "oscillate."

> F13 := z->plot([Rt[1],subs(t=z,Rt[2]),u=0..1],color=red):
F14 := seq(disk(p[k],.15,color=black),k=0..1):
F15 := seq(disk(p[k],.15,color=black),k=3..9):
F16 := z->display(disk(subs(t=z,p[2]),.15,color=black)):
F17 := plot([[p[0],p[1]], [p[3],p[4]], [p[5],p[6]], [p[6],p[7]], [p[8],p[9]]], color=magenta, linestyle=2):
F18 := z->plot([subs(t=z,p[2]),p[3]], color=magenta, linestyle=2):
F19 := z-> display([F13(z),F16(z),F18(z)]):
F20 := display([seq(F19(4+k/5),k=0..25),seq(F19(9-k/5),k=1..24)], insequence=true):
display([F9,F10,F14,F15,F17,F20], scaling=constrained);

>

Clearly, the Bezier spline allows local control of the shape of the interpolating funtion. Differentiability can be regained by choosing control points for which the slopes of contiguous "handles" are equal.

>

References

[1] Richard L. Burden and J. Douglas Faires, Numerical Analysis, Sixth Edition, Brooks/Cole Publishing Company, 1997.

[2] Curtis F. Gerald and Patrick O. Wheatley, Applied Numerical Analysis, Fifth Edition, Addison-Wesley Publishing Company, 1994.

>