B-spline

In the mathematical subfield of numerical analysis a B-spline is a special spline curve. It is a linear combination of B-splines basis curves. B-splines are a generalization of the Bézier curves and can be further generalized to NURBS, allowing the accurate modelling of more general classes of geometry.

The De Boor algorithm is a numerical stable way to evalute B-splines.

The term B-spline was coined by Isaac Jacob Schoenberg and is short for basis spline.

Definition

Given m+1 knots t_i in [0,1] with

$t_{0}<t_{1}<\ldots <t_{m}$

a B-spline of degree n is a parametric curve

$\mathbf {S} :[0,1]\to \mathbb {R} ^{2}$

composed of basis B-splines of degree n

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

The P_i are called control points or de Boor points. A polygon can be constructed by connecting the de Boor points with lines, starting with P₀ and finishing with P_n. This polygon is called the de Boor polygon.

The m+1 basis B-splines of degree n can be defined using the Cox-de Boor recursion formula

$b_{j,0}(t):=\left\{{\begin{matrix}1&\mathrm {if} \quad t_{j}<t<t_{j+1}\\0&\mathrm {otherwise} \end{matrix}}\right.$

$b_{j,n}(t):={\frac {t-t_{j}}{t_{j+n}-t_{j}}}b_{j,n-1}(t)+{\frac {t_{j+n+1}-t}{t_{j+n+1}-t_{j+1}}}b_{j+1,n-1}(t)$

When the knots are equidistant we say the B-spline is uniform otherwise we call it non-uniform.

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+1 basis B-splines is

$b_{j,n}(t):=b_{n}(t+n-j)\qquad {\mbox{ , }}j=-1,\ldots m+1$

with

$b_{n}(t):=(m+1)\sum _{i=0}^{m+1}\omega _{i}(t_{i}-t)_{+}^{m}\qquad {\mbox{ , }}t\in [0,1]$

with

$\omega _{i}:=\prod _{j=0,i\neq j}^{m+1}{\frac {1}{t_{i}-t_{k}}}$

where

$(t_{i}-t)_{+}$

is the truncated power function

Notes

When the number of knots is the same as the degree, the B-Spline degenerates into a Bezier curve. 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}<=t<t_{i+n+1}\\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.

Examples

Constant B-spline

The constant B-spline is the most simple spline.

$b_{j,0}(t)=\left\{{\begin{matrix}1&\mathrm {if} \quad t_{j}<t<t_{j+1}\\0&\mathrm {otherwise} \end{matrix}}\right.$

Cubic B-Spline

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

$Q_{i}(u)=\sum _{k=0}^{3}P_{i-3+k}B_{i-3+k}(u)$

where $Q_{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. The value of u is $0\leq u\leq 1$ as a local parameter to define a single curve segment. 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 ($Q_{3},Q_{4},...,Q_{m}$) defined by m+1 control points ($P_{0},P_{1},...,P_{m},m\geq 3$), as one B-spline in u would be defined as:

$Q(u)=\sum _{i=0}^{m}P_{i}B_{i}(u)$

where i is the control point number and u 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 is not, or 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.

See also

• Spline (mathematics)
• Parametric patch
• Beta-spline (Beta spline)
• Curve interpolation
• De Boor algorithm

References

This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

External links

• Interactive java applets for B-splines