B-spline Basis Functions: Definition

浅浅的花香味﹌ 2022-12-20 05:36 107阅读 0赞

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*0 <= *u*2 <= *u*3 <= ... <= *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.*, *ui* = *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*0, *u**m*\] into knot spans. All B-spline basis functions are supposed to have their domain on \[*u*0, *u**m*\]. In this note, we use *u*0 = 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:

![e46022e35b491d364dfdbb76d1636af5.png][]

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 = 0, *u*1 = 1, *u*2 = 2 and *u*3 = 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:

![158c208d13ed0c4cc08e9ce9121666c8.png][]

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.

![599a74148e88a7a2245fde37f5f2e908.png][]

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*) and*N*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

![85f12c56951795715b4732216b14f244.png][]

Since *u*0 = 0, *u*1 = 1 and *u*2 = 2, the above becomes

![61dff2559e1692d7bba22da2b3f3ecf3.png][]

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 *u**N*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)).

![dfce5412aa9cb270acf1769ddf85726e.png][]

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:

![809319d6d25d9df3773eb96359aab7bf.png][]

Plugging in the values of the knots yields

![1d962dd75bd5f9b28ce6b52590dea52e.png][]

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
    
    ![a3658e310c930b34314e0cfbb1d6b226.png][]
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
    
    ![719f832ddb0d3536c716a469f6444559.png][]
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
    
    ![d7ecf4c0a1042f5e1cdfb92ba9a38b6e.png][]

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.

![a3dd2a8e45b19f31e77b195c745f6a6b.png][]

![bf0067a8c9715926accef4c818b3d95d.gif][]

### 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*1, *u*2), \[*u*2, *u*3), \[*u*3, *u*4) and \[*u*4, *u*5). Or, equivalently, it is non-zero on \[*u*1, *u*5).

![cf236a80e3d178e03e107f268b11f8b5.png][]

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*).

![54f7647f6f187461c3e819e079b1691f.png][]

Let us take a look at the above diagram. To find all degree 3 basis functions that are non-zero on \[*u*4, *u*5), 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*3, *u*4) (*resp.*, \[*u*2, *u*3) ). Note that there are only three degree three basis polynomials that are non-zero on \[*u*2, *u*3).

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*),**

![bf0067a8c9715926accef4c818b3d95d.gif][]

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

![0695fae1cf8b339e6d7828be7fd7a246.png][]

[e46022e35b491d364dfdbb76d1636af5.png]: /images/20221120/5084426aeed24ddb94517ed0af04885c.png
[158c208d13ed0c4cc08e9ce9121666c8.png]: /images/20221120/dd885287fae54956952a1c0e9b2adb90.png
[599a74148e88a7a2245fde37f5f2e908.png]: https://img-blog.csdnimg.cn/img_convert/599a74148e88a7a2245fde37f5f2e908.png
[85f12c56951795715b4732216b14f244.png]: https://img-blog.csdnimg.cn/img_convert/85f12c56951795715b4732216b14f244.png
[61dff2559e1692d7bba22da2b3f3ecf3.png]: https://img-blog.csdnimg.cn/img_convert/61dff2559e1692d7bba22da2b3f3ecf3.png
[dfce5412aa9cb270acf1769ddf85726e.png]: https://img-blog.csdnimg.cn/img_convert/dfce5412aa9cb270acf1769ddf85726e.png
[809319d6d25d9df3773eb96359aab7bf.png]: https://img-blog.csdnimg.cn/img_convert/809319d6d25d9df3773eb96359aab7bf.png
[1d962dd75bd5f9b28ce6b52590dea52e.png]: https://img-blog.csdnimg.cn/img_convert/1d962dd75bd5f9b28ce6b52590dea52e.png
[a3658e310c930b34314e0cfbb1d6b226.png]: https://img-blog.csdnimg.cn/img_convert/a3658e310c930b34314e0cfbb1d6b226.png
[719f832ddb0d3536c716a469f6444559.png]: https://img-blog.csdnimg.cn/img_convert/719f832ddb0d3536c716a469f6444559.png
[d7ecf4c0a1042f5e1cdfb92ba9a38b6e.png]: https://img-blog.csdnimg.cn/img_convert/d7ecf4c0a1042f5e1cdfb92ba9a38b6e.png
[a3dd2a8e45b19f31e77b195c745f6a6b.png]: https://img-blog.csdnimg.cn/img_convert/a3dd2a8e45b19f31e77b195c745f6a6b.png
[bf0067a8c9715926accef4c818b3d95d.gif]: https://img-blog.csdnimg.cn/img_convert/bf0067a8c9715926accef4c818b3d95d.gif
[cf236a80e3d178e03e107f268b11f8b5.png]: https://img-blog.csdnimg.cn/img_convert/cf236a80e3d178e03e107f268b11f8b5.png
[54f7647f6f187461c3e819e079b1691f.png]: https://img-blog.csdnimg.cn/img_convert/54f7647f6f187461c3e819e079b1691f.png
[0695fae1cf8b339e6d7828be7fd7a246.png]: https://img-blog.csdnimg.cn/img_convert/0695fae1cf8b339e6d7828be7fd7a246.png