10. Problems

Problem DD-1. Sketch the relaxed cubic B-spline curve with control points $(0,0)$, $(1,0)$, $(1,1)$, $(0,1)$, $(0,0)$. (Calculate the Bézier control points, then sketch the Bézier curves freehand. Use a large enough scale that your sketch is meaningful.)

Problem DD-2. (a) In constructing a cubic B-spline curve from given control points $B _ 0,\ldots ,B _ n$, all the Bézier control points you generate are in the convex hull of the set of $B_i$. Why?

(b) Explain how it follows from (a) that the whole curve is in the convex hull of the set of $B_i$.

(c) If all the $B_i$ are on your rectangular screen, is the whole cubic B-spline curve necessarily on the screen? (Why?)

Problem DD-3. (a) If you use B-spline control points $B _ 0,\ldots ,B _ {20}$ to get a B-spline curve $P(t)$ with $0 \leq t \leq n$, which $B_i$ affect $P(5.3)$? (b) Which affect $P(6.0)$?

Problem DD-4. (a) For the relaxed cubic spline through data points $S_0$, $S_1$, $S _ 2$, find formulas for the B-spline and Bézier control points involved. (This is the case $n=2$, so you won't need a matrix to solve equations. Your answers will be linear combinations of the data points.)

(b) By Lagrange, there is actually a single quadratic polynomial through the data points in (a). In general, will the two Bézier curves in (a) actually both match this one quadratic curve? (Say why or why not.)

(c) Sketch the relaxed cubic spline curve through data points $(1,0)$, $(1,1)$, $(0,1)$.

(d) Show that $P({\frac 1 2}) = {\frac{13}{32}} S _ 0 + {\frac {22}{32}} S _ 1 - {\frac 3{32}} S _ 2$ for the relaxed cubic spline curve $P(t)$ interpolating $S _ 0, S _ 1, S _ 2$, where $0 \leq t \leq 2$.

Problem DD-5. For the basis functions for relaxed cubic splines in the case $n=2$, find their values at $t = {\frac 1 2}$. (You may use the results of Problem DD-.)

Problem DD-6. Sketch the relaxed cubic spline through data points $(0,0)$, $(1,1)$, $(2,0)$, $(3,0)$. (Calculate the B-spline and Bézier control points, then sketch the Bézier curves freehand. Use a large enough scale that your sketch is meaningful. Useful information: $\left[\begin{array}{cc}4&1\\ 1&4\end{array}\right] ^ {-1} = \frac 1{15} \left[\begin{array}{rr}4&-1\\ -1&4\end{array}\right]$.)

Problem DD-7. Sketch the relaxed cubic spline through data points $(0,0)$, $(1,0)$, $(2,1)$, $(3,0)$, $(4,0)$. (Calculate the B-spline and Bézier control points, then sketch the Bézier curves freehand. Use a large enough scale that your sketch is meaningful.) Useful information: $\left[\begin{array}{ccc}4&1&0\\ 1&4&1\\ 0&1&4\end{array}\right] ^ {-1} = \frac 1{56} \left[\begin{array}{rrr} 15&-4&1\\ -4&16&-4\\ 1&-4&15\end{array}\right]$

Problem DD-8. Suppose two people are given control points $B _ 0,\ldots ,B _ n$ and an affine transformation $T$ (the same $B_i$ and $T$ for each person). The first person finds the B-spline curve $P(t)$ with control points $B_i$ ( $0 \leq t \leq n$ ) and then draws the curve $T(P(t))$. The second person finds the points $T(B _ i)$ and uses them as control points to make a B-spline curve (also for $0 \leq t \leq n$). Do the two people get the same curve? (Explain.)

Problem DD-9. Suppose three consecutive B-spline control points are evenly spaced on a straight line. (a) Describe the A-frame of the middle control point of the three. (b) What is the second derivative of the curve at the middle control point?

Problem DD-10. For the Bézier curves making up a B-spline curve, each Bézier curve depends on only several of the control points $B_i$. Therefore there is no harm in using an infinite list of control points. In fact, the list could be $\ldots , B _ {-1}, B _ 0, B _ 1, B _ 2,\ldots$.

(a) Sketch the B-spline curve you get if the infinite list of $B_i$ keeps going around the corners of a Box: $B _ 0 = (1,1)$, $B _ 1 = (-1,1)$, $B _ 2 = (-1,-1)$, $B _ 3 = (1,-1)$, and $B _ 4 = B _ 0$, $B _ 5 = B _ 1$, etc., and also $B _ {-1} = B _ 3$, $B _ {-2} = B _ 2$, etc. (Calculate the $S_i$ and the Bézier control points precisely and sketch the Bézier curves freehand.)

(b) Is the curve you get an exact circle? How do you know?

Problem DD-11. (a) Suppose two cubic polynomials $p(t)$ and $q(t)$ have equal values at $t = t _ 0$, equal first derivatives, equal second derivatives, and equal third derivatives. Then they must be the same polynomial. Why? (Quote Taylor's Theorem.) (b) State a similar fact about cubic parametric curves, and say why it follows from (a). (c) In trying to glue cubic Bézier curves to make a single B-spline curve, we matched first and second derivatives, but not the third. Why not?

Problem DD-12. (a) Find a matrix $M$ so that the Bézier curve with control points $P _ 0,\ldots ,P _ 3$ can be written as $P(t) = \left[\begin{array}{cccc} 1&t&t ^ 2&t ^ 3\end{array}\right] M \left[\begin{array}{c}P _ 0\\ P _ 1\\ P _ 2\\ P _ 3\end{array}\right]$.

(Method: Each column of $M$ tells the expansion of a Bernstein polynomial in powers of $t$.)

(b) Suppose you have B-spline control points $B _ 0,\ldots ,B _ n$. Find a matrix $H$ so that the Bézier control points of Bézier curve #$i$ can be written as

${\left[\begin{array}{c}P _ 0\\ P _ 1\\ P _ 2\\ P _ 3\end{array}\right]}$ $=$ $H {\left[\begin{array}{l}B _ {i-2}\\ B _ {i-1}\\ B _ i\\ B _ {i+1}\end{array}\right]}$.

(See the explanation of the computer method in Section 4.)

(c) Explain how to use (a) and (b) to get a matrix expression for the point on Bézier curve #$i$ corresponding to a given $t$ (with $0 \leq t \leq 1$), in terms of the $B_i$.

Problem DD-13. Sketch the clamped cubic spline curve $P(t)$ through $(0,0)$, $(1,1)$, $(2,2)$ with $P'(0) = (1,0)$ and $P'(2) = (1,0)$.

(Method: Calculate B-spline and Bézier control points and then sketch the Bézier curves freehand.) Useful information:

${ {\left[\begin{array}{ccc}2&1&0\\ 1&4&1\\ 0&1&2\end{array}\right]}}^{-1}$ $=$ ${\frac 1 {12}} {\left[\begin{array}{ccc}7&-2&1\\ -2&4&-2\\ 1&-2&7\end{array}\right]}$

Problem DD-14. Sketch one cartoon frame with a simple character and some coordinate axes. Give a list of numbers that describes the cartoon. Say what each number represents, for example, the $x$ and $y$ coordinates of a specific point. Give enough information that if the numbers were changed, someone else could draw the new position of the character.

Problem DD-15. The leg and foot of a cartoon character are shown in keyframes at times $t = 0,1,2$, in Figure . Sketch the interpolated frame for $t = .5$, using relaxed cubic spline interpolation. (Calculate the position of the heel precisely; for this you may use the result of Problem DD- for the case $n=2$ at time $\frac{1}2$. You may use intuition for the other two points of the character.)

Figure: Cartoon frames at times 0, 1, 2

Problem DD-16. Suppose that you were to compute a large number of frames based on the keyframes in Figure , for $0 \leq t \leq 2$. In what way would the motion look better than if you had simply interpolated linearly between the first two key frames and then interpolated linearly between the second and third?

Problem DD-17. Sketch the nonparametric uniform relaxed cubic spline function with data values $0,1,0,-1,0$. (Method: This is the case $n=4$. Use the method of Section 8 and the basis functions from Figure .)

Problem DD-18. For two Bézier curves $P(t)$ and $Q(t)$, with respective lists of control points $P_0,\dots, P_3$ and $Q_0,\dots, Q_3$, linearly interpolating between the curves is the same as linearly interpolating between the control points. For example, if $R_i$ is the point one-third of the way from $P_i$ to $Q_i$ for each $i$, then the Bézier curve $R(t)$ with control points $R_0,\dots, R_3$ is one-third of the way from $P(t)$ to $Q(t)$, in the sense that for each $t$, the point $R(t)$ is one-third of the way from the point $P(t)$ to the point $Q(t)$.

(a) Prove the statement in this last sentence. (Let $R_0 = {\frac 2 3} P_0 + {\frac 1 3} Q_0$, etc.)

(b) Sketch the Bézier curve that is one-third of the way from the Bézier curve with control points $(0,0)$, $(6,0)$, $(6,6)$, $(0,6)$ to the Bézier curve with control points $(0,0)$, $(6,0)$, $(6,6)$, $(12,6)$.

Problem DD-19. It would be possible to use Lagrange interpolation for animation, but would the results be very good? To see what might happen, imagine a cartoon character walking along between times $t = 0$ and $t = 10$. She is walking at constant speed to the right, and is walking on one level until time $t = 7$, when she goes up one step and then walks at the new level for the rest of the time. What motion would Lagrange interpolation give? (Consult Figure .)

Problem DD-20. For the B-spline curve $B(t)$ with control points $B_0,\dots, B_n$, show that for $i = 1,\dots, n-1$,

(a) $B'(i) =$ half the vector from $B_{i-1}$ to $B_{i+1}$,

(b) $B''(i) =$ twice the vector from $B _ 1$ to the midpoint of the segment from $B_{i-1}$ to $B_{i+1}$.

Remark. These facts make it easy to look at the control polygon for a B-spline and see where the first and second derivatives will be larger and where they will be smaller. Although these facts apply only at the points $B(i) = S _ i$, in the case of the second derivative it is easy to tell what happens between: Since that $B(t)$ itself is piecewise cubic, $B'(t)$ is piecewise quadratic, and $B''(t)$ is piecewise linear, so the second derivative changes linearly from each point $S_i$ to the next, the points where you do know the second derivative--and this includes the ends, since the second derivative there is 0.