B-Splines

This node has NOT been proof-read yet. It should be correct considering I have spent a great many of the last 24 hours working on this very project for my Computer Graphics class. Any changes suggested in additional write-ups will be added to this node as soon as I see them.

A mathematical construct useful in creating surfaces for graphical images. The idea is that the user creates 16 "control points" or points that shape the surface, and the computer builds the surface based on those points.

The surface is actually formed by averaging all of the control points multiple times with different weights each time. The result of each average calculation is what I will call a "surface point", a point that actually makes up the surface of the object.

The way this works is simple, though it has a lot of matrix multiplication that is difficult to program correctly.

Create three 4x4 matrices, each of which contains a single dimension of all the control points (all the x's, all the y's, and all the z's). Keep these matrices separate:

	|x00 x01 x02 x03|
	|x10 x11 x12 x13|
	|x20 x21 x22 x23|
	|x30 x31 x32 x33|

Choose the number of points along the x and y axis that you wish to calculate. Call these two values (usually equal values) sStep and tStep. Then, divide the interval [0, 1.0] into sStep and tStep subintervals (larger sStep and tStep valuse require more calculation, but they are visually more accurate).

Matrix S is a 1x4 matrix defined like this:

	S = |s^3 s^2 s^1 s^0|

s is determined by the current iteration across the interval [0, 1.0]. See the algorithm listed below for further explanation.

Matrix T is a 4x1 matrix defined in a way similar to S:

	T = | t^3 |
	    | t^2 |
	    | t^1 |
	    | t^0 |

M is called the "magic matrix" of this transformation and is the matrix where all of the really complicated magic happens. Mt is the transpose matrix of M.

	M = 1/6 * | -1  3 -3  1 |
		  |  3 -6  3  0 |
		  | -3  0  3  0 |
		  |  1  4  1  0 |

Gx is the matrix of the x dimension of the control points. I actually think of control points as being the points actually on a surface, which helps me to organize things in my head. Think of control points that are adjacent in the matrix as being adjacent to each other in "reality".

Gy is the matrix of the y dimension of the control points, and Gz is the matrix of the z dimension of the control points.

for s = 0 to 1.0 step sStep
	for t = 0 to 1.0 step tStep
		surfacePoint[s][t].x = S*M*Gx*Mt*T
		surfacePoint[s][t].y = S*M*Gy*Mt*T
		surfacePoint[s][t].z = S*M*Gz*Mt*T

This defines the surface points in an array. From these points, you must actually build the rectangles (or in my case, triangles) that you will draw on the screen. Actually, it is a very simple procedure. It goes along these lines:

for any arbitrary x and y where 0.0 <= x, y < 1.0:
	rectangle.p1 = surfacePoint[x][y]
	rectangle.p2 = surfacePoint[x+1][y]
	rectangle.p3 = surfacePoint[x+1][y+1]
	rectangle.p4 = surfacePoint[x][y+1]

-- or --

	triangle1.p1 = surfacePoint[x][y]
	triangle1.p2 = surfacePoint[x+1][y]
	triangle1.p3 = surfacePoint[x][y+1]
	triangle2.p1 = surfacePoint[x+1][y]
	triangle2.p2 = surfacePoint[x+1][y+1]
	triangle2.p3 = surfacePoint[x][y+1]

The triangle definition has the same shape as the rectangle definition, but has the advantage that you don't have to deal with any problems with the shapes not being co-planar. Also, with that particular triangle definition, both triangles will be mathematically defined to be facing the same direction.

For a HUGE amount more information, check out this book: Computer Graphics: Principles and Practice, Second Edition in C by Foly, van Dam, Feiner and Hughes, published by Addison Wesley, 1996

The above is a very good explanation of B-Spline surfaces using a matrix approach. However, for those less familiar with linear algebra, I'll try to explain B-Spline curves using a different approach. From that, it will be relatively simple to extend this to surfaces.

A B-Spile curve is very similar to a Bezier curve. In fact, if you understand the approach to constructing a Bezier curve, a B-Spline curve is only a generalization, thereof.

For a B-Spline curve, you are given L+1 control points (CPs) and what is called a knot vector with K+1 knots on it. Let us call the CPs d⁰₀ through d⁰_L and call the knots u₀ through u_K. The degree of the curve, n, is given by n=K-L+1. Then to extrapolate a point on the B-Spline curve, you have to use the formula

where a is the local parameter on the interval [u(j+i),u(j+n-i)). Specifically:

a = (u-u_j+1)/(u_j+n-i-u_j+1)

You would repeat this process until you are left with one point, which is the point on the B-Spline curve. Below is an example calculation for clarity.

Our example will have 4 CPs and 6 knots on the knot vector. Therefore, the resulting curve will have be degree-3 (6-4+1). The order of calculation of the points would occur as follows:

d⁰₀
d⁰₁ d¹₀
d⁰₂ d¹₁ d²₀
d⁰₃ d²₂ d²₁ d³₀

So d⁰₀ and d⁰₁ would be used to calculate d¹₁ and so forth until you arrived at d³₀, which is the point on the curve at the given parameter. To show how the knot span works, below is a graphic of what span each calculated point requires:

|--------|--------|--------|--------|--------|
u0       u1       u2       u3       u4       u5
|--------------------------|                     d10
         |--------------------------|            d11
                  |--------------------------|   d12
         |-----------------|                     d20
                  |-----------------|            d21
                  |--------|                     d30

It is important to note that the curve is only defined over the interval [u₂,u₃]. If there were more CPs and more knots, the curve would be defined over a larger span. In general, a B-Spline curve is defined over the interval [u_n-1,u_K-n].

Hopefully, that explanation gives some idea as to how a B-Spline curve is constructed. To extend this idea to a surface, imagine a two-dimensional grid of CPs and two knot vectors. One would then calculate curves in one direction for the CPs to follow in the other direction. Then those CPs would be used to calculate points on the surface.

If there are things that are unclear me, drop me a message, and I will try to clear them up here.