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.
- With the left mouse button you move knots(red dots) either to the
right or to the left. The basis-functions and the curve will then be
updated.
- You can also move control points with the left mouse button and then
the curve will be updated when you release the mouse button.
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.
