CS-460/560, Week 11-A
Spring, 1998
R. Eckert

B-SPLINE POLYNOMIALS

Cubic B-Spline Polynomial Curves--Approximate m+1 control points
Pi (i=0,1,2,...m) with a curve consisting of m-2 cubic polynomial
curve segments Qi (i=3,4,...m). Each Qi is defined in terms of a
parameter, t, over the range ti<=t<=ti+1 and by four of the m+1 control
points. In other words, segment Qi is determined by:

  P   , P   , P   , P  between t  and t   .
   i-3   i-2   i-1   i          i      i+1

  Qi begins at t=t , and Q    joins Q  at t   . Join point called a knot.
                  i       i+1        i     i+1

For example, the first segment is Q3, begins at t3, and is determined by
control points P0,P1,P2,P3.

Each control point affects only 4 curve segments.

A special case is that of uniform cubic B-Splines, where we assume that:

  t    = t  + 1.
   i+1    i

We write the polynomial equation for segment Qi as follows:

  Qi(t) = a*(t-ti)^3 + b*(t-ti)^2 + c*(t-ti) + d,  ti<=t<=ti+1

We can consider the independent variable to be t-ti; it will vary from 0 to
1 for any interval.

As for the cubic Bezier curves, we want to try to find a "B-Spline Basis
Matrix" so that we can compute the polynomial coefficients (a,b,c,d) from
the control points. Here, of course, we'll have to do the computation for
each interval:

  |a|           |Pi-3|
  |b| =  M   *  |Pi-2|   (Here I've written Pi-3, but this means P    )
  |c|     BS    |Pi-1|                                            i-3
  |d|           | Pi |

where M   is the matrix we need. In order to get this matrix, we need
       BS
need to apply the B-spline continuity conditions. These are conditions on
the continuity of the first and second derivatives of the polynomial.

1. dQi/dt (at t=ti) = slope of line segment joining Pi-3 and Pi-1.

2. dQi/dt (at t=ti+1) = slope of line segment joining Pi-2 and Pi.

                                _________             _______
3. (dQi/dt)' (t=ti) = (slope of Pi-3 Pi-2  - slope of Pi-2 Pi) / del_t

                                  _________             _______
4. (dQi/dt)' (t=ti+1) = (slope of Pi-2 Pi-1  - slope of Pi-1 Pi) / del_t

Conditions 3 and 4 are conditions on the second derivative, (dQi/dt)'.

In general: dQi/dt = 3*a*(t-ti)^2 + 2*b*(t-ti) + c

And: (dQi/dt)' = 6a*(t-ti) + 2*b

Condition 1 --> c = (1/2) * ( P    - P   )
                               i-1    i-3


Condition 2 --> 3*a + 2*b + c = (1/2) * (P  - P   )
                                          i    i-2

Condition 3 --> 2*b = ( (P   - P   ) - (P    - P   ) ) / 1
                          i-1   i-2      i-2    i-3

Condition 4 --> 6*a + 2*b = ( (P   - P   ) - (P    - P   ) ) / 1
                                i     i-1      i-1    i-2

Notice that these four eqations are not independent--If we solve them we
will only get a, b, and c, but not d. The results are:

  a = (1/6) * (-P    + 3*P    - 3*P    + P )
                 i-3      i-2      i-1    i

  b = (1/6) * (3*P    - 6*P    + 3*P   )
                  i-3      i-2      i-1

  c = (1/6) * (-3*P    + 3*P   )
                   i-3      i-1

To get the d polynomial coefficient, we need another condition. We choose
the following condition:

  Q (at t=ti) = (1/6) * (P    + 4*P    + P   )
                          i-3      i-2    i-1

In other words the control point at ti (Pi-2) pulls four times as hard on
the curve at t=ti as the control points on either side ot ti.

Substituting in the polynomial equation gives:

  d = (1/6) * (P    + 4*P    + P   )
                i-3      i-2    i-1

Thus our polynomial coefficient matrix equation is:

  |a|           |-1  3 -3  1|   |Pi-3|
  |b| = (1/6) * | 3 -6  3  0| * |Pi-2|
  |c|           |-3  0  3  0|   |Pi-1|
  |d|           | 1  4  1  0|   | Pi |


PLOTTING UNIFORM CUBIC B-SPLINES:

Assume we are given m+1 control points P0,P1,P2,...Pm. (Recall that each of
these has an x and y coordinate--i.e., P0 --> x0 and y0.). The following is
a "brute force" algorithm to plot the curve:

  For (i=3 to m)
     Compute ax,bx,cx,dx and ay,by,cy,dy from ctrl pts i-3, i-2, i-1, i
     For (t=0; t<=1; t+=delta)
        x = ax*t^3 + bx*t^2 + cx*t + dx
        y = ay*t^3 + by*t^2 + cy*t + dy
        If (t==0)
           MoveTo(x,y)
        Else
           LineTo(x,y)


PROPERTIES OF UNIFORM B-SPLINES:

1. Local Control--Each segment is determined by only 4 control points
2. The curve approximates control points; does not interpolate
   (However if you triplicate a control point, it will be interpolated)
3. The curve lies entirely inside the convex hull of the control points
4. The curve is invariant under affine transformations
5. The curve is vey smooth--level-2 continuity everywhere
6. More computations required than for an "equivalent" Bezier curve