8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, yeah I had seen that article. I'm having a hard time making sense of the math and creating javascript from it. I need an example that is less theory and more application. (Or better math skills). $\endgroup$ – TimSum Jun 18 '13 at 15:13
  • $\begingroup$ Now that I've told you the name of the algorithm (Boehm or Bohm), I was thinking you could search for code. I assume that your curve is cubic (degree = 3)? Are your knots uniformly spaced? $\endgroup$ – bubba Jun 18 '13 at 15:44
  • $\begingroup$ Sorry -- one more question: are there any repetitions in your sequence of knots? $\endgroup$ – bubba Jun 18 '13 at 15:46
  • $\begingroup$ I'll continue to search for code. My curve is cubic. Knots are not evenly spaced and there are repetitions. $\endgroup$ – TimSum Jun 18 '13 at 20:24
0
$\begingroup$

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))$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.