# Optimizing De Boor's algorithm

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?

• Your question is awesome, insightful and indeed using de Boor's equation is not convenient as is, but what do you expect from answer? Have you tried using it in parallel? People use approximation, Bézier curve after Boehm, FDX (forward differences) or heavily depend on built-in graphic libraries. Cost to flatten pays up, you are right. It would be hard to tell why people don't use something else than wiki recursive definition, because the premise is wrong, they do use something else. – Evil May 24 at 11:07
• Thank You for the appreciation. I was looking for a justification that I overlooked in the answer. I have just started out researching computer graphics in high school, before going to college. So, I'll have to learn about the approximations you're talking about. – Sukant Kumar May 24 at 11:20
• @Evil Just tagging you since I didn't do it in my last comment. – Sukant Kumar May 24 at 15:22