De Boor's algorithm: Difference between revisions

Revision as of 07:56, 18 August 2017

Revision as of 08:00, 18 August 2017

Line 23:

:<math>B_{i,p}(x) := \frac{x - t_i}{t_{i+p} - t_i} B_{i,p-1}(x) + \frac{t_{i+p+1} - x}{t_{i+p+1} - t_{i+1}} B_{i+1,p-1}(x). </math>

Let the index <math> k </math> define the knot interval that contains the position, <math> x \in [t_{k},t_{k+1}) </math>. We can see in the recursion formula that only B-splines with <math> i \in= [k-p, \dots, k] </math> are non-zero for this knot interval. Thus, the sum is reduced to:

:<math> \mathbf{S}(x) = \sum_{i=k-p}^{k} \mathbf{c}_i B_{i,p}(x). </math>

Line 47:

The algorithm above is not optimized for the implementation in a computer. It requires memory for <math> (p + 1) + p + \dots + 1 = (p + 1)(p + 2)/2 </math> temporary control points <math> \mathbf{d}_{i,r} </math>. Each temporary control points is written exactly once and read twice. By reversing the iteration over <math> i </math> (counting down instead of up), we can run the algorithm with memory for only <math> p + 1 </math> temporary control points, by letting <math> \mathbf{d}_{i,r} </math> reuse the memory for <math> \mathbf{d}_{i,r-1} </math>. Similarly, there is only one value of <math> \alpha </math> used in each step, so we can reuse the memory as well.

Furthermore, it is more convenient to use ana zero-based index <math> j \in= [0, \dots, p] </math> for the temporary control points. The relation to the previous index is <math> i = j + k - p </math>. Thus we obtain the improved algorithm:

Let <math> \mathbf{d}_{j} := \mathbf{c}_{j+k - p} </math> for <math> j = 0, \dots, p</math>. Iterate for <math> r = 1, \dots, p </math>: