3.3.6 Algoritmo di de Boor

L'algoritmo di de Boor è una generalizzazione dell'algoritmo di de Casteljau alle B-spline, infatti l'idea di questo è ridurre l'ordine delle B-spline per trovare i punti della curva. Utilizzando la forma ricorsiva possiamo scrivere l'equazione di una generica curva B-spline come:

$$\mathbf{X}(t) = \sum_{i=0}^{n} \mathbf{d}_i N_{i\ k}(t) =$$

$$= \sum_{i=0}^n \mathbf{d}_i \left[\frac{t-t_i}{t_{i+k-1}-t_i} N_{i\ k-1}(t) + \frac{t_{i+k}-t}{t_{i+k}-t_{i+1}} N_{i+1\ k-1}(t)\right] =$$

$$= \sum_{i=1}^n \underbrace{\left[\frac{t-t_i}{t_{i+k-1}-t_i} \mathb... ...}{t_{i+k-1}-t_i} \mathbf{d}_{i-1}\right]}_{\mathbf{d}_i^{[1]}(t)} N_{i\ k-1}(t)$$

Riducendo nuovamente l'ordine quello che ottengo è:

$$\mathbf{X}(t) = \sum_{i=1}^{n} \mathbf{d}_{i}^{[1]}(t) N_{i\ k-1}(t) = \sum_{i=2}^{n} \mathbf{d}_{i}^{[2]}(t) N_{i\ k-2}(t) = \ldots$$

$$\ldots = \sum_{i=k-1}^{n} \mathbf{d}_{i}^{[k-1]}(t) N_{i\ 1}(t)$$ (3.8)

dove

$$\mathbf{d}_i^{[j]}(t) = \overbrace{\frac{t-t_i}{t_{i+k-j}-t_... ...lpha_i^{[j]}(t)} \mathbf{d}_{i-1}^{[j-1]}(t)\quad i=j,\ldots,n$$

Allora, se $t\in[t_r, t_{r+1})$ abbiamo $\mathbf{X}(t) = \mathbf{d}_r^{[k-1]}(t)$. In particolare, per ottimizzare il procedimento, fissato l'intervallo $[t_r, t_{r+1})$ si considerano solamente i $k$ nodi attivi, cioè:

$$\mathbf{X}(t)=\sum_{i=r-k+1}^r \mathbf{d}_i N_{i\ k}(t)$$

I passi dell'algoritmo ottenuti da quest'ultima formula possono essere rappresentati in forma tabellare (analogamente a quanto fatto con de Casteljau):

$$\begin{array}{lccccc} \mathbf{d}_{r-k+1} = \mathbf{d}_{r-k+1... ...[k-2]} & \mathbf{d}_{r}^{[k-1]} = \mathbf{X}(t) \\ \end{array}$$

Un esempio raffigurante i passi dell'algoritmo è mostrato nella figura 3.30. Va notato come la posizione dei $\mathbf{d}_{i}^{[j]}$ cambia da segmento a segmento (a meno di nodi equispaziati) contrariamente a quanto accadeva con de Casteljau. Tale tecnica viene spesso chiamata corner cutting.

Figura 3.30: Algoritmo di de Boor, $k=4$

Il costo computazionale dell'algoritmo è

$$\sum_{j=1}^{k-1} \sum_{i=r-k+j+1}^{r} (4+3\mathsf{d}) =(4+3\... ...{d}) \sum_{j=1}^{k-1} (k-j) = (4+3\mathsf{d}) \frac{k(k-1)}{2}$$

Questo significa che il costo dipende dall'ordine, non dal numero dei nodi.