Algoritmo di subdivision per curve di Bézier razionali

[ZetaFunction]

Ciao a tutti,
vorrei sapere se qualcuno è a conoscenza, magari con link in formato elettronico, appunto di un algoritmo di subdivision da applicare alle curve di Bézier razionali (analogamente a quello noto sulle classiche). Grazie in anticipo.

[vict85]

Io ho trovato un bel po' di cose cercando “Bezier subdivision”. Cosa hanno quei link che non vanno?

[ZetaFunction]

Che riguardano, appunto, l'algoritmo "classico" e non quello applicato alle razionali .

[vict85]

Prova a guardare qui http://www.belgeler.com/blg/10v9/rational-bezier-curves-rasyonel-bezier-egrileri (è in inglese)

[ZetaFunction]

Ti ringrazio, il pdf è interessante ma contiene solo il De Casteljau. Avevo pensato a ricavarmi da questo la subdivision, ma preferirei andare sul sicuro e trovare l'algoritmo vero e proprio.

[apatriarca]

Come immagino tu sappia, la formula generale di una curva di Bézier razionale è
\[ B(t) = \frac{\sum_{i=0}^n w_i \mathbf{b_i} B_{i,n}(t) }{ \sum_{i=0}^n w_i B_{i,n}(t) }, \]
dove \( \mathbf{b_i} \) sono i punti di controllo, \( w_i \) sono i pesi e \( B_{i,n}(t) \) sono i polinomi di Bernstein di grado \( n \). Considera adesso i punti affini \( \mathbf{ \widehat{b}_i } = [ w_i \mathbf{b_i}, w_i ] \). La curva di Bézier razionale sarà allora uguale alla deomogeneizzazione (rispetto all'ultima coordinata) della seguente curva di Bézier integrale nello spazio proiettivo:
\[ \widehat{B}(t) = \sum_{i=0}^n \mathbf{\widehat{b}_i} B_{i,n}(t). \]
Un primo metodo per fare la suddivisione è quindi quello di suddividere la curva dello spazio proiettivo e poi deomogeneizzare il risultato in modo da ottenere il risultato nello spazio affine.

Questo primo metodo, anche se molto semplice ed efficiente, non è però molto robusto in pratica (ci sono casi in cui il metodo è soggetto ad errori). Per questo motivo si preferisce usare un metodo alternativo in cui si deomogenizza ad ogni passo dell'algoritmo di de Casteljau per poi utilizzare i punti di controllo ottenuti dall'algoritmo come al solito per fare la suddivisione. L'algoritmo di Casteljau diventa in questo caso il seguente:
\[ \left\{ \begin{align*}
\mathbf{b_i^j} &= (1 - t) (w_i^{j-1} / w_i^j) \mathbf{b_i^{j-1}} + t (w_{i+1}^{j-1} / w_i^j) \mathbf{b_{i+1}^{j-1}} \\
w_i^j &= (1 - t) w_{i}^{j-1} + t w_{i+1}^{j-1}
\end{align*}\right. \]
In cui abbiamo come al solito che \( \mathbf{b_i^0} = \mathbf{b_i} \) e \( w_i^0 = w_i \).

Ti ricordo solo brevemente quali sono i punti di controllo dell'algoritmo di suddivisione in modo che il post contenga tutte le informazioni necessarie per implementare l'algoritmo. Per la prima curva di Bézier abbiamo come punti di controllo i punti \( \mathbf{b_0^0}, \mathbf{b_0^1}, \dotsc, \mathbf{b_0^n} \), mentre la seconda curva di Bézier ha punti di controllo \( \mathbf{b_0^n}, \mathbf{b_1^{n-1}}, \dotsc, \mathbf{b_n^0} \).

[ZetaFunction]

Avevo il dubbio proprio su questa analogia col De Casteljau originale. Grazie!

[ZetaFunction]

Una domanda solo per scrupolo, anche se immagino la risposta sarà affermativa: i pesi associati ai punti delle due sottocurve saranno gli \( \displaystyle {{w}_{{0}}^{{0}}},{{w}_{{0}}^{{1}}},\ldots,{{w}_{{0}}^{{n}}} \) e \( \displaystyle {{w}_{{0}}^{{n}}},{{w}_{{1}}^{{{n}-{1}}}},\ldots,{{w}_{{0}}^{{n}}} \) rispettivamente?

[apatriarca]

Sì, certo.