Converting Bspline curve to Bézier spline curve
1 Introduction
A nonperiodic Bspline curve of order k with m control poles has m+k knots {t_{j}},
known as the knot vector (or knot sequence). The knot vector has the following
property:
t_{0}=t_{1}=¼ = t_{k1}, t_{k} £ t_{k+1} £ ¼ £ t_{m1}, t_{m}=t_{m+1}=¼ = t_{m+k1}. 

In practice, we call knots t_{j} (j=k,¼,m1) the interior knots. A Bspline curve
whose interior knots all have multiplicity equal to k1 is known as a composite Bézier curve
(or a Bézier spline curve). Therefore, to convert a Bspline 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 k1.
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 Bspline curve by
d^{0}_{i} and t^{0}_{j}, we may represent the Bspline
curve as
r(t)= 
m1 å
i=0

N^{0}_{i,k}(t)d^{0}_{i}, 

Inserting a new knot t in [t^{0}_{r},t^{0}_{r+1}) forms
a new knot sequence:
t^{1}_{j}=t^{0}_{j},
j=0,1,¼,r
t^{1}_{r+1}=t
t^{1}_{j+1}=t^{0}_{j},
j=r+1,¼,m+k
which defines m+1 new basis functions N_{i,k}^{1}(t). Now we want to write
the given Bspline curve in terms of the new control poles d_{i}^{1}
and the new basis functions, i.e.,
r(t)= 
m å
i=0

N^{1}_{i,k}(t)d^{1}_{i}. 

Due to the local support property of a Bspline curve, it is known that the basis functions N^{0}_{0,k}(t),¼,N^{0}_{rk+1,k}(t) and N^{0}_{r,k}(t), ¼,N^{0}_{m1,k}(t) are not affected. Therefore, we can derive that
d^{1}_{i} = d^{0}_{i}, i=0,¼,rk+1
d^{1}_{i+1} = d^{0}_{i}, i=r,¼,m1
To compute k1 affected poles d^{1}_{rk+2}, ¼,d^{1}_{r}, we set
t=t^{1}_{r+1}=(1a_{i})t^{0}_{i}+a_{i} t^{0}_{i+k1}=t_{i}^{0}+a_{i}(t_{i+k1}^{0}t_{i}^{0}). 

Then, by the affine invariance, it follows
d^{1}_{i}=(1a_{i})d^{0}_{i1}+a_{i}d^{0}_{i}=d_{i1}^{0}+a_{i}(d_{i}^{0}d_{i1}^{0}), (i=rk+2,¼,r) 

with
a_{i}= 
t  t^{0}_{i} t^{0}_{i+k1}t^{0}_{i}

. 

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 Î [t^{0}_{r},t^{0}_{r+1}) into the existing knot vector for p times. The improved method is then summarized as follows:
 Copy the first part of unaffected poles:
d^{p}_{i}=d^{0}_{i}, i=0,1, ¼,rk+1. 

 Compute k+p2 affected poles d_{rk+2}^{p}, ¼, d_{r+p1}^{p}:
We use a temporary array b_{i}^{j} to store the intermediate results. So,
b_{i}^{0} = d_{i}^{0}, i=rk+1,¼, r
do j=1, p
do i=rk+1+j, r
a = (tt^{0}_{i})/(t^{0}_{i+kj}t^{0}_{i})
b_{i}^{j}=b_{i1}^{j1}+a(b_{i}^{j1}b_{i1}^{j1})
enddo
enddo
When completed, we have the following intermediate results:
What we need is (i) the diagonal elements b_{rk+2}^{1},b_{rk+3}^{2},¼,b_{rk+p+1}^{p}, (ii) the remaining elements at the pth row, i.e., b_{rk+p+2}^{p},¼,b_{r}^{p}, (iii) the remaining elements at the last column, i.e., b_{r}^{p1}, b_{r}^{p2},¼,b_{r}^{1}.
 Copy the last part of unaffected poles:
d^{p}_{p+i}=d^{0}_{i}, i=r,¼,m1 

It is noted that a big memory space is allocated to store the intermediate results
b_{i}^{j}. Actually, by rearranging the indices we need only
an k×k array to store the intermediate results. We modify step 2 as follows:
b_{i}^{0} = d_{rk+1+i}^{0}, i=0,1,¼,
k1
do j=1, p
do i=j, k1
a = (tt^{0}_{rk+1+i})/(t^{0}_{r+1+ij}t^{0}_{rk+1+i})
b_{i}^{j}=b_{i1}^{j1}+a(b_{i}^{j1}b_{i1}^{j1})
enddo
enddo
When completed, we have the following intermediate results:
We then copy the intermediate results to the array of the control poles.
 Copy diagonal elements: d_{rk+1+i}=b_{i}^{i}, i=1,2,¼,p
 Copy remaining elements at the pth row: d_{rk+1+i}=b_{i}^{p}, i=p+1,¼, k1
 Copy remaining elements at the last column: d_{r+pi}=b_{k1}^{i}, i=p1,¼, 1
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, k1
a = (tt^{0}_{rk+1+i})/(t^{0}_{r+i}t^{0}_{rk+1+i})
b_{i}=b_{i1}+a(b_{i}b_{i1})
enddo
d_{rk+2}=b_{1}
d_{r+p1}=b_{k1}
// Loop for remaining levels of insertion:
do j=2, p
p_{0} = b_{j1}
do i=j, k1
p_{1} = b_{i}
a = (tt^{0}_{rk+1+i})/(t^{0}_{r+1+ij}t^{0}_{rk+1+i})
b_{i}=p_{0}+a(p_{1}p_{0})
p_{0} = p_{1}
enddo
d_{rk+1+j}=b_{j}
d_{r+pj}=b_{k1}
enddo
// Copy remaining elements at the pth row:
d_{rk+1+i}=b_{i}, i=p+1,¼,k1
As it is seen, we separate the first level of insertion from others to avoid data copying. Furthermore, we use two variables p_{0} and p_{1} 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 Bspline curve to Bézier spline curve
A Bspline curve is a piecewise polynomial curve. One reason to convert a Bspline curve to a composite Bézier curve is to represent each nonvanishing Bspline 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 Bspline 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 k1. 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=k1s knots.
We now outline the procedure of conversion as follows:
 Search incrementally for t_{r} at which the multiplicity s is less than k1, i.e.,
t_{rs+1}=t_{rs+2}=¼ = t_{r}, s < k1. 

 Set p=k1s (i.e., we need to insert t=t_{r} for p times).
 Copy first part of unaffected poles:
b^{p}_{i}=d^{0}_{i}, i=0,1, ¼,rk+1 

 Compute k+p2 affected poles:
b_{i}^{0} = d_{rk+1+i}^{0}, i=0,1,¼,k1
do j=1, p
do i=j, k1
a = (tt^{0}_{rk+1+i})/(t^{0}_{r+1+ij}t^{0}_{rk+1+i})
b_{i}^{j}=b_{i1}^{j1}+a(b_{i}^{j1}b_{i1}^{j1})
enddo
enddo
 Copy affected poles:
d^{p}_{rk+1+i}=d^{i}_{i}, i=1,2,¼, p
d^{p}_{rk+1+p+i}=d^{pi}_{p}, i=1,2,¼, p
 Copy final part of unaffected poles: d^{p}_{2pk+1+i}=d^{0}_{i}, i=rs+1,¼,m1
 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 Bspline curves, ComputerAided Design 12, pp.199201
RETURN