Converting B-spline curve to Bézier spline curve

1  Introduction

t0=t1=¼ = tk-1,    tk £ tk+1 £ ¼ £ tm-1,     tm=tm+1=¼ = tm+k-1.

In practice, we call knots t_j (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

r(t)= m-1 å i=0  N0i,k(t)d0i,

Inserting a new knot t in [t⁰_r,t⁰_r+1) forms a new knot sequence:

       t¹_j=t⁰_j,     j=0,1,¼,r
       t¹_r+1=t
       t¹_j+1=t⁰_j,     j=r+1,¼,m+k
which defines m+1 new basis functions N_i,k¹(t). Now we want to write the given B-spline curve in terms of the new control poles d_i¹ 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 N⁰_0,k(t),¼,N⁰_r-k+1,k(t) and N⁰_r,k(t), ¼,N⁰_m-1,k(t) are not affected. Therefore, we can derive that

       d¹_i = d⁰_i,     i=0,¼,r-k+1

       d¹_i+1 = d⁰_i,     i=r,¼,m-1

To compute k-1 affected poles d¹_r-k+2, ¼,d¹_r, 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

1. Copy the first part of unaffected poles:

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

2. Compute k+p-2 affected poles d_r-k+2^p, ¼, d_r+p-1^p:

   We use a temporary array b_i^j to store the intermediate results. So,

       b_i⁰ = d_i⁰,     i=r-k+1,¼, r
       do j=1, p
             do i=r-k+1+j, r
                   a = (t-t⁰_i)/(t⁰_i+k-j-t⁰_i)
                   b_i^j=b_i-1^j-1+a(b_i^j-1-b_i-1^j-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 b_r-k+2¹,b_r-k+3²,¼,b_r-k+p+1^p, (ii) the remaining elements at the pth row, i.e., b_r-k+p+2^p,¼,b_r^p, (iii) the remaining elements at the last column, i.e., b_r^p-1, b_r^p-2,¼,b_r¹.

3. Copy the last part of unaffected poles:

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

    b_i⁰ = d_r-k+1+i⁰,     i=0,1,¼, k-1
    do j=1, p
          do i=j, k-1
                a = (t-t⁰_r-k+1+i)/(t⁰_r+1+i-j-t⁰_r-k+1+i)
                b_i^j=b_i-1^j-1+a(b_i^j-1-b_i-1^j-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.

• Copy diagonal elements: d_r-k+1+i=b_iⁱ,    i=1,2,¼,p
• Copy remaining elements at the pth row: d_r-k+1+i=b_i^p,    i=p+1,¼, k-1
• Copy remaining elements at the last column: d_r+p-i=b_k-1ⁱ,    i=p-1,¼, 1

    // First level of insertion:
    do i=1, k-1
          a = (t-t⁰_r-k+1+i)/(t⁰_r+i-t⁰_r-k+1+i)
          b_i=b_i-1+a(b_i-b_i-1)
    enddo
    d_r-k+2=b₁
    d_r+p-1=b_k-1
    // Loop for remaining levels of insertion:
    do j=2, p
          p₀ = b_j-1
          do i=j, k-1
                p₁ = b_i
                a = (t-t⁰_r-k+1+i)/(t⁰_r+1+i-j-t⁰_r-k+1+i)
                b_i=p₀+a(p₁-p₀)
                p₀ = p₁
          enddo
          d_r-k+1+j=b_j
          d_r+p-j=b_k-1
    enddo
    // Copy remaining elements at the pth row:
    d_r-k+1+i=b_i,    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 p₀ and p₁ to store the data so that b_i can be overwritten at each level of insertion. Consequently, we need to allocate only one dimension array to store b_i (i=0,1,¼, k).

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

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 t_r 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=t_r 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:

       b_i⁰ = d_r-k+1+i⁰,     i=0,1,¼,k-1
       do j=1, p
             do i=j, k-1
                   a = (t-t⁰_r-k+1+i)/(t⁰_r+1+i-j-t⁰_r-k+1+i)
                   b_i^j=b_i-1^j-1+a(b_i^j-1-b_i-1^j-1)
             enddo
       enddo

5. Copy affected poles:

          d^p_r-k+1+i=dⁱ_i,     i=1,2,¼, p

          d^p_r-k+1+p+i=d^p-i_p,     i=1,2,¼, p

6. Copy final part of unaffected poles: d^p_2p-k+1+i=d⁰_i,     i=r-s+1,¼,m-1
7. Exit the loop if all interior knots have been checked. Otherwise, go to step 1.

5  References

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