4. B-Splines

Bases Spline

See also

4.1. Normalized B-spline base function

Let consider the values \(u_i \in \mathbb{R}, i \in \mathbb{Z}\), which fulfils \(u_i \leq u_{i+1}\)! We can define the B-spline base function in the following form:

\[\begin{split}N_i^1(u) = \begin{cases} 1, & \text{if } u_i \leq u < u_{i+1}, \\ 0, & \text{else}, \end{cases}\end{split}\]
\[N_i^k(u) = \dfrac{u - u_i}{u_{i+k-1} - u_i} N_i^{k-1}(u) + \dfrac{u_{i+k} - u}{u_{i+k} - u_{i+1}} N_{i+1}^{k-1}(u).\]

  • The \(\{u_i\}_{i \in \mathbb{Z}}\) values are the knot values.

  • Its components results the knot vector.

  • We define the result of zero division as 0 when it can occur.

\(\rhd\) Let write the second and third order B-spline base functions!

For the determination of the values \(u_i\) we can use uniform parametrization, for example \(u_i = i\).

The curve with the same degree can be derived from each others by translation:

\[N_i^k(u) = N_0^k(u - i), \quad \forall i \in \mathbb{Z}.\]

Note

  • The B-spline base function of order \(k\) contains (at most) \((k-1)\) degree polynomials.

  • The base function \(N_i^k\) can be non-zero only on the interval \((u_i, u_{i+k})\).

  • Let consider the interval \([u_i, u_{i+1})\)! It has effect to the base functions \(N_j^k\), where \((i - k + 1) \leq j \leq i\).

4.1.1. Theorem of local support

\[N_i^k(u) = 0, \text{if } u \notin [u_i, u_{i+k}).\]

Proof (induction)

In the case of \(k = 1\) the statement is true by definition.

Let substitute the value \((k-1)\) and let consider that

\[\begin{split}\begin{align} &N_i^{k-1}(u) = 0, \text{if } u \notin [u_i, u_{i+k-1}), \\ &N_{i+1}^{k-1}(u) = 0, \text{if } u \notin [u_{i+1}, u_{i+k}). \\ \end{align}\end{split}\]

When \(u \notin [u_i, u_{i+k})\) we have to calculate the linear combination of them (in the function of \(u\)), which guarantees that its value must be 0. \(\square\)

4.1.2. Theory of non-negativity

The normalized B-spline base functions are non-negate, in other words

\[N_i^k(u) \geq 0, \forall u \in \mathbb{R}, i \in \mathbb{Z}, k \geq 1.\]

4.1.3. Theorem of partition of unity

The sum of the normalized B-spline base functions are 1 at any point in the defined domain:

\[\sum_j N_j^k (u) = 1, \quad \forall u \in \mathbb{R}, \forall k \geq 1.\]

4.1.4. Multiple knot values

The definition makes possible to use the same \(u_i\) knot values multiple times. Let consider its effect in the case of degree 3 B-spline base function!

We can write the normalized B-spline base function of degree 3 as

\[\begin{split}N_i^3(u) = \begin{cases} \dfrac{(u-u_i)^2}{(u_{i+2}-u_i)(u_{i+1}-u_i)}, & \text{if } u \in [u_i, u_{i+1}), \\ \dfrac{(u-u_i)(u_{i+2}-u)}{(u_{i+2}-u_i)(u_{i+2}-u_{i+1})} + \dfrac{(u_{i+3}-u)(u-u_{i+1})}{(u_{i+3}-u_{i+1})(u_{i+2}-u_{i+1})}, & \text{if } u \in [u_{i+1}, u_{i+2}), \\ \dfrac{(u_{i+3}-u)^2}{(u_{i+3}-u_{i+1})(u_{i+3}-u_{i+2})}, & \text{if } u \in [u_{i+2}, u_{i+3}), \\ 0, & \text{else}. \end{cases}\end{split}\]

For instance, let assume that \(u_{i+1} = u_{i+2}\)! We get the following:

\[\begin{split}N_i^3(u) = \begin{cases} \dfrac{(u - u_i)^2}{(u_{i+1} - u_i)^2}, & \text{if } u \in [u_i, u_{i+1}), \\ \dfrac{(u_{i+3} - u)^2}{(u_{i+3} - u_{i+1})^2}, & \text{if } u \in [u_{i+1}, u_{i+3}), \\ 0, & \text{else}. \end{cases}\end{split}\]

We can imagine this operation as a translation of \(u_{i+1}\) to the point \(u_{i+2}\). The base function remains continuous at that point, however it will not remain differentiable at that point.

We can define the coincide of consecutive knot values as the multiplicity of the knots.

The multiplicity of a knot value is \(m\), when there are \(m\) same consecutive knot values.

\[u_{i-1} < u_i = u_{i+1} = \cdots = u_{i+m-1} < u_{i+m}.\]

4.1.5. Relation with the Bernstein polynomials

In the case of

\[u_0, u_1 = u_2 = \ldots = u_{k-1}, u_k = u_{k+1} = \ldots = u_{2k-2} = 1, u_{2k-1}\]

then

\[N_i^{k-j}(u) = B_{i-j}^{k-1-j}(u), \forall u \in [u_{k-1}, u_k], i = 0, 1, \ldots, k - 1, j = 0, 1, \ldots, i.\]

4.1.7. Derivative

The derivative of the normalized B-spline base function \(N_i^k(u)\):

\[\dfrac{\mathrm{d}}{\mathrm{d}u} N_i^k(u) = (k - 1) \left( \dfrac{1}{u_{i+k-1}-u_i}N_i^{k-1}(u) - \dfrac{1}{u_{i+k} - u_{i+1}}N_{i+1}^{k-1}(u) \right),\]

where \([u_i, u_{i+k})\).

4.1.8. Linear independence

Normalized B-spline functions \(\{N_j^k\}_{j=i-k+1}^i\) are linearly independent on the interval \([u_i, u_{i+1})\), if \(u_i < u_{i+1}\).

4.2. B-spline curve

Let given the control points \(\textbf{d}_0, \textbf{d}_1, \ldots, \textbf{d}_n\) and the \(\{u_j\}_{j=0}^{n+k}\) knot values! We call the curve

\[\textbf{s}(u) = \sum_{i=0}^n N_i^k(u) \textbf{d}_i, u \in [u_{k-1}, u_{n+1}], 1 < k < n + 1\]

the order of \(k\) (in other words the degree \((k-1)\)) B-spline curve.

  • The points \(\textbf{d}_i\) are the control points (or de Boor points).

  • The \(N_i^k\) denotes the normalized B-spline polynomial of degree \((k-1)\).

The B-spline curve is an approximative curve in general. There can be for example the following cases:

  • When \(k = 2\), it results the control polygon.

  • It passes the control points when the control points are colinear.

  • When the multiplicity at the endpoints is \(k\), then it interpolates at the given point.

Note

It is easy to see the last one. Let assume, that \(u_1 = u_2 = \cdots = u_{k-1}\)! We can call the point of the curve at the parameter \(u_{k-1}\) as

\[\textbf{s}(u_{k-1}) = \sum_{i=0}^{k-1} N_i^k(u_{k-1}) \textbf{d}_i.\]

We know that \(N_i^k(u_{k-1}) = 0\), when \(i \in [1, k-2]\). By using the theorem \(N_0^k(u_{k-1}) = 1\), we obtain that

\[\textbf{s}(u_{k-1}) = \textbf{d}_0.\]

Similarly, we can conclude that the curve also will interpolate at the point \(\textbf{d}_n\) for the proper multiplicity.

4.2.1. Properties of the curve

Local modification: The B-spline curve is locally modifiable. It means that, the modification of the control points only affects a well defined part of the curve.

Convex hull property: Any arc of the B-spline curve of degree \((k - 1)\) is within the convex hull of \(k\) number of consecutive control points.

4.2.2. de Boor algorithm

The de Boor algorithm is based on a recursive method similarly to the de Casteljau algorithm, which makes possible to calculate the point of the curve at parameter \(u\). It is a numerically stable algorithm.

Let introduce the following notations:

\[\begin{split}\alpha_j^l(u) = \begin{cases} 1, & \text{if } l = 0, \\ \dfrac{u - u_j}{u_{j+k-l} - u_j}, & \text{if } l > 0, \end{cases}\end{split}\]
\[\begin{split}\textbf{d}_j^l(u) = \begin{cases} \textbf{d}_j, & \text{if } l = 0, \\ \alpha_j^l(u)\textbf{d}_j^{l-1}(u) + (1 - \alpha_j^l(u)) \textbf{d}_{j-1}^{l-1}(u), & \text{if } l > 0, \end{cases}\end{split}\]

where

\[l = 0, 1, \ldots, k - 1, j = i - k + 1 + l, \ldots, i.\]

The value \(l\) at the top right corner denotes the iteration number. We calculate the subdivision points based on \(\alpha\) ratios.

In the steps \(l < (k - 1)\):

\[\textbf{s}(u) = \sum_{j=i-k+l+1}^i \textbf{d}_j^l(u) N_j^{k-l}(u),\]

when \(l = (k - 1)\):

\[\textbf{s}(u) = \textbf{d}_i^{k-1},\]

because

\[\begin{split}N_i^1(u) = \begin{cases} 1, & \text{if } u \in [u_i, u_{i+1}), \\ 0, & \text{else}. \end{cases}\end{split}\]

The algorithm is similar to the de Casteljau algorithm, however there are some key differences.

  • We do not apply subdivision in the ratio \(u:(1-u)\).

  • The calculation of a point does not make necessary to use all of the control points. (It is the reason of the locally modifiable property.)

  • We cannot use the algorithm for splitting the curve.

See also

4.2.3. Derivative of the curve

The derivative of the B-spline curve when \(u \in [u_i, u_{i+1})\):

\[\dfrac{\mathrm{d}}{\mathrm{d}u} \textbf{s}(u) = (k - 1)\sum_{j=i-k+2}^i \dfrac{\textbf{d}_j - \textbf{d}_{j-1}}{u_{j+k-1} - u_j} N_j^{k-1}(u).\]

It means that, the hodograph of a B-spline curve of degree \((k - 1)\) is also a B-spline curve of degree \((k - 2)\).

We can express the derivative based on the subdivision points of the de Boor algorithm:

\[\dfrac{k-1}{u_{i+1} - u_i} (\textbf{d}_i^{k-2}(u) - \textbf{d}_{i-1}^{k-2}(u)).\]

4.3. Theoretical questions

  • How can we define the normalized B-spline base function?

  • Let write the theorem of local support in the case of normalized B-spline base function!

  • Let write the theorem of non-negativity in the case of normalized B-spline base function!

  • Let write the theorem of partition of unity in the case of normalized B-spline base function!

  • Let define the B-spline curve!

  • What are the properties of the B-spline curves?

4.4. Programming exercises

4.4.1. Visualization and analysis of the curve

  • Let implement an application which is able to visualize a B-spline curve for 8 control points!

  • Let make possible to set the degree of the curve!

  • Let highlight the modifiable part of the curve while the user move a control point!

  • Let make possible to set the multiplicity of the points!

  • Let highlight the corresponding curve segments and their theoretical convex hulls (for example by toggling the segments of the curve)!

  • Let implement the de Boor algorithm!

  • Let calculate and visualize the tangent and normal vector at the given point of the curve!

4.4.2. Available implementations

Let check the available implementations of the B-spline curves, for instance:

4.5. Further exercises

  • Let implement the interpolation by using B-spline curves!

  • Let approximate the set of points by using B-spline curve of degree \(k\)! (We assume a large number of sample points, which means that we cannot use them as control points.)

  • Let examine and compare the algorithms (in the assumption of the same graphic quality) from the aspect of the number of required line segments!

  • Let determine the self-intersection points of a B-spline curve!

  • Let approximate the area of a closed B-spline curve!

  • Let develope an algorithm which able to approximate a larger degree B-spline curve with a lower degree one! Let examine the accuracy!