Unit 6: B-spline Curves

Unit 6: B-spline Curves

Motivation

Consider designing the profile of a vase. The left figure below is a Bézier curve of degree 11; but, it is difficult to bend the "neck" toward the line segment P₄P₅. Of course, we can add more control points near this segment to increase the weight to that region. However, this will increase the degree of the curve. In many cases, it is not worth to use such a high degree polynomial.

As discussed in a previous page about the derivatives of a Bézier curve, we can join two Bézier curves together. As long as the last leg of the first curve and the first leg of the second have the same direction, we can at least achieve G¹ continuity because the tangent vectors have the same direction but may have different length (i.e., if the lengths are the same, it becomes C¹ continuous). The middle figure above uses this idea. It has three Bézier curve segments of degree 3 with joining points marked with yellow rectangles. This shows that with multiple low degree Bézier curve segments satisfying the G¹ continuous condition, we still can design complex shapes. But, maintaining this G¹ continuous condition may be tedious and undesirable.

Is it possible that we still can use lower degree curve segments without worrying about the G¹ continuous condition? B-spline curves are generalizations of Bézier curves and are developed to answer this question. The right figure above is a B-spline curve of degree 3 defined by 8 control points. In fact, there are five Bézier curve segments of degree 3 joining together to form the B-spline curve defined by the control points. In the above, those little dots subdivide the B-spline curve into Bézier curve segments. One can move control points for modifying the shape of the curve just like what we do to Bézier curves. We can also modify the subdivision of the curve. Therefore, B-spline curves have higher degree of freedom for curve design.

Subdividing the curve directly is difficult to do. Instead, we subdivide the domain of the curve. Thus, if the domain of a curve is [0,1], this closed interval is subdivided by points called knots. Let these knots be 0 <= u₀ <= u₁ <= ... <= u_m <= 1. Then, points C(u_i)'s subdivide the curve as shown in the figure below and, consequently, modifying the subdivision of [0,1] changes the shape of the curve.

In summary, to design a B-spline curve, we need a set of control points, a set of knots and a set of coefficients, one for each control point, so that all curve segments are joined together satisfying certain continuity condition. The computation of the coefficients is perhaps the most complex step because they must ensure certain continuity conditions. Fortunately, this computation is usually not needed in this course. We only need to know their characteristics for reasoning about B-spline curves.

B-spline Basis Functions: Definition

Bézier basis functions are used as weights. B-spline basis functions will be used the same way; however, they are much more complex. There are two interesting properties that are not part of the Bézier basis functions, namely: (1) the domain is subdivided by knots, and (2) basis functions are not non-zero on the entire interval. In fact, each B-spline basis function is non-zero on a few adjacent subintervals and, as a result, B-spline basis functions are quite "local".

Let U be a set of m + 1 non-decreasing numbers, u₀ <= u₂ <= u₃ <= ... <= u_m. The u_i's are called knots, the set U the knot vector, and the half-open interval [u_i, u_i+1) the i-th knot span. Note that since some u_i's may be equal, some knot spans may not exist. If a knot u_i appears k times (i.e., u_i = u_i+1 = ... = u_i+k-1), where k > 1, u_i is a multiple knot of multiplicity k, written as u_i(k). Otherwise, if u_i appears only once, it is a simple knot. If the knots are equally spaced (i.e., u_i+1 - u_i is a constant for 0 <= i <= m - 1), the knot vector or the knot sequence is said uniform; otherwise, it is non-uniform.

The knots can be considered as division points that subdivide the interval [u₀, u_m] into knot spans. All B-spline basis functions are supposed to have their domain on [u₀, u_m]. In this note, we use u₀ = 0 and u_m = 1 frequently so that the domain is the closed interval [0,1].

To define B-spline basis functions, we need one more parameter, the degree of these basis functions, p. The i-th B-spline basis function of degree p, written as N_i,p(u), is defined recursively as follows:

The above is usually referred to as the Cox-de Boor recursion formula. This definition looks complicated; but, it is not difficult to understand. If the degree is zero (i.e., p = 0), these basis functions are all step functions and this is what the first expression says. That is, basis function N_i,0(u) is 1 if u is in the i-th knot span [u_i, u_i+1). For example, if we have four knots u₀ = 0, u₁ = 1, u₂ = 2 and u₃ = 3, knot spans 0, 1 and 2 are [0,1), [1,2), [2,3) and the basis functions of degree 0 are N_0,0(u) = 1 on [0,1) and 0 elsewhere, N_1,0(u) = 1 on [1,2) and 0 elsewhere, and N_2,0(u) = 1 on [2,3) and 0 elsewhere. This is shown below:

To understand the way of computing N_i,p(u) for p greater than 0, we use the triangular computation scheme. All knot spans are listed on the left (first) column and all degree zero basis functions on the second. This is shown in the following diagram.

To compute N_i,1(u), N_i,0(u) and N_i+1,0(u) are required. Therefore, we can compute N_0,1(u), N_1,1(u), N_2,1(u), N_3,1(u) and so on. All of these N_i,1(u)'s are written on the third column. Once all N_i,1(u)'s have been computed, we can compute N_i,2(u)'s and put them on the fourth column. This process continues until all required N_i,p(u)'s are computed.

In the above, we have obtained N_0,0(u), N_1,0(u) andN_2,0(u) for the knot vector U = { 0, 1, 2, 3 }. Let us compute N_0,1(u) and N_1,1(u). To compute N_0,1(u), since i = 0 and p = 1, from the definition we have

Since u₀ = 0, u₁ = 1 and u₂ = 2, the above becomes

Since N_0,0(u) is non-zero on [0,1) and N_1,0(u) is non-zero on [1,2), if u is in [0,1) (resp., [1,2) ), only N_0,0(u) (resp., N_1,0(u) ) contributes to N_0,1(u). Therefore, if u is in [0,1), N_0,1(u) is uN_0,0(u) = u, and if u is in [1,2), N_0,1(u) is (2 - u)N_1,0(u) = (2 - u). Similar computation gives N_1,1(u) = u - 1 if u is in [1,2), and N_1,1(u) = 3 - u if u is in [2,3). In the following figure, the black and red lines are N_0,1(u) and N_1,1(u), respectively. Note that N_0,1(u) (resp., N_1,1(u)) is non-zero on [0,1) and [1,2) (resp., [1,2) and [2,3)).

Once N_0,1(u) and N_1,1(u) are available, we can compute N_0,2(u). The definition gives us the following:

Plugging in the values of the knots yields

Note that N_0,1(u) is non-zero on [0,1) and [1,2) and N_1,1(u) is non-zero on [1,2) and [2,3). Therefore, we have three cases to consider:

1. u is in [0,1):
   In this case, only N_0,1(u) contributes to the value of N_0,2(u). Since N_0,1(u) is u, we have

2. u is in [1,2):
   In this case, both N_0,1(u) and N_1,1(u) contribute to N_0,2(u). Since N_0,1(u) = 2 - u and N_1,1(u) = u - 1 on [1,2), we have

3. u is in [2,3):
   In this case, only N_1,1(u) contributes to N_0,2(u). Since N_1,1(u) = 3 - u on [2,3), we have

If we draw the curve segment of each of the above three cases, we shall see that two adjacent curve segments are joined together to form a curve at the knots. More precisely, the curve segments of the first and second cases join together at u = 1, while the curve segments of the second and third cases join at u = 2. Note that the composite curve shown here is smooth. But in general it is not always the case if a knot vector contains multiple knots.

Two Important Observations

Since N_i,1(u) is computed from N_i,0(u) and N_i+1,0(u) and since N_i,0(u) and N_i+1,0(u) are non-zero on span [u_i, u_i+1) and [u_i+1, u_i+2), respectively, N_i,1(u) is non-zero on these two spans. In other words, N_i,1(u) is non-zero on [u_i, u_i+2). Similarly, since N_i,2(u) depends on N_i,1(u) and N_i+1,1(u) and since these two basis functions are non-zero on [u_i, u_i+2) and [u_i+1, u_i+3), respectively, N_i,2(u) is non-zero on [u_i, u_i+3). In general, to determine the non-zero domain of a basis function N_i,p(u), one can trace back using the triangular computation scheme until it reaches the first column. The covered spans are the non-zero domain of this basis function. For example, suppose we want to find out the non-zero domain of N_1,3(u). Based on the above discussion, we can trace back in the north-west and south-west directions until the first column is reached as shown with the blue dotted line in the following diagram. Thus, N_1,3(u) is non-zero on [u₁, u₂), [u₂, u₃), [u₃, u₄) and [u₄, u₅). Or, equivalently, it is non-zero on [u₁, u₅).

In summary, we have the following observation:

Basis function N_i,p(u) is non-zero on [u_i, u_i+p+1). Or, equivalently, N_i,p(u) is non-zero on p+1 knot spans [u_i, u_i+1), [u_i+1, u_i+2), ..., [u_i+p, u_i+p+1).

Next, we shall look at the opposite direction. Given a knot span [u_i, u_i+1), we want to know which basis functions will use this span in its computation. We can start with this knot span and draw a north-east bound arrow and a south-east bound arrow. All basis functions enclosed in this wedge shape use N_i,0(u) (why?) and hence are non-zero on this span. Therefore, all degree p basis functions that are non-zero on [u_i, u_i+1) are the intersection of this wedge and the column that contains all N_i,p(u)'s. In fact, this column and the two arrows form an equilateral triangle with this column being the vertical side. Counting from N_i,0(u) to N_i,p(u) there are p+1 columns. Therefore, the vertical side of the equilateral triangle must have at most p+1 entries, namely N_i,p(u), N_i-1,p(u), N_i-2,p(u), ..., N_i-p+2,p(u), N_i-p+1,p(u) and N_i-p,p(u).

Let us take a look at the above diagram. To find all degree 3 basis functions that are non-zero on [u₄, u₅), draw two arrows and all functions on the vertical edges are what we want. In this case, they are N_1,3(u), N_2,3(u), N_3,3(u), and N_4,3(u). This is shown with the orange triangle. The blue (resp., red) triangle shows the degree 3 basis functions that are non-zero on [u₃, u₄) (resp., [u₂, u₃) ). Note that there are only three degree three basis polynomials that are non-zero on [u₂, u₃).

In summary, we have observed the following property.

On any knot span [u_i, u_i+1), at most p+1 degree p basis functions are non-zero, namely: N_i-p,p(u), N_i-p+1,p(u), N_i-p+2,p(u), ..., N_i-1,p(u) and N_i,p(u),

What Is the Meaning of the Coefficients?

Finally, let us investigate the meaning of the coefficients in the definition of N_i,p(u). As N_i,p(u) is being computed, it uses N_i,p-1(u) and N_i+1,p-1(u). The former is non-zero on [u_i, u_i+p). If u is in this half-open interval, then u - u_i is the distance between u and the left end of this interval, the interval length is u_i+p - u_i, and (u - u_i) / (u_i+p - u_i) is the ratio of the above mentioned distances and is always in the range of 0 and 1. See the diagram below. The second term, N_i,p-1(u), is non-zero on [u_i+1, u_i+p+1). If u is in this interval, then u_i+p+1 - u is the distance from u to the right end of this interval, u_i+p+1 - u_i+1 is the length of the interval, and (u_i+p+1 - u) / (u_i+p+1 - u_i+1) is the ratio of these two distances and its value is in the range of 0 and 1. Therefore, N_i,p(u) is a linear combination of N_i,p-1(u) and N_i+1,p-1(u) with two coefficients, both linear in u, in the range of 0 and 1.

B-spline Basis Functions: Important Properties

Let us recall the definition of the B-spline basis functions as follows:

This set of basis functions has the following properties, many of which resemble those of Bézier basis functions.

1. N_i,p(u) is a degree p polynomial in u
2. Nonnegativity -- For all i, p and u, N_i,p(u) is non-negative
3. Local Support -- N_i,p(u) is a non-zero polynomial on [u_i,u_i+p+1)
   This has been discussed on previous page.
4. On any span [u_i, u_i+1), at most p+1 degree p basis functions are non-zero, namely: N_i-p,p(u), N_i-p+1,p(u), N_i-p+2,p(u), ..., and N_i,p(u)
5. Partition of Unity -- The sum of all non-zero degree p basis functions on span [u_i, u_i+1) is 1:
   The previous property shows that N_i-p,p(u), N_i-p+1,p(u), N_i-p+2,p(u), ..., and N_i,p(u) are non-zero on [u_i, u_i+1). This one states that the sum of these p+1 basis functions is 1.
6. If the number of knots is m+1, the degree of the basis functions is p, and the number of degree p basis functions is n+1, then m = n + p + 1 :
   This is not difficult to see. Let N_n,p(u) be the last degree p basis function. It is non-zero on [u_n, u_n+p+1). Since it is the last basis function, u_n+p+1 must be the last knot u_m. Therefore, we have u_n+p+1 = u_m and n + p + 1 = m. In summary, given m and p, let n = m - p - 1 and the degree p basis functions are N_0,p(u), N_1,p(u), N_2,p(u), ..., and N_n,p(u).
7. Basis function N_i,p(u) is a composite curve of degree p polynomials with joining points at knots in [u_i, u_i+p+1 )
   The example shown on the previous page illustrates this property well. For example, N_0,2(u), which is non-zero on [0,3), is constructed from three parabolas defined on [0,1), [1,2) and [2,3). They are connected together at the knots 2 and 3.
8. At a knot of multiplicity k, basis function N_i,p(u) is C^p-k continuous.
   Therefore, increasing multiplicity decreases the level of continuity, and increasing degree increases continuity. The above mentioned degree two basis function N_0,2(u) is C¹ continuous at knots 2 and 3, since they are simple knots (k = 1).

The Impact of Multiple Knots

Multiple knots do have significant impact on the computation of basis functions and some "counting" properties. We shall look at two of them and a calculation example will be provided on the next page.

1. Each knot of multiplicity k reduces at most k-1 basis functions' non-zero domain.
   Consider N_i,p(u) and N_i+1,p(u). The former is non-zero on [u_i, u_i+p+1) while the latter is non-zero on [u_i+1, u_i+p+2). If we move u_i+p+2 to u_i+p+1 so that they become a double knot. Then, N_i,p(u) still has p+1 knot spans on which it is non-zero; but, the number of knot spans on which N_i+1,p(u) is non-zero is reduced by one because the span [u_i+p+1,u_i+p+2) disappears.

This observation can be generalized easily. In fact, ignoring the change of knot span endpoints, to create a knot of multiplicity k, k-1 basis functions will be affected. One of them loses one knot span, a second of them loses two, a third of them loses three and so on.

The figures below show the basis functions of degree 5 where the left end and right end knots have multiplicity 6, while all knots in between are simple (Figure (a))). Figure (b) is the result of moving u₅ to u₆. Those basis functions ended at u₆ have fewer knot spans on which they are non-zero. Then, u₄ and then u₃ are moved to u₆, making u₆ a knot of multiplicity 4 (Figure (c) and (d). Figure (e) shows the result after moving u₂ to u₆, creating a knot of multiplicity 5.

2. At each internal knot of multiplicity k, the number of non-zero basis functions is at most p - k + 1, where p is the degree of the basis functions.
   Since moving u_i-1 to u_i will pull a basis function whose non-zero ends at u_i-1 to end at u_i, this reduces the number of non-zero basis function at u_i by one. More precisely, increasing u_i's multiplicity by one will reduce the number of non-zero basis functions by one. Since there are at most p+1 basis functions can be non-zero at u_i, the number of non-zero basis functions at a knot of multiplicity k is at most (p + 1) - k = p - k + 1.

In the above figures, since the multiplicity of knot u₆ are 1 (simple), 2, 3, 4 and 5, the numbers of non-zero basis function at u₆ are 5, 4, 3, 2 and 1.

B-spline Basis Functions: Computation Examples

Two examples, one with all simple knots while the other with multiple knots, will be discussed in some detail on this page.

Simple Knots

Suppose the knot vector is U = { 0, 0.25, 0.5, 0.75, 1 }. Hence, m = 4 and u₀ = 0, u₁ = 0.25, u₂ = 0.5, u₃ = 0.75 and u₄ = 1. The basis functions of degree 0 are easy. They are N_0,0(u), N_1,0(u), N_2,0(u) and N_3,0(u) defined on knot span [0,0.25,), [0.25,0.5), [0.5,0.75) and [0.75,1), respectively, as shown below.

The following table gives the result of all N_i,1(u)'s:

The following shows the graphs of these basis functions. Since the internal knots 0.25, 0.5 and 0.75 are all simple (i.e., k = 1) and p = 1, there are p - k + 1 = 1 non-zero basis function and three knots. Moreover, N_0,1(u), N_1,1(u) and N_2,1(u) are C⁰ continuous at knots 0.25, 0.5 and 0.75, respectively.

From N_i,1(u)'s, one can compute the basis functions of degree 2. Since m = 4, p = 2, and m = n + p + 1, we have n = 1 and there are only two basis functions of degree 2: N_0,2(u) and N_1,2(u). The following table is the result:

The following figure shows the two basis functions. The three vertical blue lines indicate the positions of knots. Note that each basis function is a composite curve of three degree 2 curve segments. For example, N_0,2(u) is the green curve, which is the union of three parabolas defined on [0,0.25), [0.25, 0.5) and [0.5,0.75). These three curve segments join together forming a smooth bell shape. Please verify that N_0,2(u,) (resp., N_1,2(u)) is C¹ continuous at its knots 0.25 and 0.5 (resp., 0.5 and 0.75). As mentioned on the previous page, at the knots, this composite curve is of C¹ continuity.

Knots with Positive Multiplicity

If a knot vector contains knots with positive multiplicity, we will encounter the case of 0/0 as will be seen later. Therefore, we shall define 0/0 to be 0. Fortunately, this is only for hand calculation. For computer implementation, there is an efficient algorithm free of this problem. Furthermore, if u_i is a knot of multiplicity k (i.e., u_i = u_i+1 = ... = u_i+k-1), then knot spans [u_i,u_i+1), [u_i+1,u_i+2), ..., [u_i+k-2,u_i+k-1) do not exist, and, as a result, N_i,0(u), N_i+1,0(u), ..., N_i+k-1,0(u) are all zero functions.

Consider a knot vector U = { 0, 0, 0, 0.3, 0.5, 0.5, 0.6, 1, 1, 1 }. Thus, 0 and 1 are of multiplicity 3 (i.e., 0(3) and 1(3)) and 0.5 is of multiplicity 2 (i.e., 0.5(2)). As a result, m = 9 and the knot assignments are

Let us compute N_i,0(u)'s. Note that since m = 9 and p = 0 (degree 0 basis functions), we have n = m - p - 1 = 8. As the table below shows, there are only four non-zero basis functions of degree 0: N_2,0(u), N_3,0(u), N_5,0(u) and N_6,0(u).

Then, we proceed to basis functions of degree 1. Since p is 1, n = m - p - 1 = 7. The following table shows the result:

The following figure shows the graphs of these basis functions.

Let us take a look at a particular computation, say N_1,1(u). It is computed with the following expression:

Plugging u₁ = u₂ = 0 and u₃ = 0.3 into this equation yields the following:

Since N_1,0(u) is zero everywhere, the first term becomes 0/0 and is defined to be zero. Therefore, only the second term has an impact on the result. Since N_2,0(u) is 1 on [0,0.3), N_1,1(u) is 1 - (10/3)u on [0,0.3).

Next, let us compute all N_i,2(u)'s. Since p = 2, we have n = m - p - 1 = 6. The following table contains all N_i,2(u)'s:

The following figure shows all basis functions of degree 2.

Let us pick a typical computation as an example, say N_3,2(u). The expression for computing it is

Plugging in u₃ = 0.3, u₄ = u₅ = 0.5 and u₆ = 0.6 yields

Since N_3,1(u) is non-zero on [0.3, 0.5) and is equal to 5u - 1.5, (5u - 1.5)² is the non-zero part of N_3,2(u) on [0.3, 0.5). Since N_4,1(u) is non-zero on [0.5, 0.6) and is equal to 6 - 10u, (6 - 10u)² is the non-zero part of N_3,2(u) on [0.5, 0.6).

Let us investigate the continuity issues at knot 0.5(2). Since its multiplicity is 2 and the degree of these basis functions is 2, basis function N_3,2(u) is C⁰ continuous at 0.5(2). This is why N_3,2(u) has a sharp angle at 0.5(2). For knots not at the two ends, say 0.3, C¹ continuity is maintained since all of them are simple knots.

B-spline Curves: Definition

Given n + 1 control points P₀, P₁, ..., P_n and a knot vector U = { u₀, u₁, ..., u_m }, the B-spline curve of degree p defined by these control points and knot vector U is

where N_i,p(u)'s are B-spline basis functions of degree p. The form of a B-spline curve is very similar to that of a Bézier curve. Unlike a Bézier curve, a B-spline curve involves more information, namely: a set of n+1 control points, a knot vector of m+1 knots, and a degree p. Note that n, m and p must satisfy m = n + p + 1. More precisely, if we want to define a B-spline curve of degree p with n + 1 control points, we have to supply n + p + 2 knots u₀, u₁, ..., u_n+p+1. On the other hand, if a knot vector of m + 1 knots and n + 1 control points are given, the degree of the B-spline curve is p = m - n - 1. The point on the curve that corresponds to a knot u_i, C(u_i), is referred to as a knot point. Hence, the knot points divide a B-spline curve into curve segments, each of which is defined on a knot span. We shall show that these curve segments are all Bézier curve of degree p on the curve subdivision page.

Although N_i,p(u) looks like B_n,i(u), the degree of a B-spline basis function is an input, while the degree of a Bézier basis function depends on the number of control points. To change the shape of a B-spline curve, one can modify one or more of these control parameters: the positions of control points, the positions of knots, and the degree of the curve.

If the knot vector does not have any particular structure, the generated curve will not touch the first and last legs of the control polyline as shown in the left figure below. This type of B-spline curves is called open B-spline curves. We may want to clamp the curve so that it is tangent to the first and the last legs at the first and last control points, respectively, as a Bézier curve does. To do so, the first knot and the last knot must be of multiplicity p+1. This will generate the so-called clamped B-spline curves. See the middle figure below. By repeating some knots and control points, the generated curve can be a closed one. In this case, the start and the end of the generated curve join together forming a closed loop as shown in the right figure below. In this note, we shall use clamped curve.

The above figures have n+1 control points (n=9) and p = 3. Then, m must be 13 so that the knot vector has 14 knots. To have the clamped effect, the first p+1 = 4 and the last 4 knots must be identical. The remaining 14 - (4 + 4) = 6 knots can be anywhere in the domain. In fact, the curve is generated with knot vector U = { 0, 0, 0, 0, 0.14, 0.28, 0.42, 0.57, 0.71, 0.85, 1, 1, 1, 1 }. Note that except for the first four and last four knots, the middle ones are almost uniformly spaced. The figures also show the corresponding curve segment on each knot span. In fact, the little triangles are the knot points.

The Use of Terms

We use open, clamped and closed to describe three types of B-spline curves. However, not every author would use the same terminology and there is no agreement for a standard use. For example, some authors may use floating, open and periodic for open, clamped and closed curves. Some other authors may use "periodic" for an open B-spline curve with a uniform knot sequence. Therefore, when you read other literature, make sure you first check the definitions. Otherwise, it is likely that you could be confused,

Please continue with open curves and closed curves.

B-spline Curves: Open Curves

As mentioned earlier, if the first and last knots do not have multiplicity p+1, where p is the degree of a B-spline curve, the curve will not be tangent to the first and last legs at the first and last control points, respectively. The curve is an open B-spline curve. In this case, we should be careful about one additional restriction. On a previous page we showed an example of basis function computation using knot vector U = { 0, 0.25, 0.5, 0.75, 1 }, where m = 4. If the basis functions are of degree 1 (i.e., p = 1), there are three basis functions N_0,1(u), N_1,1(u) and N_2,1(u) as shown below.

Since this knot vector is not clamped, the first and the last knot spans (i.e., [0, 0.25) and [0.75, 1)) have only one non-zero basis functions while the second and third knot spans (i.e., [0.25, 0.5) and [0.5, 0.75)) have two non-zero basis functions. Recall from the B-spline basis function important properties that on a knot span [u_i, u_i+1), there are at most p+1 degree p non-zero basis functions of degree p. Therefore, in this example, knot spans [0,0.25) and [0.75,1) do not have "full support" of basis functions. In general, for degree p, intervals [u₀, u_p) and [u_m-p, u_m] will not have "full support" of basis functions and are ignored when a B-spline curve is open. Consequently, we have the following important note:

Consider a B-spline curve of degree 6 (i.e., p = 6) defined by 14 control points (i.e., n = 13). The number of knots is 21 (i.e., m = n + p + 1 = 20). If the knot vector is uniform, the knots are 0, 0.05, 0.10, 0.15, ..., 0.90, 0.95 and 1.0. The open curve is defined on [u_p, u_n-p] = [u₆, u₁₄] = [0.3, 0.7] and is not tangent to the first and last legs. The left figure below shows the curve and the right figure gives the B-spline basis functions.

Even though some knot spans at both end are not used, the B-spline curve still is defined by all control points. As discussed on the B-spline basis functions page that there are at most p+1 basis functions N_i-p,p(u), N_i-p,p+1(u), ..., N_i,p(u) non-zero on knot span [u_i, u_i+1). Therefore, there are p+1 non-zero functions on [u_p, u_i+1): N_0,p(u), N_1,p(u), ..., N_p,p(u). This is a "full" count. Note that N_0,p(u) has its tail in [u_p, u_p+1) and, hence, the contribution of control point P₀ to the construction of the open B-spline curve is smaller than those of most other control points. A similar argument can be used to show that P_n is also involved in the definition of the curve.

Let us use an example to illustrate the change between an open curve and a clamped one. We start with an open B-spline curve of degree 4 defined by 9 control points (i.e., n = 8) and a uniform knot vector { 0, 1/13, 2/13, 3/13, ..., 12/13, 1 }. If we change the second knot 1/13 to 0 making 0 a double knot, the curve is the yellow one in the figure. In fact, this curve and the original one with 0 being a simple knot are almost identical. Now, if we change the third knot 2/13 to 0 making 0 a knot of multiplicity 3, the result is the red curve. If the fourth knot 3/13 is change to 0 (multiplicity 4), the resulting curve is the blue one. As you can see, these three open curves are not very different from each other. Now, let us make the fifth knot 4/13 to 0. Since 0 is now a knot of multiplicity 5 (i.e., p+1), the curve not only passes through the first control point but also is tangent to the first leg of the control polyline (i.e., clamped). As you can see from the figure, the shape of the curve changes drastically by pulling one end of it to the first control point. The same holds true if we make the last 5 knots to 1.

B-spline Curves: Closed Curves

There are many ways to generate closed curves. The simple ones are either wrapping control points or wrapping knot vectors.

Wrapping Control Points

Suppose we want to construct a closed B-spline curve C(u) of degree p defined by n+1 control points P₀, P₁, ..., P_n. The number of knots is m+1, where m = n + p + 1. Here is the construction procedure:

1. Design an uniform knot sequence of m+1 knots: u₀ = 0, u₁ = 1/m, u₁ = 2/m, ..., u_m = 1. Note that the domain of the curve is [u_p, u_n-p]. See the discussion in open curves for the details.
2. Wrap the first p and last p control points. More precisely, let P₀ = P_n-p+1, P₁ = P_n-p+2, ..., P_p-2 = P_n-1 and P_p-1 = P_n. This is shown in the figure below.

The constructed curve is C^p-1 continuous at the joining point C(u_p) = C(u_n-p).

The following is an example. Figure (a) shows an open B-spline curve of degree 3 defined by 10 (n = 9) control points and a uniform knot vector. In the figure, control point pairs 0 and 7, 1 and 8, and 2 and 9 are placed close to each other to illustrate the construction. Figure (b) shows the result of making control points 0 and 7 identical. The shape of the curve does not change very much. Then, control points 1 and 8 are made identical as shown in Figure (c). It is clear that the gap between the first and last points of the curve is closer. Finally, the curve becomes a closed on when control points 2 and 9 are made identical as shown in Figure (d).

Wrapping Knots

Another way of constructing closed B-spline curves is by wrapping knots. Suppose we want to construct a closed B-spline curve C(u) of degree p defined by n+1 control points P₀, P₁, ..., P_n. The following is the construction procedure:

1. Add a new control point P_n+1 = P₀. Therefore, the number of control points is n+2.
2. Find an appropriate knot sequence of n+1 knots u₀, u₁, ..., u_n. These knots are not necessarily uniform, an advantage over the method discussed above.
3. Add p+2 knots and wrap around the first p+2 knots: u_n+1 = u₀, u_n+2 = u₁, ..., u_n+p = u_p-1, u_n+p+1 = u_p, u_n+p+2 = u_p+1 as shown in the following diagram. In this way, we have n+p+2 = (n+1) + p + 1 knots.

4. The open B-spline curve C(u) of degree p defined on the above constructed n+1 control points and n+p+2 knots is a closed curve with C^p-1 continuity at the joining point C(u₀) = C(u_n+1). Note that the domain of this closed curve is [u₀, u_n+1].

B-spline Curves: Important Properties

B-spline curves share many important properties with Bézier curves, because the former is a generalization of the later. Moreover, B-spline curves have more desired properties than Bézier curves. The list below shows some of the most important properties of B-spline curves.

In the following we shall assume a B-spline curve C(u) of degree p is defined by n + 1 control points and a knot vector U = { u₀, u₁, ...., u_m } with the first p+1 and last p+1 knots "clamped" (i.e., u₀ = u₁ = ... = u_p and u_m-p = u_m-p+1 = ... = u_m).

1. B-spline curve C(u) is a piecewise curve with each component a curve of degree p.
   As mentioned in previous page, C(u) can be viewed as the union of curve segments defined on each knot span. In the figure below, where n = 10, m = 14 and p = 3, the first four knots and last four knots are clamped and the 7 internal knots are uniformly spaced. There are eight knot spans, each of which corresponds to a curve segment. In the left figure below, these knot points are shown as triangles.

This nice property allows us to design complex shapes with lower degree polynomials. For example, the right figure below shows a Bézier curve with the same set of control points. It still cannot follow the control polyline nicely even though its degree is 10!

In general, the lower the degree, the closer a B-spline curve follows its control polyline. The following figures all use the same control polyline and knots are clamped and uniformly spaced. The first figure has degree 7, the middle one has degree 5 and the right figure has degree 3. Therefore, as the degree decreases, the generated B-spline curve moves closer to its control polyline.

2. Equality m = n + p + 1 must be satisfied.
   Since each control point needs a basis function and the number of basis functions satisfies m = n + p + 1.
3. Clamped B-spline curve C(u) passes through the two end control points P₀ and P_n.
   Note that basis function N_0,p(u) is the coefficient of control point P₀ and is non-zero on [u₀,u_p+1). Since u₀ = u₁ = ... = u_p = 0 for a clamped B-spline curve, N_0,0(u), N_1,0(u), ...., N_p-1,0(u) are zero and only N_p,0(u) is non-zero (recall from the triangular computation scheme). Consequently, if u = 0, then N_0,p(0) is 1 and C(0) = P₀. A similar discussion can show C(1) = P_n
4. Strong Convex Hull Property: A B-spline curve is contained in the convex hull of its control polyline. More specifically, if u is in knot span [u_i,u_i+1), then C(u) is in the convex hull of control points P_i-p, P_i-p+1, ..., P_i.
   If u is in knot span [u_i, u_i+1), there are only p+1 basis functions (i.e., N_i,p(u), ... , N_i-p+1,p(u), N_i-p,p(u)) non-zero on this knot span. Since N_k,p(u) is the coefficient of control point P_k, only p+1 control points P_i, P_i-1, P_i-2, .., P_i-p have non-zero coefficients. Since on this knot span the basis functions are non-zero and sum to 1, their "weighted" average, C(u), must lie in the convex hull defined by control points P_i, P_i-1, P_i-2, .., P_i-p. The meaning of "strong" is that while C(u) still lies in the convex hull defined by all control points, it lies in a much smaller one.

The above two B-spline curves have 11 control points (i.e., n = 10), degree 3 (i.e., p=3) and 15 knots (m = 14) with first four and last four knots clamped. Therefore, the number of knot spans is equal to the number curve segments. The knot vector is

The left figure has u in knot span [u₄, u₅) = [0.12,0.25) and the corresponding point (i.e. C(u)) in the second curve segment. Therefore, there are p+1 = 4 basis functions non-zero on this knot span (i.e., N_4,3(u), N_3,3(u), N_2,3(u) and N_1,3(u) ) and the corresponding control points are P₄, P₃, P₂ and P₁. The shaded area is the convex hull defined by these four points. It is clear that C(u) lies in this convex hull.

The B-spline curve in the right figure is defined the same way. However, u is in [u₉, u₁₀) = [0.75,0.87) and the non-zero basis functions are N_9,3(u), N_8,3(u), N_7,3(u) and N_6,3(u). The corresponding control points are P₉, P₈, P₇ and P₆.

Consequently, as u moves from 0 to 1 and crosses a knot, a basis functions becomes zero and a new non-zero basis function becomes effective. As a result, one control point whose coefficient becomes zero will leave the the definition of the current convex hull and is replaced with a new control point whose coefficient becomes non-zero.

5. Local Modification Scheme: changing the position of control point P_i only affects the curve C(u) on interval [u_i, u_i+p+1).
   This follows from another important property of B-spline basis functions. Recall that N_i,p(u) is non-zero on interval [u_i, u_i+p+1). If u is not in this interval, N_i,p(u)P_i has no effect in computing C(u) since N_i,p(u) is zero. On the other hand, if u is in the indicated interval, N_i,p(u) is non-zero. If P_i changes its position, N_i,p(u)P_i is changed and consequently C(u) is changed.

The above B-spline curves are defined with the same parameters as in the previous convex hull example. We intent to move control point P₂. The coefficient of this control point is N_2,3(u) and the interval on which this coefficient is non-zero is [u₂, u₂₊₃₊₁) = [u₂, u₆) = [0,0.37). Since u₂ = u₃ = 0, only three segments that correspond to [u₃, u₄) (the domain of the first curve segment), [u₄, u₅) (the domain of the second curve segment) and [u₅, u₆) (the domain of the third curve segment) will be affected. The right figure shows the result of moving P₂ to the lower right corner. As you can see, only the first, second and third curve segments change their shapes and all remaining curve segments stay in their original place without any change.

This local modification scheme is very important to curve design, because we can modify a curve locally without changing the shape in a global way. This will be elaborated on the moeing control point page. Moreover, if fine-tuning curve shape is required, one can insert more knots (and therefore more control points) so that the affected area could be restricted to a very narrow region. We shall talk about knot insertion later.

6. C(u) is C^p-k continuous at a knot of multiplicity k
   If u is not a knot, C(u) is in the middle of a curve segment of degree p and is therefore infinitely differentiable. If u is a knot in the non-zero domain of N_i,p(u), since the latter is only C^p-k continuous, so does C(u).

The above B-spline curve has 18 control points (i.e., n = 17), degree 4, and the following clamped knot vector

Thus, u₆ is a double knot, u₉ is a triple knot and u₁₃ is a quadruple knot. Consequently, C(u) is of C⁴ continuous at any point that is not a knot, C³ continuous at all simple knots, C² continuous at u₆, C¹ continuous at u₉, C⁰ continuous at u₁₃.

All points on the curve that correspond to knots are marked with little triangles. Those corresponding to multiple knots are further marked with circles and their multiplicities. It is very difficult to visualize the difference between C⁴, C ³ and even C² continuity. For the C¹ case, the corresponding point lies on a leg, while the C⁰ case forces the curve to pass through a control point. We shall return to this issue later when discussing modifying knots.

7. Variation Diminishing Property:
   The variation diminishing property also holds for B-spline curves. If the curve is in a plane (resp., space), this means no straight line (resp., plane) intersects a B-spline curve more times than it intersects the curve's control polyline.

In the above figure, the blue line intersects both the control polyline and the B-spline curve 6 times, while the yellow line also intersects the control polyline and the B-spline curve 5 times. However, the orange line intersects the control polyline 6 times and the curve 4 times.

8. Bézier Curves Are Special Cases of B-spline Curves.
   If n = p (i.e., the degree of a B-spline curve is equal to n, the number of control points minus 1), and there are 2(p + 1) = 2(n + 1) knots with p + 1 of them clamped at each end, this B-spline curve reduces to a Bézier curve.
9. Affine Invariance
   The affine invariance property also holds for B-spline curves. If an affine transformation is applied to a B-spline curve, the result can be constructed from the affine images of its control points. This is a nice property. When we want to apply a geometric or even affine transformation to a B-spline curve, this property states that we can apply the transformation to control points, which is quite easy, and once the transformed control points are obtained the transformed B-spline curve is the one defined by these new points. Therefore, we do not have to transform the curve.

The Advantage of Using B-spline Curves

B-spline curves require more information (i.e., the degree of the curve and a knot vector) and a more complex theory than Bézier curves. But, it has more advantages to offset this shortcoming. First, a B-spline curve can be a Bézier curve. Second, B-spline curves satisfy all important properties that Bézier curves have. Third, B-spline curves provide more control flexibility than Bézier curves can do. For example, the degree of a B-spline curve is separated from the number of control points. More precisely, we can use lower degree curves and still maintain a large number of control points. We can change the position of a control point without globally changing the shape of the whole curve (local modification property). Since B-spline curves satisfy the strong convex hull property, they have a finer shape control. Moreover, there are other techniques for designing and editing the shape of a curve such as changing knots.

However, keep in mind that B-spline curves are still polynomial curves and polynomial curves cannot represent many useful simple curves such as circles and ellipses. Thus, a generalization of B-spline, NURBS, is required. We will discuss NURBS later.

B-spline Curves: Computing the Coefficients

Although de Boor's algorithm is a standard way for computing the point on a B-spline curve that corresponds to a given u, we really need these coefficients in many cases (e.g., curve interpolation and approximation). We shall illustrate a simple way to do this.

Given a clamped B-spline curve of degree p defined by n+1 control points P₀, P₁, ..., P_n, and m+1 knots u₀=u₁=...=u_p=0, u_p+1, u_p+2, ..., u_m-p-1, u_m-p=u_m-p+1=...= u_m=1, we want to compute the coefficients N_0,p(u), N_1,p(u), ..., N_n,p(u) for any given u in [0,1]. A naive way is the use of the following recurrence relation:

However, this is a very time consuming process. To compute N_i,p(u), we need to compute N_i,p-1(u) and N_i+1,p-1(u). To compute N_i,p-1(u), we need to compute N_i,p-2(u) and N_i+1,p-2(u). To compute N_i+1,p-1(u), we need N_i+1,p-2(u) and N_i+2,p-2(u). As you can see, N_i+1,p-2(u) appears twice, and, as a result, its recursive computations will also be repeated. As the recursion goes deeper, more duplicated computations will occur. This is very similar to the recursive version of de Casteljau's algorithm discussed on a previous page. Consequently, the computation speed is very slow.

There is an easy way. Suppose u is in knot span [u_k,u_k+1). An important property of B-spline basis functions states that at most p+1 basis functions of degree p are non-zero on [u_k,u_k+1), namely: N_k-p,p(u), N_k-p+1,p(u), N_k-p+2,p(u), ..., N_k-1,p(u), N_k,p(u). By definition, the only non-zero basis function of degree 0 on [u_k,u_k+1) is N_k,0(u). As a result, the coefficients can be computed from N_k,0(u) in a "fan-out" triangular form as shown below:

Since N_k,0(u) = 1 on knot span [u_k,u_k+1) and other B-spline basis functions of degree 0 are zero on [u_k,u_k+1), we can start from N_k,0(u) and compute the basis functions of degree 1 N_k-1,1(u) and N_k,1(u). From these two values, we can compute the basis functions of degree 2 N_k-2,2(u), N_k-1,2(u) and N_k,2(u). This process repeats until all p+1 non-zero coefficients are computed.

In this computation, "internal" values such as N_k-1,2(u) has a north-west predecessor (i.e., N_k-1,1(u)) and a south-west predecessor (i.e., N_k,1(u)); values on the north-east direction boundary of the above triangle such as N_k-1,1(u) has only a south-west predecessor (i.e., N_k,0(u)); and values on the south-east direction boundary of this triangle such as N_k,2(u) has only a north-west predecessor (i.e., N_k,1(u)). Thus, values that are on the north-east (resp., south-east) direction boundary use the second (resp., first) term of the recurrence relation in the definition. Only the internal values use both terms. Based on this observation, we have the following algorithm:

Input: n, p, m, u, and m+1 clamped knots { u₀, ..., u_m }
Output: Coefficients N_0,p(u), N_1,p(u), ..., N_n,p(u) in N[0], N[1], ..., N[n]
Algorithm:

Initialize N[0..n] to 0; // initialization
if u = u₀ then // rule out special cases

N[0] = 1.0;
return

else u = u_m then

N[n] = 1.0
return

end if

// now u is between u₀ and u_m

Let u be in knot span [u_k,u_k+1);
N[k] := 1.0 // degree 0 coefficient
for d :=1 to p do // degree d goes from 1 to p

begin

N[k-d] = * N[(k-d)+1]; // right (south-west corner) term only
for i := k-d+1 to k-1 do // compute internal terms

N[i] := * N[i] + * N[i+1];

N[k] = * N[k]; // let (north-west corner) term only

end

// array N[0..n] has the coefficients.

The above is not a very efficient algorithm. Its purpose is to illustrate the idea in an intuitive and easy to understand way. Array N[ ] holds all intermediate and the final results. For a degree d, N[i] stores the value of N_i,d(u), and, at the end, N[k-d], N[k-d+1], ..., N[k] contain the non-zero coefficients. The computation starts with d=1 because we know that the only non-zero basis function is N_k,0(u) if u is in knot span [u_k,u_k+1). The outer loop lets degree d go from 1 to p. The first assignment following begin computes N_k-d,d(u) using only one term (i.e., its south-west term in the triangle, N_k-d+1,d-1(u)), the inner for loop computes the "internal" terms, and the last statement in the outer loop computes N_k,d(u) using only one term (i.e., its north-west term in the triangle, N_k,d-1(u)).

Can you make this algorithm more efficient?

B-spline Curves: A Special Case

If we have 2n+2 knots u₀ = u₁ = ... = u_n = 0 and u_n+1 = u_n+2 = ... = u_2n+1 = 1 (i.e., the first n+1 being 0 and the next n+1 being 1), what are the B-spline basis functions of degree n?

Since every u is in [0,1] = [u_n, u_n+1], the non-zero basis functions of degree n are: N_0,n(u), N_1,n(u), ..., N_n,n(u). Recall the definition of B-spline basis functions as follows:

Since the only non-zero basis function of degree 0 is N_n,0(u), the index i can only be in the range of 0 and n. Therefore, the u_i's are zero and u_i+n's and u_i+n+1's are 1. Consequently, the second equation above can be rewritten as follows:

If we organize the computation of N_0,n(u), N_1,n(u), ..., N_n,n(u) in a triangular form as discussed on the previous page, we have the following diagram. In this diagram, each north-east (resp., south-east) bound arrow means multiplying 1-u (resp., u) to the term at the tail of the arrow. Note that there are n stages in the computation, one for obtaining each column. Therefore, the contribution of N_n,0(u) to N_0,n(u) is (1-u)ⁿ, and the contribution of N_n,0(u) to N_n,n(u) is uⁿ.

Now, consider the computation of a general term N_i,n(u). The contribution of N_n,0(u) to the computation of N_i,n(u) can be determined by the "path-counting" technique that was used to show the correctness of de Casteljau's algorithm and in the computation of higher derivatives of a Bézier curve. Each path going from N_n,0(u) to N_i,n(u) encounters n arrows of which i are south-east bound and n-i are north-east bound. Those north-east (resp., south-east) bound arrows mean multiply the term at the tail by 1-u (resp., u). Therefore, the contribution of N_n,0(u) to N_i,n(u) along a single path is uⁱ(1-u)^n-i. The total number of paths from N_n,0(u) to N_i,n(u) is C(n,i). More precisely, the number of paths is equal to the number of different ways of placing i south-east bound arrows in n positions. The remaining n-i positions are filled with north-east bound arrows. This n arrows precisely describe a single path from N_n,0(u) to N_i,n(u). Since each path contributes uⁱ(1-u)^n-i to the computation and since there are C(n,i) paths, the total contribution of N_n,0(u) to N_i,n(u) is

This is exactly the i-th Bézier basis function of degree n. Therefore, we have the following conclusion:

B-spline Curves: Moving Control Points

Moving control points is the most obvious way of changing the shape of a B-spline curve. The local modification scheme discussed on an earlier page states that changing the position of control point P_i only affects the curve C(u) on interval [u_i, u_i+p+1), where p is the degree of a B-spline curve. In fact, the shape change is translational in the direction of the control point being moved. More precisely, if control point P_i is moved in certain direction to a new position Q_i, then point C(u), where u is in [u_i, u_i+p+1), will be moved in the same direction from P_i to Q_i. However, the distance moved is different from point to point. In the following figures, control point P₄ is moved from the position in the left figure to a new position in the middle figure and finally to its final position in the right figure. As you can see those points corresponding to knots (marked with little triangles) are moved in the same direction.

Let us take a look at some details. Suppose C(u) is a given B-spline curve of degree p defined as follows:

Let control point P_i be moved to a new position P_i + v. Then, the new B-spline curve D(u) of degree p is the following:

Therefore, the new curve D(u) is simply the sum of the original curve C(u) and a translation vector N_i,p(u)v. Since N_i,p(u) is non-zero on the interval [u_i,u_i+p+1), if u is not in this interval, this "translation" term is zero. Hence, moving a control point only affects the shape of a section of the given curve. The left curve below is a B-spline curve of degree 4 (i.e., p = 4) defined by 13 control points (i.e., n = 12) and 18 knots (i.e., m = 17). These 18 knots are all simple and define a clamped curve (i.e., u₀ = u₁ = u₂ = u₃ = u₄ = 0 and u₁₃ = u₁₄ = u₁₅ = u₁₆ = u₁₇ = 1). The remaining knots define 9 knot spans and hence 9 curve segments as shown in the figure. These nine knot spans and curve segments are named as follows:

Now let us move P₆. The result is shown in the right figure above. As you can see, the curve is moved in the same direction. The coefficient of P₆ is N_6,4(u), which is non-zero on [u₆, u₁₁). Thus, moving P₆ affects curve segments 3, 4, 5, 6 and 7. Curve segments 1, 2, 8 and 9 are not affected.

Some Useful Consequences from the Strong Convex Hull Property

Recall from the strong convex hull property that if u lies in [u_i,u_i+1), then C(u) lies in the convex hull defined by control points P_i, P_i-1, ..., P_i-p+1, P_i-p. This will help us perform the following design tasks:

1. Force a curve segment to become a line segment: let p+1 adjacent control points be collinear.

If u lies in knot span [u_i,u_i+1), then C(u) lies in the convex hull defined by p+1 control points P_i, P_i-1, ..., P_i-p+1, P_i-p. Since this is true for all u in that span, the curve segment on this knot span lies entirely in this convex hull. If all of these p+1 control points are collinear (i.e., on a straight line), the convex hull collapses to a line segment and so does the curve segment it contains. As a result, the curve segment on knot span [u_i,u_i+1) becomes a line segment. Note that in this case only this curve segment becomes a line segment. Other curve segments are still non-linear.

Let us take a look at an example. Figures above are defined by n = 15 (i.e., 16 control points), p = 3 (degree 3) and m = 19 (i.e., 20 knots). Note that the first four and last four knots are clamped. Figure (a) is the given B-spline curve. Let us make P₉, P₈, P₇ and P₆ collinear. Therefore, the curve segment on [u₉,u₁₀) lies in the convex hull defined by P₉, P₈, P₇ and P₆. Since this convex hull is a line segment, the curve segment must also be a line segment. Keep in mind that the first four knots are clamped and hence the first three knot spans do not exist. Since [u₉,u₁₀) is the seventh knot span, the seventh segment collapses to the line segment P₇P₈. This is illustrated by figures (b), (c) and (d).

But, why is the curve segment on [u₉,u₁₀) the only collapsed curve segment? Look at Figure (b). The shaded area is the convex hull just before u enters [u₉,u₁₀). This convex hull is defined by control points P₈, P₇, P₆ and P₅, which is still not a line segment yet. Once u enters [u₉,u₁₀), the curve segment collapses (Figure (c)). Immediately after u leaving [u₉,u₁₀), a new convex hull appears (Figure (d)).

Figure (e) has P₅ collinear with its four successors. The curve contains one more line segment. Figure (f) has P₁₀ collinear with its five predecessors; however, it is moved to a position between P₈ and P₉. This would make part of the corresponding curve segment a straight line (why?)

2. Force a B-spline curve to pass a control point: let p adjacent control points be identical.

Consider control P_i. Since the curve segment on knot span [u_i, u_i+1) lies entirely in the convex hull defined by P_i, ..., P_i-p+1,P_i-p, if we make the first p control point identical (i.e., P_i = P_i-1 = ... = P_i-p+1), the convex hull collapses to a line segment P_i-pP_i and the curve must pass P_i.

The curve in the left figure above is of degree 3. If P₅ is moved and made identical with P₆, the curve is moved closer to P₆ but not passing though it yet. This is shown in the middle figure. Note that the number of curve segments is not changed due to this move; however, the little triangle marker near to P₅ is move closer to P₆. If P₄ is moved and made identical to P₆ = P₅, the curve passes through P₆ and the point that corresponds to a knot becomes identical to control point P₄ due to this move.

3. Force a B-spline curve to be tangent to a leg of control polyline: let P_i-p, P_i-p+1 = P_i-p+2 = .... = P_i-1 = P_i and P_i+1 be collinear.

In the above, p adjacent control points are made identical. At that control point, the continuity is C⁰ because the curve has a cusp (see the right figure above). However, a B-spline curve is C^p-1 at simple knots and infinitely differentiable at other places, the curve is C^p-1 continuous at control point P_i (the collapsed control point renumbered to i) on leg P_i-pP_i and is also C^p-1 continuous at control point P_i on leg P_iP_i+1. Therefore, if we make control points P_i-p, P_i and P_i+1 collinear, as long as the two adjacent curve segments do not have a cusp at the knot, they are C^p-1 continuous at P_i.

In the above figure figures, the curve is of degree 2. If we make control points 2, 3, 4 and 5 collinear and 3 and 4 identical, we have the right figure. The collinearity makes sure the curve segment lies on the line while the identical control points enforce the C^3-1 = C² continuous.

B-spline Curves: Modifying Knots

Because a B-spline curve is the composition of a number of curve segments, each of which is defined on a knot span, modifying the position of one or more knots will change the association between curve segments and knot spans and hence change the shape of the curve.

The following figures depict the effect of modifying a single knot. It is a B-spline curve of degree 6 with 17 knots with the first seven and last seven clamped at the end points, while the internal knots are 0.25, 0.5 and 0.75. The initial curve is shown in the left. If knot 0.25 is moved to 0.1, the shape of the curve changes and the original C(0.25) moves downward to a new position. If knot 0.5 is moved to 0.1 so that knot 0.1 becomes a double knot (with multiplicity 2), the shape of the curve moves to the left; but C(0.1) is moved upward to a position near to the original point (i.e., the original C(0.25)). The result is shown in the right figure. Moreover, even though we have a double knot at 0.1 and another knot at 0.75 that unevenly subdivide the domain [0,1] into three knot spans, the B-spline curve is more or less evenly subdivided by their corresponding points.

The following figure shows the change of shape of three curves, each of which is defined by 10 (n=9) control points and is of degree 6. Their internal knot vectors are (0.25,0.5,0.75) - red curve, (0.25,0.25,0.75) - blue curve, and (0.25,0.25,0.25) - black curve.

Practical experience shows that modifying knot positions is neither predictable nor satisfactory. More precisely, because it is not clear how the shape of a B-spline curve will respond to the change of the knot vector, modifying the shape of B-spline curve by changing knots is usually unsatisfactory and difficult to achieve the desired goal.

A Note about Multiple Knots

Multiple knots may help to generate expect/desirable results. Recall from a property of multiple knots discussed earlier that increasing the multiplicity of an internal knot decreases the number of non-zero basis functions at this knot. In fact, if the multiplicity of this knot is k, there are at most p - k + 1 non-zero functions at this knot. Moreover, the basis functions are C^p-k continuous at this knot.

Suppose a knot has multiplicity p-k, there will be k+1 non-zero basis functions at this knot and the corresponding point on the curve lies in the convex hull defined by the control points that correspond to these non-zero basis functions. If k = p - 1, there are two non-zero functions and the corresponding convex hull is a line segment.

If k = p, there is only one non-zero basis function at this knot and there is only one control point has non-zero coefficient. As a result, the curve passes through this point!

 

In Figure (a) above, which shows a B-spline curve of degree 5, the knot that corresponds to the marked knot point is moved to its previous knot, creating a knot of multiplicity two. The result is in Figure (b), which does not show much difference from the original. Then, the next knot (marked with a rectangle) is moved to the resulting knot (marked with an ellipse) again, creating a knot of multiplicity three. This is in Figure (c). The resulting curve moves towards a leg of the control polyline. Moving one more knot creates a new knot of multiplicity four. This forces the corresponding point (marked with an ellipse) lies on a leg. Finally, the only remaining knot is moved to combined with the other knots. Since its multiplicity is five and p=5, there is only one non-zero coefficient and hence forces the curve to pass that control point. As shown in Figure (e), that control point is P₅.

Derivatives of a B-spline Curve

Although B-spline curves are more complicated than Bézier curves, their derivatives share a very similar form. Suppose a B-spline curve is defined as follows:

The derivative of each of these basis functions can be computed as follows:

Plugging these derivatives back to the curve equation yields the following result:

where Q_i's are defined as follows:

Therefore, the derivative of a B-spline curve is another B-spline curve of degree p - 1 on the original knot vector with a new set of n control points Q₀, Q₁, ..., Q_n-1.

If the original clamped knot vector is u₀(p+1), u_p+1, ..., u_m-p-1, u_m(p+1), then removing the first and the last knots so that the multiplicity of the first and the last knots become p rather than p+1, we have a new knot sequence of m - 1 knots u₀(p), u_p+1, ..., u_m-p-1, u_m(p). Then, it can be shown that N_i+1,p-1(u) evaluated on the original knot sequence is equal to N_i,p-1(u) on the new one. Therefore, on the new knot sequence the derivative of a B-spline curve is the following:

In the following left is a B-spline curve of degree 5. Its derivative curve, which is a B-spline curve of degree p-1 defined by the new n control points, is shown in the middle. As in the Bézier curve case, this is the hodograph of the original curve. Below right shows the same hodograph with control polyline removed.

Clamped B-spline Curves

We know that a clamped B-spline curve passes through the first and the last control points. In fact, it is also tangent to the first and last legs of its control polyline. Recall from above that the derivative of a B-spline curve C(u) of degree p is

whose knot vector is obtained by dropping the first knot and last knot from the original knot sequence. Thus, the multiplicity of the first (and of course the last) knot is p and, consequently, the above B-spline curve of degree p-1 is clamped. Since a clamped B-spline curve passes through its first and last control points, we have C'(0) = Q₀ and C'(1) = Q_n-1. Since u₀ = .... = u_p = 0 for i = 0, we have

Therefore, the tangent vector at C'(0) is in the same direction of the vector from P₀ to P₁ and C(u) is tangent to the first leg.

With the same reasoning, we can show the following:

Hence, C(u) is tangent to the last leg. In summary, we have the following important fact:

Higher Derivatives

Since the first derivative of a B-spline curve is another B-spline curve, recursively applying this technique one can compute higher derivatives without any difficulty.

B-spline Curves: Knot Insertion

The meaning of knot insertion is adding a new knot into the existing knot vector without changing the shape of the curve. This new knot may be equal to an existing knot and, in this case, the multiplicity of that knot is increased by one. Because of the fundamental equality m = n + p + 1, after adding a new knot, the value of m is increased by one and, consequently, either the number of control points or the degree of the curve must also be increased by one. Changing the degree of the curve due to the increase of knots will change the shape of the curve globally and will not be considered. Therefore, inserting a new knot causes a new control point to be added. In fact, some existing control points are removed and replaced with new ones by corner cutting.

Although knot insertion looks like not very interesting, it is one of the most important algorithms for B-spline curves since many other useful algorithms are based on knot insertion. Therefore, we shall start important algorithms with knot insertion. In the following, we shall present an algorithm for inserting a single knot, followed by an algorithm for inserting a single knot multiple times.

The left figure below shows a clamped B-spline curve of degree 4 with uniform knots, while the right figure shows the result after a new knot u = 0.5 is inserted. The left figure also shows the control polylines before and after the insertion. As you can see, the shape of the curve does not change. However, the defining control polyline is changed. In fact, four new control points in red replace the original control points P₄, P₅ and P₆, and three line segments in yellow cut the corners at P₄, P₅ and P₆.

Inserting a Single Knot

Given a set of n+1 control points P₀, P₁, ..., P_n, a knot vector of m+1 knots U = { u₀, u₁, ..., u_m } and a degree p, we want to insert a new knot t into the knot vector without changing the shape of the B-spline curve C(u).

Suppose the new knot t lies in knot span [u_k, u_k+1). From the strong convex hull property, C(t) lies in the convex hull defined by control points P_k, P_k-1, ..., P_k-p and the basis functions of all other control points are zero. Thus, the knot insertion computation can be restricted on control points P_k, P_k-1, ..., P_k-p. The way of inserting t is to find p new control points Q_k on leg P_k-1P_k, Q_k-1 on leg P_k-2P_k-1, ..., and Q_k-p+1 on leg P_k-pP_k-p+1 such that the old polyline between P_k-p and P_k (in black below) is replaced by P_k-pQ_k-p+1...Q_kP_k (in orange below) by cutting the corners at P_k-p+1, ..., P_k-1. All other control points are unchanged. Note that p-1 control points of the original control polyline are removed and replaced with p new control points.

Fortunately, the positions of new control points Q_i's are easy to compute. The formula for computing the new control point Q_i on leg P_i-1P_i is the following:

where the ratio a_i is computed as below:

In summary, to insert a new knot t, we first find the knot span [u_k, u_k+1) that contains t. With k available, p new control points Q_k-p+1, ..., Q_k are computed with the above formula. Finally, the original control polyline between P_k-p and P_k is replaced with the new polyline defined by P_k-p, Q_k-p+1, Q_k-p+2, ..., Q_k-1, Q_k and P_k. Note that after inserting a new knot, the knot vector becomes u₀, u₁, ..., u_k, t, u_k+1, ..., and u_m. If the new knot t is equal to u_k, the multiplicity of u_k is increased by one.

The above computation scheme can be illustrated with the following diagram. First, the affected control points are listed on the left column. Then, the computed new control points are listed on the second column. Note that the number of new control points is one less than the affected control points. The computation of new control point Q_i, where k-p+1 <= i <= k, requires two original control points P_i-1 and P_i with coefficients 1-a_i and a_i, respectively. After the computation, use the points surrounded by the blue dotted line to replace those not in the region. All unaffected control points are preserved. Therefore, the original set of control points P_k-p, P_k-p+1, ..., P_k-1, P_k is replaced with P_k-p, Q_k-p+1, ..., Q_k-1, P_k.

Let us take a look at a geometric interpretation of a_i. From its definition, a_i:1-a_i is the ratio of dividing interval [u_i, u_i+p) by the value of t as shown below:

There are k a_i's, each of which covers p knot spans (i.e., [u_i, u_i+p)). If we stack these intervals together and align them at the value of t, we have the following diagram:

Therefore, the position of t divides knot spans [u_k, u_k+p), [u_k-1, u_k+p-1), ..., [u_k-p+1, u_k+1) into ratios a_k, a_k-1, ...,, a_k-p+1, which, in turn, provide the ratios for dividing legs P_kP_k-1, P_k-1P_k-2, ... P_k-pP_k-p+1.

Example 1: Inserting a Knot in a Knot Span

Suppose we have a B-spline curve of degree 3 with a knot vector as follows:

We want to insert a new knot t = 0.5. Since t = 0.5 lies in knot span [u₅,u₆), the affected control points are P₅, P₄, P₃ and P₂. To determine the three new control points Q₅, Q₄ and Q₃, we need to compute a₅, a₄ and a₃ as follows:

The three new control points are

The new control polyline becomes P₀, P₁, P₂, Q₃, Q₄, Q₅, P₅, ...., and the new knot vector is

Since the original B-spline curve has p = 3 and m = 11, we have n = m - p - 1 = 11 - 3 - 1 = 7 and hence 8 control points. The following is a B-spline curve satisfying this condition and its basis functions:

The three blue rectangles are Q₃, Q₄ and Q₅. After inserting t = 0.5, the corners at P₃ and P₄ are cut, yielding the following B-spline curve and its basis functions. Note that the shape of the curve does not change:

The following diagram shows the relationship between the old and new control points. Note that the new set of control points contains P₀, P₁, P₂, Q₃, Q₄, Q₅, P₅, P₆ and P₇.

The relationship among a_j's, u_j's, and t are shown below:

Example 2: Inserting a Knot at an Existing Simple Knot

Suppose we have a knot vector as follows:

We want to insert a new knot t = 0.5, which is equal to an existing one (i.e., t = u₈ = 0.5). The following is a B-spline curve of degree 4 and its basis functions before the new knot t is inserted.

Since t is in [u₈,u₉), the affected control points are P₈, P₇, P₆, P₅ and P₄. The coefficients are computed as follows:

The new control points are

The new control point Q₈ is equal to the original control point P₇. In fact, if t is equal to a knot, say u_k, then

Consequently, we have

That is, if the new knot t to be inserted is equal to an existing simple knot u_k, then Q_k, the last new control point, is equal to P_k-1. The following diagram shows the computation scheme:

The figure shown at the beginning of this example shows the new control points and the new control polyline in orange, Note that the new control points are P₀, P₁, P₂, P₃, P₄, Q₅, Q₆, Q₇, Q₈ = P₇, P₈, P₉, P₁₀ and P₁₁. The curve and its basis functions after the new knot t = 0.5 is inserted is shown below.

The relationship among a_j's, u_j's, and t are shown below:

Example 3: Inserting a Knot at an Existing Multiple Knot

What if the new knot t is inserted at a multiple knot? Suppose t is inserted at knot u_k of multiplicity s. Hence, we have s consecutive equal knots: u_k = u_k-1 = u_k-2 = .... = u_k-s+1 and u_k-s+1 being not equal to u_k-s. In the computation of coefficients a_k, ...., a_k-p+1, we have the following:

Hence, coefficients a_k, ...., a_k-p+1 are all zero and, consequently, we have

This shows that if the new knot t is inserted at a knot u_k of multiplicity s, then the last s new control points, Q_k, Q_k-1, ..., Q_k-s+1 are equal to the original control points P_k-1, P_k-2, ..., P_k-s. If s = 1 (i.e., simple knot), Q_k is equal to P_k-1, which is exactly what is discussed in Example 2. If s = 0 (i.e., t is not a knot), then all control points from P_k-p to P_k are involved. This is the case of Example 1. The following diagram shows the computation scheme:

B-spline Curves: Inserting a Knot Multiple Times

In many applications, a knot is required to be inserted multiple times. A simple method for inserting the same knot multiple times is to repeatedly apply the knot insertion algorithm. However, in doing so, the original knot vector and the original set of control points must be modified after each insertion, which is a rather tedious task. Fortunately, by studying the behavior of the knot insertion algorithm, we can find a much simpler way to do the same.

Observation I: The Coefficients for Computing the New Control Points

Let us start with a simple case. Let t be inserted in the middle of knot span [u_k, u_k+1) and let the degree be p. The coefficients a_i,1's for the first insertion, where k-p+1 <= i <= k, are computed as follows:

After t is inserted, it becomes a knot and knots u_k+1, u_k+2, ..., u_m will be shifted one position to the right. More precisely, the new knots, v₀, v₁, ..., v_k, v_k+1, ..., v_m and v_m+1 are

Note that v_k+1 divides the new knot vector into two halves. Knots to the left of v_k+1 = t are identical to the corresponding values of the original, while knots to the right of t satisfy the relation v_h = u_h-1.

If t is inserted again, it lies in knot span [v_k+1,v_k+2). Since t is equal to the left end, this second insertion makes v_{k+1 a double knot. The coefficients ai,2}'s for this second insertion, based on the new knot sequence, are computed as

where i is less than or equal to k+1. Rewriting the above using u we have

Note that the u_i's are on the left-hand side of t = v_k+1 and the u_i+p's are on the right-hand side of v = v_k+1.

Let this new set of knots be w_i's. The relation of this new set and the origin is shown below:

Let t be inserted a third time, which makes w_{k+1 a triple knot. It is not difficult to see that the coefficients ai,3}'s for this third insertion are computed as follows:

The above can be rewritten as

Generalizing this idea, a_i,h's, the coefficients for the h-th insertion, are computed as follows:

What if in the original knot vector u_k is a multiple knot with multiplicity s and t is inserted at u_k? Would this affect the above formula? Fortunately, nothing will change. Let us see why. If u_k is a multiple knot of multiplicity s, then u_k = u_k-1 = u_k-2 = ... = u_k-s+1:

Because all of them lie to the left-hand side of t and because the shifting of indices only happen to those knots to right of t, the computation formula for a_i,h does not have to be modified. Therefore, we conclude that

Observation II: The Computation of New Control Points

Recall from the way of inserting a knot at an existing knot that if t is inserted at an existing knot u_k of multiplicity s, then control points P_k-s, P_k-s+1, ..., P_k-1 and P_k are not affected and only P_k-p, P_k-p+1, ..., P_k-s participate in the computation of new control points Q_i's. Let us rewrite all new control points after the first insertion with a second subscript 1. Thus, we have the following diagram:

If the same knot is inserted the second time, the affected p+1 control points are P_k, P_k-1, P_k-s, P_k-s,1, P_k-s-1,1, ..., P_k-p+1,1 as shown in the above diagram. Note that P_k-p is excluded because only p+1 control points are affected. However, since the multiplicity of t is increased by one due to the previous insertion, s+2 control points will not participate in the knot insertion computation: P_k, P_k-1, ..., P_k-s and P_k-s,1. The computation scheme and the new set of control points are shown below. Note that new control points generated from the second insertion has 2 as the second subscript. The new control points are: (1) P_k-p+1,1 and P_k-s,1 computed from the first insertion, and (2) P_k-p+2,2 to P_k-s,2 computed from the second insertion.

For the third insertion, the affected p+1 control points are P_k-p+2,2 to P_k-s,2, P_k-s,1, and P_k-s to P_k. Since this third insertion increases the multiplicity of t by one again, the number of control points that will not involve in the computation is also increased by one. As a result, P_k-s,2 will be the same before and after the third insertion. This is the meaning of the following diagram:

In general, if t is inserted h times at a knots u_k of multiplicity s, where s = 0 means t is inserted in the middle of that knot span and s > 0 means t is inserted at a knot u_k of multiplicity s, one can

1. write down the first set of p+1 affected control points as the 0-th column;
2. ignore the last s control points (i.e., P_k-s+1 to P_k);
3. compute the first column, the second column, ... and the h-th column;
4. the new set of control points are those surrounded by the blue polygon

A Summary

Combining these two observations, we have the following algorithm for inserting a knot t multiple times.

Input: knot t in [u_k, u_k+1) with initial multiplicity s to be inserted h times, where h+s is less than or equal to p, the degree of the given B-spline curve
Output: a new set of control points after t is inserted h times

Let control points P_k, P_k-1, ..., P_k-p be renamed as P_k,0, P_k-1,0, ..., P_k-p,0 by adding a second subscript 0.

for r := 1 to h do

for i := k-p+r to k-s do

begin

Let a_i,r = (t - u_i) / ( u_i+p-r+1 - u_i )
Let P_i,r = (1 - a_i,r) P_i-1,r-1 + a_i,r P_i,r-1

end

The new set of control points are constructed from the original ones from P₀ to P_k-p, followed by the top edge of the diagram above (i.e., P_k-p+1,1, P_k-p+2,2, ..., P_k-p+h,h), followed by the right edge of the diagram (i.e., P_k-p+h+1,h, P_k-p+h+2,h, ...., P_k-s,h), followed by the bottom edge of the diagram (i.e., P_k-s,h-1, P_k-s,h-2, ...., P_k-s,1), followed by the original control points P_k-s, ..., P_k, ..., P_n.

Corner Cutting

As mentioned earlier, knot insertion is a corner cutting process. For example, suppose we have a B-spline curve of degree 6 and want to insert u twice at a knot u₁₀ of multiplicity 2. The affected control points are P₁₀, P₉, ..., P₄, since k = 10, p = 6 and k-p = 4. Since the multiplicity of u₁₀ is 2, we have s = 2 and u₁₀ and P₉ are not changed. The first insertion produces P_8,1, P_7,1, P_6,1 and P_5,1 and the corners at P₇, P₆ and P₅ are cut. The new set of control points contains P₀ to P₄, P_5,1, P_6,1, P_7,1, P_8,1, P₈, P₉, P₁₀, .....

The second insertion produces P_8,2, P_7,2 and P_6,2. Thus, the corners at P_7,1 and P_6,1 are cut and the new set of control points are P₀ to P₄, P_5,1, P_6,2, P_7,2, P_8,2, P_8,1, P₈, P₉, P₁₀, .....

De Boor's Algorithm

De Boor's algorithm is a generalization of de Casteljau's algorithm. It provides a fast and numerically stable way for finding a point on a B-spline curve given a u in the domain.

Recall from a property of multiple knots that increasing the multiplicity of an internal knot decreases the number of non-zero basis functions at this knot. In fact, if the multiplicity of this knot is k, there are at most p - k + 1 non-zero basis functions at this knot. Consequently, at a knot of multiplicity p, there will be only one non-zero basis function whose value at this knot is one because of the property of partition of unity. Let this knot be u_i. If u is u_i, since N_i,p(u) is non-zero on [u_i,u_i+1), the point on the curve C(u) is affected by exactly one control point P_i. More precisely, we actually have C(u) = N_i,p(u) P_i = P_i!

So, what is the point of this interesting or somewhat strange property? Simple: if a knot u is inserted repeatedly so that its multiplicity is p, the last generated new control point is the point on the curve that corresponds to u. Why is this so? After inserting u multiple times, making its multiplicity p, the triangular computation scheme yields one point. Because the given B-spline curve must pass this new point, it is the point on the curve corresponding to u. This observation provides us with a technique for finding C(u) on the curve. We just insert u until its multiplicity becomes p and the last point is C(u)!

Let us take a look at an example before move on. Figure (a) is a B-spline curve of degree 4 defined by 7 control point. To compute C(0.9), where 0.9 is not a knot, u = 0.9 is inserted 4 (the degree) times. Figure (b) and Figure (c) show the results after the first and second insertion. Thus, two new control points are added near the lower right corner. Note that the control polyline is closer to the curve than the original. The result of the third insertion is shown in Figure (d). The fourth insertion yields the point on the curve (Figure (e)). Therefore, after four insertions, C(0.9) is a control point.

 

The general knot insertion algorithm discussed on the previous page can easily be modified to fulfill our purpose. First note that we only need to insert u enough number of times so that u becomes a knot of multiplicity p. If u is already a knot of multiplicity s, then inserting it p - s times would be sufficient.

Input: a value u
Output: the point on the curve, C(u)

If u lies in [u_k,u_k+1) and u != u_k, let h = p (i.e., inserting u p times) and s = 0;
If u = u_k and u_k is a knot of multiplicity s, let h = p - s (i.e., inserting u p - s times);
Copy the affected control points P_k-s, P_k-s-1, P_k-s-2, ..., P_k-p+1 and P_k-p to a new array and rename them as P_k-s,0, P_k-s-1,0, P_k-s-2,0, ..., P_k-p+1,0;

for r := 1 to h do

for i := k-p+r to k-s do

begin

Let a_i,r = (u - u_i) / ( u_i+p-r+1 - u_i )
Let P_i,r = (1 - a_i,r) P_i-1,r-1 + a_i,r P_i,r-1

end

P_k-s,p-s is the point C(u).

In the left diagram below, all P_i,0's are on the left column. From the 0-th column and coefficients a_i,1, one can compute P_i,1's. From this first column and coefficients a_i,2's, the second column is computed and so on. Since there are (k-s)-(k-p)+1 = p-s+1 points on the zero-th column and since each column has one point less than the previous one, it takes p-s columns to reduce the number of points on a column to 1. This is why the last point is P_k-s,p-s. The right diagram shows the corner-cutting process.

Although this process looks like the one obtained from de Casteljau's algorithm, they are very different. First, under de Casteljau's algorithm, the dividing points are computed with a pair of numbers 1 - u and u that never change throughout the computation procedure, while under de Boor's algorithm these pairs of numbers are different and depend on the column number and control point number. Second, in de Boor's algorithm only p+1 affected control points are involved in the computation, while de Casteljau's algorithm uses all control points. Since control points P_k-p to P_k define a convex hull that contains the curve segment on knot span [u_k, u_k+1), the computation of de Boor's algorithm is performed within the corresponding convex hull.

An Example

Suppose we have a B-spline curve of degree 3 (i.e., p = 3) defined by seven control points P₀, ..., P₆ (i.e., n = 6) and the following knot vector of 11 knots (i.e., m = 10):

Based on this information, we shall compute P(0.4). For de Boor's algorithm, this is equivalent to inserting u = 0.4 three times. Since u = 0.4 is not an existing knot, s = 0 and u = 0.4 is in [u₄, u₅), the affected control points are P₄, P₃, P₂ and P₁. The following is the computation scheme:

Let us compute the second column. The involved a coefficients are

The first column is computed as follows:

To compute the second column, we need the following coefficients:

The points are

Finally, since

the final point is

This is the point on the curve corresponding to u = 0.4.

Notice the similarity of the intermediate polylines generated by de Boor's algorithm and those generated by de Casteljau's algorithm. Also note that u is not a knot in this example. If u is a knot, the computation will be easier since we will have fewer number of affected control points.

De Casteljau's and de Boor's Algorithms

Because a Bézier curve is a B-spline curve in a special form and because de Boor's algorithm works very similar to de Casteljau's algorithm, we expect that the latter may be a special case of the former. This indeed is the case.

Suppose we have a B-spline curve C(u) of degree n defined by n+1 control points P₀, ..., P_n and a knot vector of p+1 0's followed by p+1 1's. We discussed on a previous page that C(u) is actually a Bézier curve of degree n.

Consider the computation steps of de Boor's algorithm. We already know C(0) = P₀ and C(1) = P_n. What we need to show is that de Boor's algorithm and de Casteljau's algorithm act the same way and compute the same result for every u. Let the knots be u₀ = u₁ = ... = u_n = 0 and u_n+1 = u_n+2 = ... = u_2n+1 = 1. Given any u in (0,1), it is in [u_n, u_n+1). Consequently, the control points that involve in the knot insertion computation are P_n, ..., P_n-n = P₀, and the intervals used for calculating the a_i's are [u_n, u_n+n) = [0,1), [u_n-1, u_n+n-1) = [0,1), ..., and [u_n-n+1, u_n+1) = [0,1). Therefore, for each i, we have

Since each leg is divided with a ratio of a_i:1-a_i, the above expression shows that in this special case the dividing ratio is all the same and is equal to u:1-u. Thus, the first knot insertion in de Boor's algorithm computes exactly the first column in de Casteljau's algorithm.

A similar argument shows that the dividing ratio in all subsequent insertion steps is also equal to u:1-u. Consequently, in this special case, the computation steps of de Boor's algorithm are exactly identical to the corresponding steps of de Casteljau's algorithm. Therefore, de Boor's algorithm reduces to de Casteljau's algorithm when the knot vector has only two knots of multiplicity n+1.

B-spline Curves: Subdividing a B-spline Curve

Subdividing a B-spline curve follows exactly the same procedure for subdividing a Bézier curve. However, de Boor's algorithm will be used.

Selecting Control Points

Suppose we want to subdivide a B-spline curve at u into two B-spline curves, one on [0,u] and the other on [u,1]. The first thing to do is to apply de Boor's algorithm at u. Note that if u is in [u_k, u_k+1), then at most p+1 control points will be used in the computation, namely: P_k, P_k-1, ..., P_k-p. To find the control points of the B-spline curve on [0,u], we start with P₀ and follow the control polyline. When we encounter a control point or a point computed in the process of de Boor's algorithm, we select that point and make a turn. This process continues until we reach C(u) which is also selected as a control point. These points, in the visiting order, form the control points that define the B-spline curve on [0,u]. For the B-spline curve defined on [u,1], we start with the point C(u) and apply the same process. We select each encountered point and make a turn until P_n is reached. Note that this order is important!!!

The following shows a B-spline curve of degree 3 defined by 11 (n = 10) control points. Suppose we wish to subdivide this curve at u = 0.5. The computation process of C(0.5) using de Boor's algorithm generates a de Boor net. In the figure below, points on column 0 are marked with circles, points on column 1 are marked with squares, points on column 2 are marked with triangles, points on column 3 are marked with pentagons, and the point on the curve C(u) is on column 4. Therefore, the control points of the B-spline curve on [0,u] are P₀, P₁, P₂, P₃, P₄, a (take a turn), b (take a turn), c (take a turn), and C(0.5). The control points of the B-spline curve defined on [u,1] are C(0.5), d (take a turn), e (take a turn), f (take a turn), P₈, P₉ and P₁₀.

Thus, the control points for the curve on [0,u] include the original unaffected control points and the first point of each polyline of the de Boor net. Similarly, the control points for the curve on [u,1] consists of the last point of each polyline of the de Boor net, followed by the other unaffected control points. Since the first and last points of a polyline of a de Boor net are the first and last points on the same column, they can be extracted once a column is completely computed.

In the following diagram showing the triangular computation scheme of de Boor's algorithm, we can immediately extract P_k-p (curve on [0,u]) and P_k-s (curve on [u,1]). Once column 1 is computed, we can extract P_k-p+1,1 (curve on [0,u]) and P_k-s,1 (curve on [u,1]). After column 2 is computed, we can extract P_k-p+2,2 (curve on [0,u]) and P_k-s,2 (curve on [u,1]). This process continues until we reach P_k-s,p-s = C(u) which will be selected for both curves. Thus, graphically, points on the upper edge of the wedge from P₀ to P_k-s,p-s form the control points of the curve on [0,u], and points on the lower edge from P_k-s,p-s to P_n form the control points of the curve on [u,0].

Selecting Knots

The knot vector for the curve on [0,u] includes all knots in [0,u) followed by p+1 copies of u, and the knot vector for the curve on [u,1] includes p+1 copies of u followed by all knots in (u,1].

For example, if the original knot vector of a B-spline curve of degree 4 is { 0(5), 0.3, 0.4, 0.6, 0.7, 0.85, 0.9, 1(5) }. If the curve is divided at u = 0.65, the curve on [0,0.65] has a knot vector { 0(5), 0.3, 0.4, 0.6, 0.65(5) } and the curve on [0.65, 1] has a knot vector { 0.65(5), 0.7, 0.85, 0.9, 1(5) }.

It can be shown that the component curves constructed this way are also B-spline curves with the original degree and are part of the original curve on [0,u] and [u,1].

Subdividing a B-spline Curve into Bézier Curve Segments

If a B-spline curve of degree p is subdivided at its knots, then each curve segment becomes a Bézier curve of degree p. The following figures show an example. Figure (a) is a B-spline curve of degree 4 defined by 7 (n = 6) control points and knot vector { 0(5), 1/3, 2/3, 1(5) }. Figure (b) shows the de Boor net at u = 1/3 and Figure (c) shows the selected control points after the subdivision completes. The curve segment on [0,1/3] is now a Bézier curve of degree 3, while the second curve segment on [2/3,1] is still a B-spline curve of degree 4 defined by 6 (n = 5) control points and a knot vector { 1/3(5), 2/3, 1(5) }. Figure (d) shows the de Boor net at u = 2/3 and Figure (e) shows the subdivided curves, one on [1/3,2/3] and the other on [2/3,1]. Finally, Figure (f) shows the original control polyline and the control polylines of the three Bézier segments. The original B-spline curve has 7 control points. However, the total number of control points for the three Bézier curves is 13! It is almost doubled.

Why is each segment a Bézier curve? Since the given B-spline curve is subdivided at its knots, each curve segment has no internal knots. Moreover, the subdivision process makes the internal knots to have multiplicity p+1, and the curve segment is "clamped" at the first and last control points of each curve segment. From a previous page, we know that these curve segments must be Bézier curves.

In the process of subdividing a B-spline curve, a large number of control points will be introduced. Therefore, manipulating a B-spline curve is easier than manipulating its component Bézier curves. Moreover, the B-spline curve is C^p-k continuous at a knot point, where k is the multiplicity of the corresponding knot. When we manipulate a B-spline curve by moving control points, this continuity is always maintained. However, if a B-spline curve is subdivided into a sequence of Bézier curves, maintaining the continuity at the joining control points would be a challenging task. Consequently, handling a B-spline curve is much easier than handling a sequence of Bézier curves.

Problems

• B-spline Basis Functions
  1. Compute and plot all basis functions up to degree 2 for knot vector U = { 0, 1, 2, 3, 4 }.
  2. Compute and plot all basis functions up to degree 2 for knot vector U = { 0, 1, 2, 3, 3, 3, 4, 5, 6 }.
  3. Verify the following propositions with convincing arguments:
     • N_i,p(u) is a degree p polynomial.
     • For all i, p and u, N_i,p(u) is non-negative.
  4. Given knot sequences U₁ = { 0, 0, 1, 1 } and U₂ = { 0, 0, 0, 1, 1, 1 }, use hand calculation to verify that the B-spline basis functions on U₁ and U₂ are identical to the Bézier basis functions.
• B-spline Curves
  1. Show that a clamped B-spline curve passes through the first and last control points. More precisely, show that C(0) = P₀ and C(1) = P_n hold.
  2. In the discussion of forcing a B-spline to pass through a control point, we indicated that if we let P_i = P_i-1 = ... = P_i-p+1, the convex hull collapses to a line segment P_i-pP_i and the curve must pass through P_i. Why is this so?
  3. In the discussion of forcing a B-spline to pass a control point, we indicated that a point on the curve that corresponds to a knot may become identical to the collapsed control point. If we let P_i = P_i-1 = ... = P_i-p+1, will you be able to identify the knot u_k such that P(u_k) becomes identical to P_i? Why? Elaborate your finding.
  4. In the discussion of multiple knots, we mentioned that if a knot u_i has multiplicity k-1, where k is the degree of a B-spline curve, then C(u_i) lies on a leg of the control polyline. Based on your understanding of multiple knots, answer the following questions:

1.  Why does this proposition hold?

2.  On which leg does C(u_i) lie?

5. Consider a clamped cubic B-spline curve defined by seven control points P₀, ..., P₆ and knot vector U = { 0, 0, 0, 0, 2/5, 3/5, 3/5, 1, 1, 1, 1 }. Find its derivative B-spline curve, its new control points and knot vector.
6. Modify the derivative computation method so that it works for open and closed B-spline curves.
7. Use B-spline curves of degree 2 and 3 and hand calculation to verify that de Boor's algorithms reduces to de Casteljau's algorithm.
8. Suppose we have a clamped B-spline curve of degree p defined by n+1 control points and a knot vector of simple knots except for the first and last knots which are of multiplicity p+1. Derive a relation of the number of control points between the given B-spline curve and the number of control points of its Bézier curve segments.

References

• Gerald Farin, Curves and Surfaces for CAGD: A Practical Guide, fourth edition, Academic Press, 1997.
• Josef Hoschek and Dieter Lasser, Fundamentals of Computer Aided Geometric Design, translated from the German 1989 edition by Larry L. Schumaker, A K Peters, 1993.
• Les Piegl and Wayne Tiller, The NURBS Book, second edition, Springer-Verlag, 1997.
• David F. Rogers and J. Alan Adams, Mathematical Elements for Computer Graphics, second edition, McGraw-Hill, 1990.

 

posted on 2007-06-25 18:34 zmj 阅读(3001) 评论(0)  编辑 收藏 引用