Converting B-spline curve to Bézier spline curve

1  Introduction

A non-periodic B-spline curve of order k with m control poles has m+k knots {tj}, known as the knot vector (or knot sequence). The knot vector has the following property:

t0=t1= = tk-1,    tk tk+1 tm-1,     tm=tm+1= = tm+k-1.
In practice, we call knots tj (j=k,,m-1) the interior knots. A B-spline curve whose interior knots all have multiplicity equal to k-1 is known as a composite Bézier curve (or a Bézier spline curve). Therefore, to convert a B-spline curve into a composite Bézier curve is equivalent to inserting knots into the knot vector repeatedly until all the interior knots have multiplicity equal to k-1.

Algorithm presented in this article is derived from Boehm's knot insertion method [1].

2  Inserting a single knot

Denoting the control poles and the knots of a given a B-spline curve by d0i and t0j, we may represent the B-spline curve as

r(t)= m-1

i=0 
N0i,k(t)d0i,
Inserting a new knot t in [t0r,t0r+1) forms a new knot sequence:

       t1j=t0j,     j=0,1,,r
       t1r+1=t
       t1j+1=t0j,     j=r+1,,m+k
which defines m+1 new basis functions Ni,k1(t). Now we want to write the given B-spline curve in terms of the new control poles di1 and the new basis functions, i.e.,

r(t)= m

i=0 
N1i,k(t)d1i.
Due to the local support property of a B-spline curve, it is known that the basis functions N00,k(t),,N0r-k+1,k(t) and N0r,k(t), ,N0m-1,k(t) are not affected. Therefore, we can derive that

       d1i = d0i,     i=0,,r-k+1

       d1i+1 = d0i,     i=r,,m-1

To compute k-1 affected poles d1r-k+2, ,d1r, we set

t=t1r+1=(1-ai)t0i+ai t0i+k-1=ti0+ai(ti+k-10-ti0).
Then, by the affine invariance, it follows

d1i=(1-ai)d0i-1+aid0i=di-10+ai(di0-di-10),     (i=r-k+2,,r)
with

ai= t - t0i
t0i+k-1-t0i
.

3  Inserting a knot multiple times

Inserting a knot for multiple times can be done repeatedly using the method discussed in the previous section. However, this approach is very inefficient since we have to repeatedly update the control poles and the knot vector after each knot insertion. In order to avoid repeatedly updating the control poles and knots, an improved method, also known as the blossoming algorithm, is used to insert a knot multiple times. Assume that we want to insert a knot t [t0r,t0r+1) into the existing knot vector for p times. The improved method is then summarized as follows:

  1. Copy the first part of unaffected poles:

    dpi=d0i,    i=0,1, ,r-k+1.

  2. Compute k+p-2 affected poles dr-k+2p, , dr+p-1p:

    We use a temporary array bij to store the intermediate results. So,

        bi0 = di0,     i=r-k+1,, r
        do j=1, p
              do i=r-k+1+j, r
                    a = (t-t0i)/(t0i+k-j-t0i)
                    bij=bi-1j-1+a(bij-1-bi-1j-1)
              enddo
        enddo

    When completed, we have the following intermediate results:

    j=1
    b1r-k+2
    b1r-k+3
    b1r-k+4
    b1r
    j=2
    b2r-k+3
    b2r-k+4
    b2r
    ·
    ·
    ·
    ·
    j=p
    bpr-k+p+1
    bpr
    What we need is (i) the diagonal elements br-k+21,br-k+32,,br-k+p+1p, (ii) the remaining elements at the pth row, i.e., br-k+p+2p,,brp, (iii) the remaining elements at the last column, i.e., brp-1, brp-2,,br1.

  3. Copy the last part of unaffected poles:

    dpp+i=d0i,     i=r,,m-1

It is noted that a big memory space is allocated to store the intermediate results bij. Actually, by rearranging the indices we need only an k×k array to store the intermediate results. We modify step 2 as follows:

    bi0 = dr-k+1+i0,     i=0,1,, k-1
    do j=1, p
          do i=j, k-1
                a = (t-t0r-k+1+i)/(t0r+1+i-j-t0r-k+1+i)
                bij=bi-1j-1+a(bij-1-bi-1j-1)
          enddo
    enddo

When completed, we have the following intermediate results:

j=1
b11
b12
b13
b1k-1
j=2
b22
b23
b2k-1
·
·
·
·
j=p
bpp
bpk-1
We then copy the intermediate results to the array of the control poles.

Actually, we can still reduce the memory size for intermediate results and improve the efficiency of code. We modify step 2 as follows:

    // First level of insertion:
    do i=1, k-1
          a = (t-t0r-k+1+i)/(t0r+i-t0r-k+1+i)
          bi=bi-1+a(bi-bi-1)
    enddo
    dr-k+2=b1
    dr+p-1=bk-1
    // Loop for remaining levels of insertion:
    do j=2, p
          p0 = bj-1
          do i=j, k-1
                p1 = bi
                a = (t-t0r-k+1+i)/(t0r+1+i-j-t0r-k+1+i)
                bi=p0+a(p1-p0)
                p0 = p1
          enddo
          dr-k+1+j=bj
          dr+p-j=bk-1
    enddo
    // Copy remaining elements at the pth row:
    dr-k+1+i=bi,    i=p+1,,k-1

As it is seen, we separate the first level of insertion from others to avoid data copying. Furthermore, we use two variables p0 and p1 to store the data so that bi can be overwritten at each level of insertion. Consequently, we need to allocate only one dimension array to store bi (i=0,1,, k).

4  Converting B-spline curve to Bézier spline curve

A B-spline curve is a piecewise polynomial curve. One reason to convert a B-spline curve to a composite Bézier curve is to represent each non-vanishing B-spline segment (or span) as a Bézier curve to facilitate geometric operations such as computation of an arc length, curve offsetting, etc.

Having gone through previous sections, the conversion from a B-spline curve to a composite Bézier curve is fairly straightforward: Inserting knots repeatedly using the blossoming formula until the interior knots all have multiplicity equal to k-1. In applications, we may encounter a case where some interior knots may already have multiplicity s with respect to t. In this case, we consider that s knots have been inserted into the knot vector and need to insert remaining p=k-1-s knots.

We now outline the procedure of conversion as follows:

  1. Search incrementally for tr at which the multiplicity s is less than k-1, i.e.,

    tr-s+1=tr-s+2= = tr,     s < k-1.

  2. Set p=k-1-s (i.e., we need to insert t=tr for p times).
  3. Copy first part of unaffected poles:

    bpi=d0i,    i=0,1, ,r-k+1

  4. Compute k+p-2 affected poles:

        bi0 = dr-k+1+i0,     i=0,1,,k-1
        do j=1, p
              do i=j, k-1
                    a = (t-t0r-k+1+i)/(t0r+1+i-j-t0r-k+1+i)
                    bij=bi-1j-1+a(bij-1-bi-1j-1)
              enddo
        enddo

  5. Copy affected poles:

           dpr-k+1+i=dii,     i=1,2,, p

           dpr-k+1+p+i=dp-ip,     i=1,2,, p

  6. Copy final part of unaffected poles: dp2p-k+1+i=d0i,     i=r-s+1,,m-1
  7. Exit the loop if all interior knots have been checked. Otherwise, go to step 1.
In real life programming, we can actually avoid updating control poles and knots repeatedly by carefully arranging and computing indices.

5  References

[1] Boehm, W. (1980), Inserting new knots into B-spline curves, Computer-Aided Design 12, pp.199-201

RETURN