Convert a B-Spline into Bezier curves

Question

I have a B-Spline curve. I have all the knots, and the x,y coordinates of the Control Points.

I need to convert the B-Spline curve into Bezier curves.

My end goal is to be able to draw the shape on an html5 canvas element. The B-Spline is coming from a dxf file which doesn't support Beziers, while a canvas only supports Beziers.

I've found several articles which attempt to explain the process, however they are quite a bit over my head and really seem to be very theory intensive. I really need an example or step by step help.

Here's what I've found: (Explains B-Splines), (Convert B-Splines),

I can share my Nodes or Control Points if that would be useful. If someone would point me to a step-by-step procedure or help me with some psuedo(or actual)code, I would be so grateful.

Answer 1

What you need is something called "Boehm's algorithm" (after its originator, Wolfgang Boehm). It has a simple geometric interpretation, and drawing a few pictures should make it clear. There is a pretty good explanation (with pictures) in this document.

The algorithm is based on a process called "knot insertion". You keep inserting knots into the b-spline curve until each knot has multiplicity 3. Then, the b-spline control points of this refined curve give you the Bezier control points of its segments.

So, if you're writing code to do this, one approach is to write a knot insertion function first, and then call it repeatedly.

There is knot insertion code here.

Answer 2

As an alternative to Boehm's Algorithm, there is the following recurrence relation in the special case where a degree $d$ B‑spline has distinct knots $\{u_1,u_2,\ \ldots,u_s\}$ with common multiplicity $m$.

If the multiplicity of the interior knots is increased to $n$, we can obtain the new coefficients by multiplying the old ones by a matrix whose $i,j$'th entry equals $M^{d,m,n}_{i,j}$. You can add $0$-columns to that matrix if you too want to insert the boundary knots.

Clearly, if $m=n$ then $M^{d,m,n}_{i,j}=\delta_{i,j}$.
Otherwise, and if not $\ 1+\scriptsize\left\lceil\normalsize\frac{\large i}{\large m}\right\rceil\normalsize\leq 2 + \frac{\large j-i}{\large n-m} \leq \scriptsize\left\lceil\normalsize\frac{\large i+d+1}{\large m}\right\rceil$, then $M^{d,m,n}_{i,j}=0$.

Else we have

$$ M^{d,m,n}_{i,j} = \begin{cases} \begin{aligned}&\left.\underline{ \frac {u_{k+1} - u_{\small\left\lceil\normalsize\frac{\Large i}{\Large m}\right\rceil}} {u_{\small\left\lceil\normalsize\frac{\Large i+d}{\Large m}\right\rceil} - u_{\small\left\lceil\normalsize\frac{\Large i}{\Large m}\right\rceil}} M^{d-1,m,d}_{i,j-k+1} + \frac {u_{\small\left\lceil\normalsize\frac{\Large i+d+1}{\Large m}\right\rceil} - u_{k+1}} {u_{\small\left\lceil\normalsize\frac{\Large i+d+1}{\Large m}\right\rceil} - u_{\small\left\lceil\normalsize\frac{\Large i+1}{\Large m}\right\rceil}} M^{d-1,m,d}_{i+1,j-k+1}}\hspace{-0.05cm}\right| \\[-3pt]&\hspace{-0.05cm}\left|^{\text{ }\\ \large \Delta j = \begin{cases} 1 & (d - m) \left(\small\left\lceil\normalsize\frac {\Large i+d}{\Large m}\right\rceil \normalsize\ +\ \small\left\lceil\normalsize\frac {\Large i+1}{\Large m}\right\rceil \normalsize\ -\ 3\right)\ <\ \frac{\Large (2j-1)d\ +\ 2m}{\Large n}-2i\\ 0 & \text{else} \end{cases} }_{\text{ }\\ \large k\ = \small\ \left\lceil\normalsize j\ -\ \frac{\Large 1}{\Large 2} \left(\frac{\Large(2j-1)d\ +\ 2m}{\Large n}\ -\ \frac{\Large \Delta j}{\Large n}\right)\right\rceil }\right.\end{aligned} & d < n \\ \text{ } & \text{ } \\ \begin{aligned}&\left.\underline{ \frac {u_{k+1} - u_{\small\left\lceil\normalsize\frac{\Large i}{\Large m}\right\rceil}} {u_{\small\left\lceil\normalsize\frac{\Large i+d}{\Large m}\right\rceil} - u_{\small\left\lceil\normalsize\frac{\Large i}{\Large m}\right\rceil}} M^{d-1,m,n}_{i,j-\Delta j+1} + \frac {u_{\small\left\lceil\normalsize\frac{\Large i+d+1}{\Large m}\right\rceil} - u_{k+1}} {u_{\small\left\lceil\normalsize\frac{\Large i+d+1}{\Large m}\right\rceil} - u_{\small\left\lceil\normalsize\frac{\Large i+1}{\Large m}\right\rceil}} M^{d-1,m,n}_{i+1,j-\Delta j+1}}\hspace{-0.05cm}\right| \\[-3pt]&\hspace{-0.05cm}\left|^{\text{ }\\ \large \Delta j = \begin{cases} 1 & (n - m) \left(\small\left\lceil\normalsize\frac {\Large i+d}{\Large m}\right\rceil \normalsize\ +\ \small\left\lceil\normalsize\frac {\Large i+1}{\Large m}\right\rceil \normalsize\ -\ 3\right)\ >\ 2(j\ -\ i) \\ 0 & \text{else} \end{cases} }_{\text{ }\\ \large k\ =\small\ \left\lceil\normalsize\frac{\Large j\ + \ \Delta j (d-1)\ -\ m\ +\ 1/2}{\Large n}\right\rceil }\right.\end{aligned} & d \geq n \end{cases} $$

The function expression for $\Delta j$ can be replaced by any function from $\{d,m,n,i,j\}$ to $\{0,1\}$. The particular choice above (among many others) minimizes the recursive calls to non-zero entries.

Note that you will only encounter the first case of the piecewise function when converting a B-spline coefficients to Bezier coefficients, because $n=d+1$ throughout the recursions.

Edit:

If $d \leq 2m$, then the recurrence relation above can be replaced by a much more efficient one:

$\begin{align} & M^{d,m,n}_{i,j} = \begin{cases} B_{Q_1}^{Q_2,Q_3} & Q_3 > 0 \\ 1 & \text{else} \end{cases}\\[0.18cm]& B^{m,n}_i = \begin{cases} \begin{cases} \dfrac{u_{i+1}-u_i}{u_{i+1}-u_{i-1}}\,\dfrac{n\,B^{m,n-1}_i}{n-m} & n \neq m \\ \dfrac{u_i-u_{i-1}}{u_{i+1}-u_{i-1}}B^{m-1,n-1} & \text{else} \end{cases} & n > 0 \\ 1 & \text{else} \end{cases} \end{align}$

where
$Q_1 = \left\lceil \dfrac{d+2(n-m+j)}{2 n}\right\rceil$
$Q_2 = i + d + \min(m, n - ((j + d - 2m)\ \%\ n)) - m\left\lceil \dfrac{j+2(n-m)+d+1}{n} \right\rceil$
$Q_3=\min((j\ \%\ n) + d - 2m, n - m, n - (j\ \%\ n))$