CS 4620 Homework 7 solution

This problem can be solved various ways, but the matrix form of the spline equation is handy.  I solved this homework in Matlab using the following function:

----------
function X = spline_eval(M, P, t)

% Evaluates a spline given the spline matrix M and control point sequence,
% at the parameter values given in the column vector t.
% The matrix M is (d+1) by k, where d is the degree of the spline and k
% is the order (number of control points affecting a segment -- normally
% k == d+1).  The control point sequence P is k by D, where D is the
% dimension of the curve.

d = size(M,1)-1;
N = length(t);
T = (t * ones(1,d+1)) .^ (ones(N,1) * (d:-1:0));
X = T*M*P;
----------

(This is not really the way to evaluate a spline in practice, but it is simple and flexible.)

Part 1:

P = [-1 0; 0 -1; 1 0; 0 1]

M_bez = [-1 3 -3 1; 3 -6 3 0; -3 3 0 0; 1 0 0 0]
M_h = [2 -2 1 1; -3 3 -2 -1; 0 0 1 0; 1 0 0 0]
M_cr = M_h * [0 1 0 0; 0 0 1 0; -.5 0 .5 0; 0 -.5 0 .5]
M_bs = [-1 3 -3 1; 3 -6 3 0; -3 0 3 0; 1 4 1 0]/6

X_bez = spline_eval(M_bez, P, linspace(0,1,101)')
X_cr = spline_eval(M_cr, P, linspace(0,1,101)')
X_bs = spline_eval(M_bs, P, linspace(0,1,101)')

The matrices X can be used to plot the coordinate functions (each column separately) or the spline curve (column 1 against column 2).

Part 2:

Inspection of the plots shows it is easy to get the bboxes of the Catmull-Rom and B-spline curves, because the ends of the curve are the corners of the box.  For the Bezier spline, we need to find the maxima of the coordinate functions.  We can do that by solving for the zeroes of the derivative, which is a quadratic function.  In Matlab we can do this in a slick way by using a matrix multiplication on the coefficients to do the differentiation and then using "roots" as a shorthand for the quadratic formula.  But you could achieve the same result by manually differentiating the coordinate functions and using the quadratic formula to find the roots.

roots([3 0 0 0; 0 2 0 0; 0 0 1 0] * M_bez * P(:,1))
roots([3 0 0 0; 0 2 0 0; 0 0 1 0] * M_bez * P(:,2))

The maxima for x and y (ignoring roots that fall outside the [0,1] interval) are at t = 1-sqrt(1/2) and t = sqrt(1/2) respectively.  Evaluating the spline for that t value reveals the maxima are at sqrt(2) - 1.

Part 3:

Using the matrix formulation, this can be done quite simply.  The idea is to apply a linear transformation to the points so that when they are used with the "destination" spline matrix the same result is achieved as would have been achieved with the "source" spline matrix.  That is, we want new points X P so that, e.g., M_cr X P == M_bez P.  Solving for X, X = inverse(M_cr) * M_bez.  In Matlab:

>> P_cr = (M_cr \ M_bez) * P

P_cr =

   -6.0000    7.0000
   -1.0000    0.0000
    0.0000    1.0000
   -7.0000    6.0000

>> P_bs = (M_bs \ M_bez) * P

P_bs =

   -4.0000    7.0000
   -1.0000   -2.0000
    2.0000    1.0000
   -7.0000    4.0000