De Boor's algorithm

In mathematics, De Boor algorithm is an algorithm for evaluating spline curves.

Goal of the algorithm

Suppose we want to evaluate the spline curve

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

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

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

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

The algorithm

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

${\displaystyle {\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

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

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