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