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].

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.

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.

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})$$.

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.

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.

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.

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 points $$\vec{c_k} \in \mathbb{R}^d$$ are called control points. 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.

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.