B-splines

This is an edited section from my thesis “Solving Poisson’s equation with Dataflow computing”. It might be a bit more formal than most of my other posts.

Splines are a mathematical concept which can be used to define smooth (or less smooth) curves and surfaces.

In this article, I’ll cover some mathematical background.

Introduction to splines

Splines (or spline functions) are also called piecewise polynomial. The reason is illustrated by the following definition:

Definition: A spline or piecewise polynomial function of degree is a function , such that there exist and polynomials , , …, with degree at most such that if , and either or when . The values , , …, are called breaks.

In order to define spline spaces, we introduce the concept of a knot vector:

Definition: A knot vector is a non-decreasing vector . The values , , …, are called knots, and the number of times that a knot occurs in the knot vector is called the multiplicity of the knot.

We can now define a space of splines, where the continuity along the breaks is defined by the multiplicities of the knots:

Definition: The spline space of degree for a knot vector is defined as the space of splines of order , with breaks , , …, and support on a subset of . Furthermore, we require that is -continuous on , for , , …, .

To ensure that is well-defined and continuous, we demand that is a knot vector of degree .

Definition: A knot vector is called a knot vector of degree if all knots have a multiplicity of at most .

It should be noted that the requirement that is continuous implies that and . Sometimes, this is not desirable. To remove this restriction, the concept of an open knot vector of degree is introduced:

Definition: A knot vector is called an open knot vector of degree when the first and last knot have multiplicity , and all other knots have a multiplicity of at most .

It should be noted that, according to these definitions, an open knot vector of degree is not a knot vector of degree . We will work with knot vectors with uniformly distributed knots on the interval .

Definition: A knot vector is called a uniform knot vector when for all and some constant . A knot vector of the same form is called a uniform open knot vector of degree when and have multiplicity , and for and some constant .

B-splines

The term ‘B-spline’ is an abbreviation for ‘basis spline’. B-splines were introduced as basis functions for the spline space. However, the CAD community has adopted the term to refer to splines which are represented in terms of these basis functions. This has caught on, and it has become common to call the basis functions ‘B-spline basis functions’. This is the terminology that will be used in this document as well.

The recursive definition that is commonly used to introduce B-splines was presented in [2] by de Boor.

Definition: For , a -dimensional B-spline curve is defined as a linear combination of B-spline basis functions :

The image is a one-dimensional subset of . It is common to identify with this subset and refer to both as a B-spline curve. The coefficients are called control points, and the B-spline basis functions are defined by the Cox-de-Boor recursion formula. The following version is from [3]:

where

is called the polynomial degree, and is a knot vector of degree

The index , denoting the polynomial degree, will often be omitted when its value is irrelevant or clear from the context, so that denotes the same basis function as .

The next image shows the B-spline basis functions associated to the uniform knot vector for polynomials orders :

The following characterization of B-spline basis functions is due to Curry and Schoenberg in [4] and [5]:

Theorem (Curry-Schoenberg): The set of B-spline basis functions associated to the knot vector is a basis for the spline space . Moreover, the B-splines basis functions have minimal support: for any with we have that there exists a basis function with .

For a proof that is a basis of , see [6], chapter 1, theorem 1.8 on page 8, or [4]. For a proof that the B-spline basis functions have minimal support, see [5].

In computer-aided design (CAD), it is convenient to have continuous curves that interpolate the first and last control point. This means that , and if is the last control point. This can be achieved by using an open knot vector to define the B-spline basis functions. The effect of taking the open knot vector of degree 2 is illustrated in the next image.

It can be seen that the first and the last B-spline basis functions and are discontinuous at the first knot , and the last knot , since for , but . Likewise, we have , but for . However, since is only defined on , is still continuous. In practice, we will extend the domain of to by the following convention.

Convention: Unless indicated otherwise, the knot vector used to define B-spline basis functions of degree , is an open knot vector that satisfies , . Moreover, the domain of B-spline curves will be taken as , with the convention

This convention ensures that B-spline curves are continuous mappings from to . In code, this is achieved by including a special check for the last basis function: If the last basis function is evaluated at the last knot of an open knot vector, it should evaluate to one (instead of zero).

Theorem: Suppose that is a (not necessarily open) knot vector of degree . Then the basis functions of order associated to , and the B-spline curve as defined in satisfy the following properties:

  1. , , …,
  2. If the derivative of a B-spline basis function exists at a point , it is given by
  1. The B-spline basis functions satisfy and .
  2. For a B-spline basis function we have . Moreover iff or and is an open knot vector of degree .
  3. , , , and are all zero whenever . It follows that $$\int N_{i, p}(\xi) N_{j, p}(\xi)\ \text{d}\xi = 0 \text{ whenever } | j - i| > p$$
  4. The B-spline basis functions satisfy and , where is the smallest nonzero difference between two consecutive knots.
  5. On any point in the , there are at most nonzero basis functions. More specifically, there are nonzero basis functions on , whenever is not a knot.
  6. If is an open knot vector, interpolates the first and last control points: , .

Proof: A sketch of the proofs is given. The interested reader can try to prove the properties more rigorously, or look at proofs given in [2], [6] or [7]. The first property follows from the Curry-Schoenberg theorem. The second property can be proved by taking the derivative of the recursive definition of the B-spline basis functions. Using the definition of a B-spline basis function, it can be proved by induction on the degree that should be treated differently, since the value is defined by the convention that is introduced). By taking the derivative of both sides, it follows that , and the third property follows. The fourth property follows from the definition of the B-spline basis functions by induction (except for the case , which follows from the convention we use). The fifth property follows from the fourth. The sixth property follows from the second and third property. The seventh property follows from the fourth. For the eighth property, we can prove that for by using the definition of the B-spline basis functions and induction on . Likewise we have by the used convention. From the third property we have , so that it follows that , .

Now, the problem of finding an interpolating B-spline is considered. Suppose that we define a one-dimensional B-spline and we want to choose the control points , , …, such that , , …, . This is called the interpolation problem. We have the following theorem:

Theorem (Whitney-Schoenberg): For basis functions , , …, with which are a subset of the B-spline basis functions , , … associated to a not necessarily open knot vector , and interpolations points , the interpolation matrix is nonsingular if and only if , and $$N_{i_k}(\xi_k) \neq 0 \quad \text{for }$$

See [6], section 3.3, theorem 3.2 on page 19 for a proof.

Given a knot vector, it is not immediately obvious how we can choose interpolation points that satisfy the conditions of the Whitney-Schoenberg theorem. For this purpose, one can define the Greville abscissae:

Definition: For a knot vector of degree , the Greville abscissae are defined as

Theorem: For B-spline basis functions associated to an open knot vector of degree we have

Proof: Suppose that . Then we have . So, the knot has multiplicity .

If , we have that the multiplicity of is at most . So, we can’t have or and both inequalities are strict, so we have . By property 4, it follows that .

If , then is the first knot, and has multiplicity , so it follows that . So it follows that , and we have by property 4.

This means that the Greville abscissae are suitable as a standard choice for interpolation points for B-splines.

References

[1] C. De Boor. Splines as Linear Combinations of B-splines. A Survey.

[2] Carl de Boor. On calculating with B-splines.

[3] Carl de Boor. B(asic)-Spline Basics.

[4] H. B. Curry and Schoenberg I. J. On spline distributions and their limits: The Pólya distribution functions.

[5] H. B. Curry and Schoenberg I. J. On Pólya frequency functions IV: The fundamental spline functions and their limits.

[6] Tomas Sauer. Splines in Industrial Applications.

[7] Les Piegl and Wayne Tiller. The NURBS Book.