De Boor's algorithm

Goal of the algorithm

Suppose we want to evaluate the spline curve

${\vec {s}}(u)=\sum _{i=-n}^{p-1}{\vec {d}}_{i}N_{i}^{n}(u),$

defined on the interval $[u_{0},u_{p})$ for a parameter value $x\in [u_{\ell },u_{\ell +1})$. Due to the spline locality property, we can write

${\vec {s}}(x)=\sum _{i=\ell -n}^{\ell }{\vec {d}}_{i}N_{i}^{n}(x)$

So the value ${\vec {s}}(x)$ is determined by the controlpoints ${\vec {d}}_{\ell -n},{\vec {d}}_{\ell -n+1},{\vec {d}}_{\ell }$; the other control points have no influence. The goal of de Boor's algorithm is to evaluate ${\vec {s}}(x)$ efficiently.

The algorithm

Suppose $x\in [u_{\ell },u_{\ell +1})$ and ${\vec {d}}_{i}^{[0]}={\vec {d}}_{i}$ for $i=\ell -n+k,\dots ,\ell$. Now calculate

${\vec {d}}_{i}^{[k]}=(1-\alpha _{k,i}){\vec {d}}_{i-1}^{[k-1]}+\alpha _{k,i}{\vec {d}}_{i}^{[k-1]};\qquad k=1,\dots ,n;\quad i=\ell -n+k,\dots ,\ell$

with

$\alpha _{k,i}={\frac {x-u_{i}}{u_{i+n+1-k}-u_{i}}}.$

Then ${\vec {s}}(x)={\vec {d}}_{\ell }^{[n]}$.