Algoritmo di subdivision per curve di Bézier razionali
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.
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.
Risposte
Io ho trovato un bel po' di cose cercando “Bezier subdivision”. Cosa hanno quei link che non vanno?
Che riguardano, appunto, l'algoritmo "classico" e non quello applicato alle razionali 
.
.
Prova a guardare qui http://www.belgeler.com/blg/10v9/rational-bezier-curves-rasyonel-bezier-egrileri (è in inglese)
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.
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} \).
\[ 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} \).
Avevo il dubbio proprio su questa analogia col De Casteljau originale. Grazie!
Una domanda solo per scrupolo, anche se immagino la risposta sarà affermativa: i pesi associati ai punti delle due sottocurve saranno gli $w_0^0, w_0^1, ..., w_0^n$ e $w_0^n, w_1^(n-1), ..., w_0^n$ rispettivamente?
Sì, certo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo