CHAPTER 4: B-SPLINE CURVES

1  Introduction

In the previous chapter we discovered a way of avoiding the lack of flexibility of Bézier curves through the use of rational curves.  Even so, the flexibility that the weights of the rational curves provide us is much limited. Instead of covering the whole curve with just one parametrization (polynomial or rational), we could use several of them. Then we achieve more flexibility: when we modify a parametrization, we just modify the corresponding part of the graphic.

First we shall study how to build C¹ piecewise parabolas and C² and C¹ piecewise cubics as a prior step to a more general procedure.

2  C¹ piecewise parabolas

Consider a plane curve formed by N parabolic pieces. We have a collection of vertices {c₀,..., c_2N}, such that {c₀,c₁,c₂} is the control polygon of the first piece, {c₂,c₃,c₄} is the polygon of the second one, {c_2(i-1),c_2i-1,c_2i}, the one for the i-th, and {c_2N-2,c_2N-1,c_2N}, the last one.

Each polygon defines a parametrization over an interval.  The first piece is defined over the interval [u₀,u₁], the second one over [u₁,u₂], the i-th over [u_i-1,u_i] and the last one over [u_N-1,u_N].

If we want the piecewise curve to be C¹ all over the interval [u₀,u_N], we must demand it for each value u = u_i, as seen in the second chapter:

That is: that vectors c_2i-1c_2i y c_2ic_2i+1 are parallel and in proportion Δu_i-1:Δu_i.

The expressions (1) collapse if we allow the user to modify (move) all the vertices. Therefore, if we want the class of differentiability unchanged, all we have to do is to allow the modification (movement) of those vertices which will not affect that condition.

Having this in mind, we can view the definition (1) as the definition of the vertex c_2i, given the vertices c_2i-1, c_2i+1,

These expressions bring back the fact that the simple ratio of the points c_2i-1, c_2i, c_2i+1 is [c_2i-1,c_2i,c_2i+1] = Δu_i-1/Δu_i.

Summing up, the only data that must be given to the user in order to modify freely the curve without changing the smoothness condition are:

• the knots of the partition of the interval {u₀,..., u_N} and 
• the vertices of the control polygons {c₀,c₁,...,c_2i-1,..., c_2N-1,c_2N}, 

Hence: N+2 vertices, corresponding to the fact that we have 2N+1 vertices and N-1 differentiability conditions at the unions. Example

We refer to those vertices as {d₀,...,d_N+1},

This set of vertices is the so-called B-spline control polygon of the piecewise polynomial curve.

The construction of the C¹ class piecewise parabola can be used for interpolating a C¹ class curve that passes through N+1 points of the plane, a₀,...,a_N, for some given values of the parameter u, a_i = c(u_i). We just have to solve a linear system of equations c_2i = a_i,

This is underdetermined: we have N-1 linear equations for N unknowns, the vertices d₁,...,d_N. 

We need another condition besides the values x_i: = (Δu_i-1+Δu_i) a_i. 

We need to fix, for instance, a tangent in one of the pieces.

If the curve is closed, c₀ = c_2N+2, each and every even vertex can be found from the odd adjacent ones due to the relation (2). Hence, it is only necessary to give these ones, {c₁,...,c_2i-1,...,c_2N+1}. 

The initial-final vertex can be found as a particular case:

The B-spline polygon, {d₀,...,d_N}, is formed by the interior vertices , d₀ = c_2N+1, d_i = c_2i-1, i = 1,...,N.

The matrix for this problem is regular for even N. As a consequence, this method enables us to find a unique solution for the interpolation problem for an odd number of points. Hence, it does not seem to be a reliable method. Example

Notice that, as the parabola is a plane conic section, this construction is valid only for plane curves.

3  C² piecewise Cubics

In order to solve the problem in the space, we have to use cubic curves. We try to build a C² class curve of N pieces. The vertices of our control polygons will be {c₀,...,c_3N}, of which {c_3(i-1),c_3i-2,c_3i-1,c_3i} correspond to the i-th piece, defined  over the interval [u_i-1,u_i].

We impose the parametrization to be C² class in u = u_i, union of the pieces i-th and (i+1)-th. As in the previous item, this is the C¹ condition

that is to say: the vectors c_3i-1c_3i y c_3ic_3i+1 are parallel and in proportion Δu_i-1:Δu_i.

Finally, the condition of continuity of the second derivatives (see chapter 2) applied to the knot u_i give us as information that the vectors c_3i-2c_3i-1 and c_3i-1d_i are in ratio Δu_i-1:Δu_i, the same as the vectors d_i c_3i+1 and c_3i+1 c_3i+2.

Applying this condition to the knot u_i+1 we get another relation. The vectors c_3i+1c_3i+2 and c_3i+2d_i+1 are in ratio Δu_i:Δu_i+1. 

And from the knot u_i-1 we learn d_i-1 c_3i-2 and c_3i-2c_3i-1 are in ratio Δu_i-2:Δu_i-1.

Using all this information, we can express the vertices c_3i-1, c_3i+1 in terms of the new points we have introduced,

Combining this result with (7) allows us to find all the vertices of the piecewise curve having as a starting point the points d₁,...,d_N-1, ensuring that the parametrization is  C². 

We left behind the vertices that are not adjacent to any union, i.e., the initial vertices, c₀, c₁, and the final ones, c_3N-1, c_3N, that cannot be found through any of these relations.

We denote d_-1: = c₀, d₀: = c₁, d_N: = c_3N-1, d_N+1: = c_3N, in order to complete the list of vertices. The remaining vertices, c₂, c_3N-2 can be found from (8) taking Δu_-1 and Δu_N equal to zero.

Actually, the usual notation is the correlative one from 0 to N+2. In that case we have to move all the indexes in one unity. We follow this notation from now on.

In the case of closed curves, there is no need to add more points, and all the vertices can be found from (7) y (8).

Consequently, we can encode the piecewise curve in the B-spline control polygon, {d₀,...,d_N+2} and the sequence of knots {u₀,...,u_N}. Thus, the user will be able to modify the curve without changing its properties of differentiability.

Replacing the expressions of the vertices c_3i-1 and c_3i+1 in (7),

Notice that c_3i depends on three consecutive vertices of the B-spline polygon.

This relation is helpful for solving the interpolation problem: given N+1 points a₀,..., a_N and knots  {u₀,...,u_N}, find the C² piecewise cubic such that c(u_i) = a_i. 

The problem can be reduced to the linear system (9), where the data are:

•  c₀ = d₀ = a₀, c_3i = a_i, i = 1,...,N-1, a_N = d_N+2 = c_3N  
• and the unknowns are the vertices of the B-spline polygon {d₀,...,d_N+2}. 

We have, then, N+3 unknowns for N+1 data, so the system has two free parameters (two degrees of freedom), for instance, d₁ y d_N+1. 

It can be proven that the system has rank N+1, and hence the problem has a unique solution (but we have to fix those vertices first).

There are many ways of fixing vertices by imposing conditions on the curve.

One of them, imposing the so-called natural conditions, that mimic the physical behaviour of a real spline, which tends to a straight line near the endings. Therefore:

Notwithstanding, these conditions are not much appreciated in design, because they cause that the curve is too straight at the endpoints.

Another option is choosing the tangent directions at the endpoints, c'(u₀), c'(u_N). These will determine the vertices  d₁, d_N+1,

if we take into account that d₀ = a₀, d_N+2 = a_N,

This will reduce the linear system to N-1 equations for N-1 unknowns.

An alternative way of choosing the tangent directions is given by Bessel conditions: choosing c'(u₀) as the value of the derivative in the origin of the parabola that passes through the points a₀, a₁, a₂ and, analogously, c'(u_N) will be the derivative at u_N of the parabola that interpolates a_N-2, a_N-1, a_N.

The Bessel tangents provide us much better results than natural conditions. Example

In the case of closed curves, no additional data are needed. The system is closed naturally in a periodic way.

Summing up: in order to build curves of degree n of N pieces of C^n-1 class, the Bézier curves give us nN+1 vertices from their control polygons, but we have n-1 conditions of differentiability at the N-1 unions. Hence, we have nN+1-(N-1)(n-1) = N+n degrees of freedom.

4  C¹ piecewise Cubics 

An alternative problem for piecewise cubic interpolation could be:

• Given: Data points c(u_i) and tangent directions at those points
• Find: a C¹ piecewise cubic polynomial that passes through the given data points and is tangent to the given directions there.

Assume that we have N+1 points {a₀,...,a_N} and N+1 vectors {v₀,...,v_N} and we want to trace the interpolating curve c(u) such that c(u_i) = a_i, c'(u_i) = v_i, i = 0,...,N, for an increasing sequence of values of the parameter u, {u₀,...,u_N}.

A simple solution for this problem could be a C¹ piecewise cubic with N pieces. As in the previous example, the curve requires 3N+1 vertices {c₀,...,c_3N}, of which N+1, the endpoints of the cubics, are determined by the conditions c_3i = a_i, i = 0,..., N. The rest of them are determined by the tangent directions.

Having in mind the previous expressions:

respectively for the initial and final points of each piece. From here, we get the interior vertices of each polygon,

Hence, in this case there are no additional degrees of freedom and the curve is clearly determined.

However, in order to encode the information of the curves, it is not necessary to give all the vertices of the curve but only the inner ones, due to the fact that the outer ones can be found from the previous relations, but the initial and final vertices, c₀, c_3N. 

Therefore, the curve can be characterized by a sequence of knots {u₀,..., u_N} and vertices of the  B-spline polygon, {d₀,..., d_2N+1}, given by d₀: = c₀, d_2i-1 = c_3i-2, d_2i = c_3i-1, i = 1,..., N, d_2N+1 = c_3N,

In case we are interpolating with closed curves it is even easier: the expressions (12-13) are still valid even for the cases i = 0,N for Δu_-1: = Δu_N, but we need in addition one more knot, u_N+1, the one who closes the curve with the conditions a₀ = c(u_N+1), v₀ = c'(u_N+1).

5  B-spline Curves 

Consider a parabola parametrized on an interval [u₁,u₂] by c(u). Considering that blossoms are multiaffine, we can express c(u) as another step of the de Casteljau algorithm,

and with another step of the de Casteljau algorithm, but this time using auxiliary knots u₀,u₃,

Consequently, we have expressed every point of c(u) as function of three vertices, c[u₀,u₁], c[u₁,u₂], c[u₂,u₃], which, in general, the curve is not passing through. Example

Notice that, for u₀ = u₁, u₃ = u₂, we recover the de Casteljau algorithm for the control polygon   {c₀ = c[u₁,u₁], c₁ = c[u₁,u₂], c₂ = c[u₂,u₂]}.

Therefore, we have just generalized the de Casteljau algorithm by introducing two auxiliary knots. 

In order to make all the terms positive in the parametrization, we define it over the interval [u₁,u₂]. We have done this for linking different pieces of polynomial curves.

Summing up, the steps of the algorithm are:

The B-spline  polygon for the parabola is formed by the vertices:

{d₀: = c[u₀,u₁],d₁: = c[u₁,u₂],d₂: = c[u₂,u₃]}.

This is the de Boor algorithm for a parabolic curve with just one piece. The algorithm can be generalized to curves of degree n having just one piece. The polygon will be formed by n+1 vertices, corresponding to a polynomial curve of degree n, {d₀,...,d_n}, for d_i = c[u_i,...,u_i+n-1]. 

The sequence of knots will be formed by 2n parameter values {u₀,...,u_2n-1}. Example

Finally, the de Boor algorithm consists on using in a iterated way the de Casteljau algorithm,

For: c(u) = dⁿ⁾₀(u). The parametrization is defined over the interval [u_n-1,u_n]. Example

6  Blossom

The blossom for the de Boor algorithm can be formed easily. For the polygon of a curve of degree n, {d₀,...,d_n}, and a sequence of knots, {u₀,...,u_2n-1}, the blossom can be evaluated at the parameter values v₁,...,v_n ,

The blossom is still symmetric, despite its apparent asymmetry.

The blossom again returns the correct values of the vertices of the control polygon,

By introducing the de Boor algorithm for polynomial curves of just one piece, we have just changed the set of points which we calculated the blossom with. Instead of using {c₀,...,c_n} for the de Casteljau algorithm, we use {d₀,...,d_n} for the de Boor one. But the blossom is still the same.

The blossom gives us a simple mechanism for passing from one scheme to the other. 

For instance, if we have a B-spline polygon of a curve of degree n, {d₀,...,d_n}, the control polygon as a Bézier curve will be

This could seem superfluous but we shall see the importance for curves of several pieces in the next section.

7  The de Boor Algorithm 

The de Boor algorithm can be easily used for curves consisting on N parabolic pieces of degree n. Consider a set of vertices {d₀,...,d_n+N-1} and a sequence of knots {u₀,...,u_2n+N-2}. The first piece of the curve is parametrized over the interval [u_n-1,u_n], in accordance with the algorithm already studied, by the vertices {d₀,..., d_n} and the knots {u₀,...,u_2n-1}. And so on, the polygon of the i-th piece is {d_i-1,..., d_n+i-1}, its knots are {u_i-1,..., u_2n+i-2} and it is defined over the interval[u_n+i-2,u_n+i-1]. Finally the last piece of the curve has for control polygon {d_N-1,...,d_n+N-1}, its knots are {u_N-1,...,u_2n+N-2} and it is defined in [u_n+N-2,u_n+N-1]. Example

Consequently: a curve of N pieces and degree n has n+N vertices and 2n+N-1 knots and is defined over the interval [u_n-1,u_n+N-1]. The n-1 initial and final knots are auxiliary. We shall usually take them respectively equal to the initial knot and to the final knot, u₀ = ... = u_n-1, u_n+N-1 = ... = u_2n+N-2.

Doing this we force the curve to pass through the initial and final vertices, d₀ = c(u_n-1), d_n+N-1 = c(u_n+N-1).

It is simple to see that the repetition of a non-auxiliary knot, for instance u_I = u_I+1, causes the cancellation of the corresponding piece of curve, in this case the (I-n+1)-th, that it has been reduced to a point.

Thus, the question is: how do we use the de Boor algorithm for every and each piece in order to construct the piecewise curve?.

Assume that we want to evaluate the curve in a given value of the parameter u. First, we need to find which interval [u_I,u_I+1) is included in and then apply the de Boor algorithm to the polygon corresponding to that piece, { d'₀: = d_I-n+1,...,d'_n: = d_I+1} and to the knots u'₀: = u_I-n+1,..., u'_2n-1: = u_I+n, as explained in (16).

The extension to piecewise rational curves is automatic, because as it has been seen in the previous chapter, the rational parametrization in  Aⁿ is obtained from the polynomial one in Rⁿ⁺¹, where the additional component corresponds to the denominator of the parametrization. Thus, introducing one new component, we can apply the de Boor algorithm to rational curves dividing by the additional coordinate.

8  Properties of the piecewise polynomial curves

The de Boor algorithm expresses that piecewise polynomial parametrizations are barycentric combinations of B-spline polygon vertices, and therefore they have the same properties of Bézier curves. In the case of rational curves, they are projectively invariant. Other properties, like passing through the initial and final vertices depend on the choice of auxiliary knots. Example

As in the de Boor algorithm only appear quotients of differences of the parameter value u, the parametrization is affine invariance under parameter changes as u' = a u+b, if we transform in the same way the knots , u'_i = a u_i+b, i = 0,..., 2n+N-2.

Moreover, inside each interval spline curves are polynomial curves and they have the properties already described. Thus, inside each piece, for instance the i-th, the curve has the convex hull property of its control polygon, {d_i-1,...,d_i+n-1}. The same happens with the diminishing variation property: a line intersects the i-th curve piece in, at most, as many points as the control polygon of its piece does. Example.

Finally, there are two properties that are substantially improved.

Each piece of the curve depends exclusively of the n+1 vertices of its control polygon.

This means that a generic vertex d_i is present in the control polygons of every piece of curve from the (i-n+1)-th, {d_i-n,...,d_i}, to the (i+1)-th, {d_i,...,d_i+n}. 

Consequently, a displacement of the vertex d_i modifies only n+1 pieces of the curve at most.

This property is called local control and did not exist for the Bézier curves. Example

9  Knot Insertion Algorithm

Closely related to the de Boor algorithm is the Knot Insertion Algorithm. Essentially it is equivalent to the subdivision algorithm studied for the de Casteljau algorithm.

Consider a B-spline control polygon for a curve of degree n of N pieces, {d₀,...,d_n+N-1} and a sequence of knots {u₀,...,u_2n+N-2}. We want to introduce in that list an additional knot u', different or equal to any of the original ones, but the graphic of the curve must remain the same.

As the number of vertices (L+1) and knots (K+1) are related by K = L+n-1, the inclusion of a new knot implies the creation of a new curve piece, that is to say, a subdivision and, consequently, a new vertex.

In the sequence of vertices, { u'₀,...,u'_2n+N-1}, the new knot takes the i-th position,

And as we already know, the blossom provides us the vertices of the control polygon:

The iterated application of the insertion algorithm of the knots u_i,u_i+1 until they reach the multiplicity n is an equivalent way of obtaining the control polygon of the curve over the interval [u_i,u_i+1]. Example. 

This seems clear because the list of knots of that interval after the insertion will be:

{u_i ^{< n >} , u_i+1 ^{< n >} } and that corresponds to a Bézier curve with vertices: 

c_i = d[u_i ^{< n-i >} , u_i+1 ^{< i >} ].

10  Degree Elevation

We may elevate the degree of B-splines in (almost) the same way as we elevate the degree of Bézier curves using:

which associates the blossom of a curve of degree n with the blossom of degree n+1 for the same curve. 

Expression (19) was derived for Bézier curves and therefore it makes no reference to any sequence of knots. 

A given B-spline is a piecewise degree n curve over a given knot sequence: {u₀ ^{< n >} , u₁ ^{< n >} } . Its differentiability is determined by knot multiplicities. If we write it as a piecewise curve of degree n+1, we need to increase the multiplicity of every knot by one, thus keeping the original differentiability properties. Hence the sequence of knots will be  {u₀ ^{< n+1 >} , u₁ ^{< n+1 >} }. 

Consequently, in order to elevate the degree we have to use formula (19), but taking into account that we have to duplicate every inner knot: from u_n-1 to u_n+N-1. Example.

In order to elevate the degree of a piecewise polynomial curve we use expression (19), for instance, for finding the B-spline polygon° with the knot sequence,

and we finally obtain 2n+2N knots and n+2N vertices.

11  Differentiability

In chapter two, we proved that the derivatives of a Bézier curve could be expressed by the blossom:

using vectorial interpolations with vector e, that connects the points 0 and 1 over the real line.

This expression is still acceptable for every piece of a spline curve, because it is based on the blossom. For instance, the first derivative in u ∊ [u_i,u_i+1],

That is, the vertices of the last step of the algorithm determine the tangent directions to the curve at c(u). Example. For higher derivatives,

And if we have piecewise polynomial curves of degree n, the curve c(u) is C^n-1 at u_i, if this knot is simple.

In case of multiple knots is not much complicated. Example.

This result shows the versatility of piecewise polynomial curves, which allow us to combine pieces with different classes of differentiability by repeating the knots at the unions.

12  B-spline functions

As the iterated application of the de Casteljau algorithm introduces the Bernstein polynomials, the de Boor algorithm introduces polynomial functions in each piece.

Consider piecewise polynomial functions defined over [u₀,u_m], with partition {u₀,...,u_m}, such that inside each interval [u_i,u_i+1] the functions are polynomials of degree n and at every knot u_i they are C^n-r_i. This functions form a linear space.

The dimension of the spline function space of degree n and N pieces is dim = n+N = 1+L, that is, it is equal to the number of vertices of the B-spline polygon.

We can encode the de Boor algorithm in some functions {Nⁿ₀(u),..., Nⁿ_L(u)}, basis of that space, such that the polygon of the curve is {d₀,..., d_L},

In order to do that, we have to construct functions instead of parametric curves. 

Expressing the linear monomial u with the blossom,

elevating the blossom to degree n, we obtain

Hence, in order to find the B-spline polygon, {ξ₀,...,ξ_n+N-1}, of the linear monomial with a sequence of knots {u₀,...,u_2n+N-2}, degree n and N pieces, we evaluate the blossom

These terms are called Greville abscissae.

Therefore, if we express a piecewise polynomial function f(u), as a graphic, (u,f(u)), the vertices of its B-spline control polygon will be of the form (ξ_i,[d']_i), where [d']_i are the vertices of the parametric "curve'' f(u).

With that information, we construct the B-spline functions, Nⁿ_i(u), of degree n over a sequence of knots {u₀,...,u_2n+N-2} in the same way as those of the graphic which has as B-spline polygon {dⁱ₀,...,dⁱ_n+N-1}, where dⁱ_j = (ξ_j,Δⁱ_j), that is, the ordinate of every vertex is null, but the one corresponding to index i.

Hence, {Δⁱ₀,...,Δⁱ_n+N-1} is the polygon of the nodal function Nⁿ_i(u). 
Therefore, {Σd_iΔⁱ₀,...,Σd_iΔⁱ_n+N-1} = {d₀,...,d_n+N-1} is, at the same time, the polygon of c(u) and Σd_iNⁿ_i(u),. Consequently we have arrived to expression (24). 

13  Properties of B-spline functions 

B-spline functions are piecewise polynomials.

Consider the graphic of the function Nⁿ_i(u) over a sequence of knots {u₀,...,u_2n+N-2}.

The support, the closed interval out of which the function Nⁿ_i(u) is null, is [u_i-1,u_i+n]. A major property of these functions is that they have minimal support. There are no non-null functions with smaller support than the B-spline functions.

All of these are linearly independent, hence, the B-spline functions form a basis for this space.

And B-spline functions form a partition of unity, as Bernstein polynomials,

Just as the de Casteljau algorithm for Bézier curves is related to the recursion of Bernstein polynomials, the de Boor algorithm yields a recursion for B-splines,

for a given sequence of indices {u₀,...,u_2n+N-2}. Example.

14  Rational Splines 

As we said, iterated application of the de Boor algorithm to rational curves introduces an auxiliary coordinate that gives place to the denominator of the parametrization.

In the same way, a piecewise rational curve could be expressed in terms of B-spline functions introducing a denominator.

Hence, a rational degree n curve with N pieces is determined by the vertices of its B-spline polygon , {d₀,...,d_n+N-1}, the corresponding weights, {w₀,...,w_n+N-1}, and a sequence of knots, {u₀,...,u_2n+N-2},

The procedures derived for piecewise polynomial curves as knot insertion, degree elevation... can be automatically translated to rational curves by introducing an auxiliary coordinate and projecting.

Because of local control property, modification of a weight changes only n+1 pieces of the curve. Example. The properties of rational curves hold, and of course, those of piecewise polynomials.