B-splines



              
A picture of the knots and basis-functions of a given B-spline curve of degree 2, from Figure 6.6 in Blending techniques in Curve and Surface constructions.

A B-spline curve is expressed by the following formula:   \( C(t) = \displaystyle\sum_{i=0}^{n-1} p_i\ b_{d,i}(t),\ \ \) where we has \(n\) control points \(p_i\), polynomial degree \(d\), and \(n\) scalar basis functions \(b_{d,i}(t)\). In the figure above, a set of basis functions is plotted. We have a knot vector  \(\mathbf{ \overline t}=\{ 0,\ 0,\ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 8,\ 8 \}\). They are marked with red dots in the figure. This knot vector and the degree \(d=2\) then generate the basis functions \(b_{2,i}(t),\ i=0,1,...,9 \) which are plotted in each color in the figure above . Note that the parameter domain is \([t_d,\ t_n] = [0_,\ 8]\). As we see in the figure, the knot values divide the domain into 8 segments. In the figure below, we have added \(n=10 \) control points  \(p_i,\ i=0,1,...,9\) which are marked with black pentagons. Thin black line segments are plotted between the points. We call these line segments together a control polygon. We also see a set of round red markers in the figure below. There are 7 located on the control polygon and one at each end which is partially covered by the control point pentagons. These correspond to the 9 knot values \(t_2,\ t_3,\ ...,\ t_{10} \).
 

If you click on the figure, you will get a B-spline curve where: degree and open/closed can be set and knot values and control points can be changed graphically.

The figure is from Figure 6.7 i blendingsboka.

When you click on the link above you get a graphical editor to create and modify the B-spline curve plotted above. The user interface is a menu at the top right and the use of a mouse.

A 3rd degree B-spline curve will have the following formula using matrix formulation:

\( c(t) = \begin{bmatrix}1- w_{1,i}(t)  & w_{1,i}(t) \end{bmatrix} \begin{bmatrix} 1- w_{2,i-1}(t) & w_{2,i-1}(t)  & 0  \\ 0 & 1- w_{2,i}(t) & w_{2,i}(t)  & 0 \end{bmatrix} \begin{bmatrix} 1- w_{3,i-2}(t) & w_{3,i-2}(t)  & 0 & 0  \\ 0 & 1- w_{3,i-1}(t) & w_{3,i-1}(t)  & 0 \\ 0 & 0 & 1- w_{3,i}(t) & w_{3,i}(t)  \end{bmatrix} \begin{bmatrix} c_{i-3} \\ c_{i-2} \\ c_{i-1} \\ c_{i} \end{bmatrix}\),   when   \(t \in[t_i, t_{i+1})\),

and where  \(w_{d,i}(t) = \frac{t - t_i}{t_{i+d} - t_i} \),  see section 6.2.3 in Blending techniques in Curve and Surface constructions.

If we multiply the 3 matrices we get:   \( c(t) =  \begin{bmatrix} b_{3,i-3}(t)  &  b_{3,i-2}(t)  &   b_{3,i-1}(t)  &   b_{3,i}(t)  \end{bmatrix} \begin{bmatrix} c_{i-3} \\ c_{i-2} \\ c_{i-1} \\ c_{i} \end{bmatrix} \ \).

The following algorithm performs the matrix multiplications and provides the B-spline bases for  \(t \in[t_i, t_{i+1})\)

    vector<double>  b(d+1);   // A vector for  \(b_{d,i}(t) \quad i=0,1,...,d\).

    b[0] =  \(1\);

    for (\(j=1\); \(j\leq d\); \(j++)\)

       b[j] = \(w_{j,i}(t)\) b[j-1];

       for (\(k=j-1\); \(k > 0\); \(k--)\)

          b[k] = \(w_{j,i-j+k}(t) \) b[k-1] + \( (1-\) \(w_{j,i-j+k+1}(t)) \) b[k];

       b[0] = \((1-\) \(w_{j,i-j+1}(t))\) b[0];

This algorithm is algorithm 3 in the  book.  An extended algorithm that also calculates all derivatives is algorithm 4 in the book.