According to De Boor's algorithm, a B-Spline basis function can be evaluated using the formula:
$$ B_{i,0} = \left\{ \begin{array}{ll} 1 & \mbox{if } t_i \le x < t_{i+1} \\ 0 & \mbox{otherwise} \end{array} \right. $$
$$ B_{i,p} = \frac{x-t_i}{t_{i+p}-t_i}B_{i-1,p}(x) + \frac{t_{i+p+1} - x}{t_{i+p+1}-t_{i+1}}B_{i+1,p-1}(x) $$
where the function $B$ is defined for $n$ control points for the curve of degree $d$. The domain $t$ is divided into $n+d+1$ points called knots (in the knot vector). To evaluate this, we can define a recursive function $B(i,p)$.
The B-Spline itself is represented as, $S(x) = \sum{c_iB_{i,p}}$.
To evaluate this, the algorithm in Wikipedia tells us to take $p+1$ control points starting from $c_{k-p}$ to $c_p$, and then repeatedly take each consecutive pair's weighted average, ultimately reducing to one point.
I find this algorithm fine for one or two evaluations; however, when we draw a curve, we take hundreds of points from the curve and connect them to make it look smooth. The recursive formula still requires up to $(p-1)+(p-2)+(p-3)...$ calculations, right? (To take the weighted averages)
In my research, however, we need to evaluate only one polynomial - since the B-Spline is ultimately composed of $p+d+1$ basis polynomials (as I'll show).
Suppose we take a knot vector $[0, .33, .67, 1]$ and control points $[0, 1, 0]$ (degree $1$), then we can represent the basis polynomials as:
$$c_0B_{0,1}= 0, \mbox{ if } 0\leq x<.25, + 0, \mbox{ if } .25\leq x < .5 $$ $$c_1B_{1,1}= 4x-1, \mbox{ if } .25\leq x<.5, + \,\,-4x+3, \mbox{ if } .5\leq x < .75 $$ $$c_2B_{2,1}= 0, \mbox{ if } .5\leq x<.75 + 0, \mbox{ if } .75\leq x < 1 $$
Now, we can flatten them to produce: $$S(x) = \sum{c_i B_{i,1}} = \left\{ \begin{array}{ll} 0 & \mbox{if } 0 \le x < .25 \\ 4x-1 & \mbox{if } .25 \le x < .5 \\ -4x+3 & \mbox{if } .5 \le x < .5 \\ 0 & \mbox{if } .75 \le x < 1 \\ \end{array} \right. $$
Now, if we were to calculate $S$ at any $x$, we can directly infer which polynomial to use and then calculate it in $d$ multiplications and $d+1$ additions.
I have implemented this calculation using explicit Polynomial objects in JavaScript. See https://cs-numerical-analysis.github.io/.
I want to know why people don't use the algorithm I described. If you calculated the polynomial representation of the B-Spline and then flatten it out, it will be a one-time cost. Shouldn't that one-time cost be offset by remove the unnecessary recursive averaging?
