Flavors and Types of B-Splines

There are various flavors and types of B-splines. This page tries to give an overview of them. More details can be looked up in the referenced literature.


Cardinal B-Splines

Cardinal B-splines can be defined in various equivalent ways, possibly the shortest and most beautiful way being $$b^p := \underbrace{\mathbf{1}_{[0,1)} \ast \cdots \ast \mathbf{1}_{[0,1)}}_{\text{$(p+1)$ times}}$$ with the degree \(p \in \mathbb{N}_0\), the convolution operator \(\ast\), and the indicator function \(b^0 = \mathbf{1}_{[0,1)}\) of the half-open unit interval \([0,1)\).

However, there are numerous other ways to characterize the B-spline \(b^p\), at least for the most common cubic case \(p = 3\) [Quak 2016].

Cardinal B-splines.
Cardinal B-splines.

The figure shows that \(p\) controls the smoothness of \(b^p\) (in fact, \(b^p \in \mathcal{C}^{p-1}(\mathbb{R})\)), but also the size of its support. With the Central Limit Theorem, it can be shown that for \(p \to \infty\), the centralized B-spline \(b^p(\cdot \,- \frac{p+1}{2})\) converges in distribution to the density function of the standard normal distribution (Gaussian bell curve), which is infinitely smooth and globally supported.

The B-spline \(b^p\) is a polynomial of degree \(p\) on the knot intervals \([k, k+1)\), \(k = 0, \dotsc, p\), and vanishes elsewhere. The places \(k = 0, \dotsc, p + 1\) where \(b^p\) is only \((p – 1)\) times continuously differentiable are called knots.

The name “cardinal” is used differently in the literature; here, we refer to B-splines whose knots are a subset of \(\mathbb{Z}\).


Uniform B-Splines

Uniform B-splines arise from cardinal B-splines by shifting and scaling the knots linearly: $$b_{k,h}^p := b^p\!\left(\frac{\cdot}{h} – k\right).$$

By linearly combining multiple B-splines \(b_{k,h}^p\), \(k = \underline{k}, \dotsc, \overline{k}\) (\(\underline{k} \le \overline{k} – p + 1\)), one obtains arbitrary splines (piecewise polynomials). In fact, these B-splines form a basis of the spline space with degree \(p\) and knots \(\{kh \mid k = \underline{k} + p, \dotsc, \overline{k} + 1\}\). This is the subspace of \(\mathcal{C}^{p-1}([\underline{k} + p, \overline{k} + 1])\) that contains the functions \(s\) which are, with respect to this knot set, piecewise polynomials of degree \(\le p\).

This also answers the question to what the “B” in “B-splines” is for: basis.

Uniform cubic B-splines forming a cubic spline.
Uniform cubic B-splines forming a cubic spline.

The figure illustrates the cubic case \(p = 3\). In the figure, we use already the notation \(\xi_k := kh\) to prepare for the non-uniform case (see next section, set \(\underline{k} := 0\) and \(\overline{k} := m – 1\) to establish consistency).


Non-Uniform B-Splines

The definition of B-splines can be generalized to arbitrary knot vectors \(\vec{\xi} = (\xi_0, \dotsc, \xi_{m+p})\) where \(m \ge p\), \(\xi_k \le \xi_{k+1}\) for all \(k = 0, \dotsc, m+p-1\), and the multiplicity \(\nu_k\) of every knot \(\xi_k\) should be \(\le p\).

This results in non-uniform B-splines defined via the Cox–de Boor recurrence relation $$b_{k,\vec{\xi}}^p := \gamma_{k,\vec{\xi}}^p b_{k,\vec{\xi}}^{p-1} + (1-\gamma_{k+1,\vec{\xi}}^p) b_{k+1,\vec{\xi}}^{p-1},\\\gamma_{k,\vec{\xi}}^p := \frac{\cdot \,- \xi_k}{\xi_{k+p} – \xi_k},$$ starting from the indicator functions \(b_{k,\vec{\xi}}^0 := \mathbf{1}_{[\xi_k, \xi_{k+1})}\) and discarding terms for which the denominators vanish [Cox 1972, de Boor 1972].

Cox–de Boor recursion formula for creating a quadratic B-spline. The dashed lines show the combination coefficients.
Cox–de Boor recursion formula for creating a quadratic B-spline. The dashed lines show the combination coefficients.

The B-splines \(b_{k,\vec{\xi}}^p\), \(k = 0, \dotsc, m\), form a basis of the spline space with degree \(p\) and knots \(\vec{\xi}\). This is the space of all functions on \([\xi_p, \dotsc, \xi_m]\) which are polynomials of degree \(\le p\) on all knot intervals \([\xi_k, \xi_{k+1})\), \(k = p, \dotsc, m – 1\), and \((p – \nu_k)\) times continuously differentiable at all knots \(k = p + 1, \dotsc, m – 1\).


Tensor Product B-Splines

All of the previous definitions treated only the univariate case. A straightforward generalization to multiple variables is using cartesian and tensor products. For example, 1D non-uniform B-splines can be generalized to tensor product B-splines via $$b_{\vec{k},\Xi}^{\vec{p}}(\vec{x}) := \prod_{t=1}^d b_{k_t,\vec{\xi_t}}^{p_t}(x_t),$$ where \(\Xi = (\vec{\xi_1}, \dotsc, \vec{\xi_d})\) contains the 1D knot vectors \(\vec{\xi_t} = (\xi_{t,0}, \dotsc, \xi_{t,m_t+p_t})\).

Two-dimensional cubic tensor product B-spline.
Two-dimensional cubic tensor product B-spline.

Hierarchical B-Splines with Knot Trees

Adaptive refinement can be easily done with B-splines by just adding knots in regions where higher accuracy is desired. However, directly using tensor product B-splines leads to problems as their construction implies that modifying the knot vectors has global effect.

One approach is arranging the knot vectors in a tree-like structure. When refining in a region, the relevant B-splines (i.e., the B-splines that do not vanish in that region) are replaced by B-splines on a knot vector with a finer resolution. Correspondingly, this knot vector is inserted into the tree as a new leaf [Höllig 2013].

Left: Hierarchical refinement of linear 1D B-splines. The dashed B-splines are replaced by the finer B-splines below them. Right: Nested refinement grids in 2D.
Left: Hierarchical refinement of linear 1D B-splines. The dashed B-splines are replaced by the finer B-splines below them. Right: Nested refinement grids in 2D.

Hierarchical B-Splines on Sparse Grids

Another approach to construct a hierarchical B-spline basis are sparse grids. Here, uniform B-splines are arranged in a binary tree by halving the scaling parameter \(h = 2^{-\ell}\) in every level \(\ell \in \mathbb{N}_0\).

Left: Hierarchical cubic B-spline basis. Right: Regular sparse grid of level 5 in 2D.
Left: Hierarchical cubic B-spline basis. Right: Regular sparse grid of level 5 in 2D.

Like knot tree approach, it can be shown that the resulting basis functions form the basis of a spline space, depending on the boundary conditions chosen [Valentin 2016].

The method can be generalized to non-uniform sparse grids, for example using Clenshaw-Curtis (Chebychev) points, to increase accuracy near the boundary of the domain.


WEB-Splines

The obvious limitation of tensor product approaches is that the domain is rectangular. For example, the goal might be to solve a partial differential equation (PDE) on some domain \(\Omega \subset \mathbb{R}^d\) with Dirichlet zero boundary conditions.

In this case, one can work around this issue by multiplying all B-splines with a weight function \(w\) which should be positive in the domain, negative outside of the domain, and vanish on its boundary \(\partial \Omega\).

However, the resulting weighted B-splines have stability issues as there are B-splines whose supports have a very small intersection with \(\Omega\). As a solution, these outer B-splines can be adjoined to inner B-splines, creating weighted extended B-splines (WEB-splines) in the process, a much more stable basis [Höllig 2003, www.web-spline.de].

Left: Weight function for a B-shaped domain. Right: Classification of cubic B-splines in inner and outer B-splines.
Left: Weight function for a B-shaped domain. Right: Classification of cubic B-splines in inner and outer B-splines.

The figure shows the classification of cubic B-splines on a uniform grid in inner (blue) and outer (red) B-splines. Each B-spline is associated with a dot in the lower left corner of its support. The support of an inner B-spline has to contain at least one cell that is a subset of the domain \(\Omega\).


B-Spline Curves, Surfaces, and Solids

All of the previous definitions resulted in only scalar-valued splines whose curves are described by functions \(s\colon \mathbb{R}^d \supset D \to \mathbb{R}\), \(\vec{x} \to s(\vec{x})\).

A very important application for B-splines is geometric modeling. Spline curves of degree \(p\) in \(d\) dimensions are linear combinations with vector-valued coefficients, parametrized by a single parameter \(t\): $$\vec{s} \colon \mathbb{R} \supset D \to \mathbb{R}^d,\\t \mapsto (s_1(t), \dotsc, s_d(t)) = \sum_{k=0}^{m-1} \vec{c_k} b_{k,\xi}^p(t).$$ In this context, the knots \(\vec{c_k} \in \mathbb{R}^d\) are called control points.

Quadratic B-spline curve in two dimensions with control polygon and knot vector.
Quadratic B-spline curve in two dimensions with control polygon and knot vector.

The figure illustrates a B-spline curve for \(d = 2\) and \(p = 2\). The control points (red) and the knot vector (bottom) are calculated such that the curve interpolates the given interpolation points (blue). By repeating the first and the last knot \((p+1)\) times respectively, the first and last control point coincides with the respective interpolation points.

Analogously, spline surfaces are defined by using two parameters \(t_1, t_2\) and bivariate splines, i.e.,

$$\vec{s} \colon \mathbb{R^2} \supset D \to \mathbb{R}^d,\\\vec{t} \mapsto (s_1(\vec{t}), \dotsc, s_d(\vec{t})) = \sum_{k_1=0}^{m_1-1} \sum_{k_2=0}^{m_2-1} \vec{c_k} b_{\vec{k},\Xi}^{\vec{p}}(\vec{t}).$$

Of course, the approach can be generalized to an arbitrary number of parameters, for example trivariate spline solids [Höllig 2003].


NURBS

As piecewise polynomials, spline curves are not able to reproduce circles exactly. This would limit their use in geometric modeling. As a solution, one can multiply the control points \(\vec{c_k}\) of the spline curve \(\vec{s}(\cdot)\) with weights \(w_k\) and divide the curve by the spline function with coefficients \(w_k\), i.e.,

$$\vec{r}(t) = (r_1(t), \dotsc, r_d(t)) = \frac{\sum_{k=0}^{m-1} w_k \vec{c_k} b_{k,\xi}^p(t)}{\sum_{k=0}^{m-1} w_k b_{k,\xi}^p(t)}.$$

The resulting functions are well-known as non-uniform rational B-spline (NURBS) curves and surfaces [Höllig 2003].

Quadratic NURBS exactly representing the quarter circle, in contrast to a non-rational quadratic B-spline curve.
Quadratic NURBS exactly representing the quarter circle, in contrast to a non-rational quadratic B-spline curve.

The figure shows the exact representation of the quarter circle by a quadratic NURBS (blue) in Bézier form (i.e., \(0 = \xi_0 = \dotsb = \xi_p\), \(\xi_m = \dotsb = \xi_{m+p} = 1\), \(m = p+1\)) with weights \(w_0 = \sqrt{2} w_1 = w_2\). Not dividing by the spline in the denominator and using the same control points (or any other set of control points) yields a non-rational quadratic B-spline curve (red) which deviates from the quarter circle.

By joining multiple NURBS patches together, one has great design flexibility. Consequently, NURBS are nowadays common in modeling and simulation.