B-spline

In the mathematical subfield of numerical analysis, a B-spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. B-splines were investigated as early as the nineteenth century by Nikolai Lobachevsky. A fundamental theorem states that every spline function of a given degree, smoothness, and domain partition, can be uniquely represented as a linear combination of B-splines of that same degree and smoothness, and over that same partition.^[1]

The term "B-spline" was coined by Isaac Jacob Schoenberg and is short for basis spline.^[2]^[3] B-splines can be evaluated in a numerically stable way by the de Boor algorithm. Simplified, potentially faster variants of the de Boor algorithm have been created but they suffer from comparatively lower stability.^[4]^[5]

In the computer science subfields of computer-aided design and computer graphics, the term B-spline frequently refers to a spline curve parametrized by spline functions that are expressed as linear combinations of B-splines (in the mathematical sense above). A B-spline is simply a generalisation of a Bézier curve, and it can avoid the Runge phenomenon without increasing the degree of the B-spline.

1 Definition
- 1.1 Uniform B-spline
- 1.2 Cardinal B-spline
2 Notes
3 Examples
4 See also
5 References
6 External links

Definition

Given m real values t_i, called knots, with

$t_0 \le t_1 \le \cdots \le t_{m-1}$

a B-spline of degree n is a parametric curve

$\mathbf{S}:[t_{n}, t_{m-n-1}] \to \mathbb{R}^d$

composed of a linear combination of basis B-splines b_i,n of degree n

$\mathbf{S}(t)= \sum_{i=0}^{m-n-2} \mathbf{P}_{i} b_{i,n}(t) \mbox{ , } t \in [t_{n},t_{m-n-1}]$ .

The points $\mathbf{P}_{i} \in \mathbb{R}^d$ are called control points or de Boor points. There are m−n-1 control points, and they form a convex hull.

The m-n-1 basis B-splines of degree n can be defined, for n=0,1,...,m-2, using the Cox-de Boor recursion formula

$b_{j,0}(t)�:= \left\{ \begin{matrix} 1 & \mathrm{if} \quad t_j \leq t < t_{j%2B1} \\ 0 & \mathrm{otherwise} \end{matrix} \right.,\qquad j=0,\ldots, m{-}2$

$b_{j,n}(t)�:= \frac{t - t_j}{t_{j%2Bn} - t_j} b_{j,n-1}(t) %2B \frac{t_{j%2Bn%2B1} - t}{t_{j%2Bn%2B1} - t_{j%2B1}} b_{j%2B1,n-1}(t) ,\qquad j=0,\ldots, m{-}n{-}2.$

Note that j+n+1 can not exceed m-1, which limits both j and n.

When the knots are equidistant the B-spline is said to be uniform, otherwise non-uniform. If two knots t_j are identical, any resulting indeterminate forms 0/0 are deemed to be 0.

Note that when one sums a run of adjacent n-degree basis B-splines one obtains, from this recursion

$\sum_{j=j'}^{j''} b_{j,n}(t) = \frac{t - t_{j'}}{t_{j'%2Bn} - t_{j'}} b_{j',n-1}(t) \quad %2B \sum_{j=j'{%2B}1}^{j''} b_{j,n{-}1}(t) \quad %2B \; \frac{t_{j''%2Bn%2B1} - t}{t_{j''%2Bn%2B1} - t_{j''%2B1}} b_{j''%2B1,n-1}(t)$

for any sum with $0\le j' < j''\le m{-}n{-}2.$

When $j''\ge j'%2Bn-1$ here, then this sum is, by this recursion, identically equal to 1, within the limited subrange $t_{j'{%2B}n} \le t \le t_{j''{%2B}1}$ , (since this interval excludes the supports of the two basis B-splines in the separate terms at the ends of this sum).

Uniform B-spline

When the B-spline is uniform, the basis B-splines for a given degree n are just shifted copies of each other. An alternative non-recursive definition for the m−n-1 basis B-splines is

$b_{j,n}(t) = b_n(t - t_j), \qquad\; j = 0, \ldots, m-n-2$

with

$b_{n}(t)�:= \frac{n%2B1}{n} \sum_{i=0}^{n%2B1} \omega_{i,n}(t - t_i)_%2B^{n} \,\;$

and

$\omega_{i,n}�:= \prod_{j=0, j \neq i}^{n%2B1} \frac{1}{t_j - t_i} \,\;$

where

$(t - t_i)_%2B^n�:= \left\{\begin{matrix} (t - t_i)^n &\mbox{if}\ t \ge t_i \\ 0 &\mbox{if}\ t < t_i \end{matrix}\right.$

is the truncated power function.

Cardinal B-spline

Define B₀ as the characteristic function of $[-\tfrac{1}{2}, \tfrac{1}{2}]$ , and B_k recursively as the convolution product

$B_k�:= B_{k-1} * B_0, ~k =1, 2, \dots$

then B_k are called (centered) cardinal B-splines. This definition goes back to Schoenberg.

B_k has compact support $[-\tfrac{k%2B1}{2}, \tfrac{k%2B1}{2}]$ and is an even function. As $k \rightarrow \infty$ the normalized cardinal B-splines tend to the Gaussian function.^[6]

Notes

When the number of de Boor control points is one more than the degree and $t_0 = \ldots = t_n = 0$ and $t_{n%2B1} = \ldots = t_{2n} = 1$ (thus $t \in [0, 1]$ ), the B-Spline degenerates into a Bézier curve. In particular, the B-Spline basis function $b_{i,n}(t)$ coincides with the n-th degree univariate Bernstein polynomial.^[7] The shape of the basis functions is determined by the position of the knots. Scaling or translating the knot vector does not alter the basis functions.

The spline is contained in the convex hull of its control points.

A basis B-spline of degree n

$b_{i,n}(t)\,\;$

is non-zero only in the interval [t_i, t_i+n+1] that is

$b_{i,n}(t) = \left\{\begin{matrix} >0 & \mathrm{if} \quad t_{i} \le t < t_{i%2Bn%2B1} \\ 0 & \mathrm{otherwise} \end{matrix} \right.$

In other words if we manipulate one control point we only change the local behaviour of the curve and not the global behaviour as with Bézier curves.

Also see Bernstein polynomial for further details.

Examples

Constant B-spline

The constant B-spline is the simplest spline. It is defined on only one knot span and is not even continuous on the knots. It is just the indicator function for the different knot spans.

$b_{j,0}(t) = 1_{[t_j,t_{j%2B1}]} = \left\{\begin{matrix} 1 & \mathrm{if} \quad t_j \le t < t_{j%2B1} \\ 0 & \mathrm{otherwise} \end{matrix} \right.$

Linear B-spline

The linear B-spline is defined on two consecutive knot spans and is continuous on the knots, but not differentiable.

$b_{j,1}(t) = \left\{\begin{matrix} \frac{t - t_j}{t_{j%2B1} - t_j} & \mathrm{if} \quad t_j \le t < t_{j%2B1} \\ \frac{t_{j%2B2} - t}{t_{j%2B2} - t_{j%2B1}} & \mathrm{if} \quad t_{j%2B1} \le t < t_{j%2B2} \\ 0 & \mathrm{otherwise} \end{matrix} \right.$

Uniform quadratic B-spline

Quadratic B-splines with uniform knot-vector is a commonly used form of B-spline. The blending function can easily be precalculated, and is equal for each segment in this case.

$b_{j,2}(t) = \begin{cases} \frac{1}{2}(t-t_j)^2 & t_j\le t \le t_{j%2B1} \\ -(t-t_{j%2B1})^2 %2B (t-t_{j%2B1}) %2B \frac{1}{2} & t_{j%2B1} \le t \le t_{j%2B2}\\ \frac{1}{2}(1-(t-t_{j%2B2}))^2 & t_{j%2B2} \le t \le t_{j%2B3}\\ 0 & \mbox{otherwise} \end{cases}$

Put in matrix-form, it is:^[8]

$\mathbf{S}_i(t) = \begin{bmatrix} t^2 & t & 1 \end{bmatrix} \frac{1}{2} \begin{bmatrix} 1 & -2 & 1 \\ -2 & 2 & 0 \\ 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_{i-1} \\ \mathbf{p}_{i} \\ \mathbf{p}_{i%2B1} \end{bmatrix}$ for $t \in [0,1], i = 1,2 \ldots m-2$

Cubic B-Spline

A B-spline formulation for a single segment can be written as:

$\mathbf{S}_{i} (t) = \sum_{k=0}^3 \mathbf{P}_{i-3%2Bk} b_{i-3%2Bk,3} (t) \mbox{�; }\ t \in [0,1]$

where S_i is the ith B-spline segment and P is the set of control points, segment i and k is the local control point index. A set of control points would be $P_i^w = ( w_i x_i, w_i y_i, w_i z_i, w_i)$ where the $w_i$ is weight, pulling the curve towards control point $P_i$ as it increases or moving the curve away as it decreases.

An entire set of segments, m-2 curves ( $S_3,S_4,...,S_m$ ) defined by m+1 control points ( $P_0,P_1,...,P_m, m \ge 3$ ), as one B-spline in t would be defined as:

$\mathbf{S}(t) = \sum_{i=0}^{m-1} \mathbf{P}_{i} b_{i,3} (t)$

where i is the control point number and t is a global parameter giving knot values. This formulation expresses a B-spline curve as a linear combination of B-spline basis functions, hence the name.

There are two types of B-spline - uniform and non-uniform. A non-uniform B-spline is a curve where the intervals between successive control points are not necessarily equal (the knot vector of interior knot spans are not equal). A common form is where intervals are successively reduced to zero, interpolating control points.

Uniform cubic B-splines

Cubic B-splines with uniform knot-vector is the most commonly used form of B-spline. The blending function can easily be precalculated, and is equal for each segment in this case. Put in matrix-form, it is:

$\mathbf{S}_i(t) = \begin{bmatrix} t^3 & t^2 & t & 1 \end{bmatrix} \frac{1}{6} \begin{bmatrix} -1 & 3 & -3 & 1 \\ 3 & -6 & 3 & 0 \\ -3 & 0 & 3 & 0 \\ 1 & 4 & 1 & 0 \end{bmatrix} \begin{bmatrix} \mathbf{p}_{i-1} \\ \mathbf{p}_{i} \\ \mathbf{p}_{i%2B1} \\ \mathbf{p}_{i%2B2} \end{bmatrix}$

for $t \in [0,1].$

References

^ Carl de Boor (1978). A Practical Guide to Splines. Springer-Verlag. pp. 113–114.
^ Carl de Boor (1978). A Practical Guide to Splines. Springer-Verlag. pp. 114–115.
^ Gary D. Knott (2000), Interpolating cubic splines. Springer. p. 151
^ Lee, E. T. Y. (December 1982). "A Simplified B-Spline Computation Routine". Computing (Springer-Verlag) 29 (4): 365–371. doi:10.1007/BF02246763.
^ Lee, E. T. Y. (1986). "Comments on some B-spline algorithms". Computing (Springer-Verlag) 36 (3): 229–238. doi:10.1007/BF02240069.
^ Brinks R: On the convergence of derivatives of B-splines to derivatives of the Gaussian function, Comp. Appl. Math., 27, 1, 2008
^ Prautzsch et al., Hartmut (2002). Bezier and B-Spline Techniques. Springer-Verlag. pp. 60–66. ISBN 3540437614.
^ Splitting a uniform B-spline curve