CS 465 Solution 9
(revised November 29, 2004)

Problem 13

See the file posted on the web site for an example robot

Problem 14

1) The rules for subdividing a line are fairly simple. Given this setup:
   
   a1    a2    a3     a4 ...
   b1 b2 b3 b4 b5 ...

   We want to subdivide the list of values a1-a4 and get the resulting
   list b1-b5.  Using the rules discussed in lecture,

   b1 = a1 (since we have fixed the end points)
   b2 = (4*a1 + 4*a2)/8
   b3 = (a1 + 6*a2 + a3)/8
   b4 = (4*a2 + 4*a3)/8
   b5 = (a2 + 6*a3 + a4)/8
   ...


   This resulting list of b-values is then subdivided further to obtain a
   level 2 subdivision curve.


   I implemented this procedure in matlab, and have attached the code at the
   end of this solution.  The graphs are also posted on the web page, next to
   the robot soluion. The list of points is:

    x       y
   -3     0
   -2.75  0
   -2.5   0
   -2.25  0
   -2     0
   -1.75  0
   -1.5   0.015625
   -1.25  0.0625
   -1     0.15625
   -0.75  0.3125
   -0.5   0.48438
   -0.25  0.625
    0     0.6875


2) f_b(+/- 2) = 0.     Our basis function is also 0 at this distance.
   f_b(+/- 1) = 1/6.   Our basis function is 0.15625, just below the actual
   BSpline function.
   f_b(0)     = 2/3    Our basis function is 0.6875 at the center, just above
   the BSpline function.

   It appears that our basis function is approaching the actual BSPline curve,
   from above in points that are more near the center, and from below on
   points that are further out.


3) At 4 levels of subdivision, the subdivision curve evaluates to 0.66797 at
   point D.  This is very close to the BSpline curve.


4) These plots are also in the graph posted on the web site.



The Matlab commands I used to generate the plots are:

>> [xResult, yResultA] = compute_points(xStart, yStartA, 2);
>> [xResult, yResultB] = compute_points(xStart, yStartB, 2);
>> [xResult, yResultD] = compute_points(xStart, yStartD, 2);
>> plot(xResult, yResultA, xResult, yResultB, xResult, yResultD);

where xStart  = [-3; -2; -1;  0;  1;  2;  3]
      yStartA = [ 1;  0;  0;  0;  0;  0;  0]
      yStartB = [ 0;  1;  0;  0;  0;  0;  0]
      yStartD = [ 0;  0;  0;  1;  0;  0;  0]

The matlab function compute_points is:


function [xList, yList] = compute_points(xValues, yValues, level)

if level == 0
    xList = xValues;
    yList = yValues;
    return;
end

n = size(xValues, 1);
xValues2 = zeros(2*n - 1, 1);
yValues2 = zeros(2*n - 1, 1);

xValues2(1) = xValues(1);
xValues2(2*n - 1) = xValues(n);

yValues2(1) = yValues(1);
yValues2(2*n - 1) = yValues(n);

for i = 2:2*n - 2
    if mod(i, 2) == 0
        xValues2(i) = (xValues(i/2) + xValues(i/2 + 1))/2;
        yValues2(i) = (yValues(i/2) + yValues(i/2 + 1))/2;
    else
        yValues2(i) = (yValues((i - 1)/2) + 6*yValues((i + 1)/2) + yValues((i + 3)/2))/8;
        xValues2(i) = xValues((i + 1)/2);
    end
end

[xList, yList] = compute_points(xValues2, yValues2, level - 1);