Curve di Bézier
Le curve di Bézier originariamente inventate per il design di auto, sono le curve
più utilizzate nella computer grafica.
Le curve di Bézier come vedremo dalla loro formulazione sono definite a partire da una successione di punti chiamati punti di controllo che racchiudono al loro interno una curva di Bézier.
L'algoritmo di de Casteljau è un facile algoritmo per capire come le curve di Bézier sono costruite. Una curva di Bezier di 1° grado è definita come: $$B^1(t)=(1-t)P_0+tP_1 $$ Dove \(P_0\) e \(P_1\) sono punti \(P\in \mathbb{R}^d\) con \(d=2\) o \(d=3\), mentre \(t\) è definito in \([0,1]\), una curva di Bézier di 1° grado è una semplice linea da \(P_0\) a \(P_1\).
Una curva di Bézier di 2° grado è invece definita come: $$B^2(t)=(1-t)B_0^1(t) + t B_1^1(t).$$ La curva di Bézier di 2° grado è definita su 3 punti a partire da due curve di Bézier di 1° grado, perciò:
$$B^2(t)=(1-t)[(1-t)P_0+t P_1] + t [(1-t)P_1 + t P_2] $$ $$=(1-t)^2 P_0 + 2(1-t)t P_1 +t^2 P_2 $$
Genericamente l'algoritmo di de Casteljau è definito come: $$B_i^r(t)=(1-t)B_i^{r-1}(t) + tB_{i+1}^{r-1}(t).$$ Esiste un'altra formulazione delle curve di Bézier non ricorsiva, che si ottiene a partire dall'algoritmo di De Casteljau, si può osservare infatti che risolvendo: $$B_i^r(t)=(1-t)B_i^{r-1}(t) + tB_{i+1}^{r-1}(t).$$ fino a ottenere la formulazione in punti si ottiene:
$$B_i^r(t)={r\choose 0} t^0 (1-t)^{r}P_0 + {r\choose 1} t^1 (1-t)^{r-1}P_1 + {r\choose 2} t^2 (1-t)^{r-2}P_2+ $$
$$...+ {r\choose r} t^{r-1} (1-t)^{1}P_{r-1}.$$
nel caso di una curva di Bézier di grado 2 ho: $$B^2(t)={2\choose 0} t^0 (1-t)^{2}P_0 + {2\choose 1} t^1 (1-t)^{1}P_1 + {2\choose 2} t^2 (1-t)^{0}P_2.$$ Nel caso di una curva di 3° grado si ottiene: $$B^3(t)={3\choose 0} t^0 (1-t)^{3}P_0 + {3\choose 1} t^1 (1-t)^{2}P_1 + {3\choose 2} t^2 (1-t)^{1}P_2 + {3\choose 3} t^3 (1-t)^{0}P_3.$$ Se si definisce ogni termine moltiplicativo \(b_i^r(t)\) dei punti \(P\) come: $$b_i^r(t)={r\choose i} t^i (1-t)^{r-i}.$$ otteniamo i coefficienti di Bernstein, e possiamo quindi scrivere la curva come: $$B_i^r(t)=\sum_{i=0}^r b_{i}^r(t)P_i.$$
Le curve di Bézier come vedremo dalla loro formulazione sono definite a partire da una successione di punti chiamati punti di controllo che racchiudono al loro interno una curva di Bézier.
L'algoritmo di de Casteljau è un facile algoritmo per capire come le curve di Bézier sono costruite. Una curva di Bezier di 1° grado è definita come: $$B^1(t)=(1-t)P_0+tP_1 $$ Dove \(P_0\) e \(P_1\) sono punti \(P\in \mathbb{R}^d\) con \(d=2\) o \(d=3\), mentre \(t\) è definito in \([0,1]\), una curva di Bézier di 1° grado è una semplice linea da \(P_0\) a \(P_1\).
Una curva di Bézier di 2° grado è invece definita come: $$B^2(t)=(1-t)B_0^1(t) + t B_1^1(t).$$ La curva di Bézier di 2° grado è definita su 3 punti a partire da due curve di Bézier di 1° grado, perciò:
$$B^2(t)=(1-t)[(1-t)P_0+t P_1] + t [(1-t)P_1 + t P_2] $$ $$=(1-t)^2 P_0 + 2(1-t)t P_1 +t^2 P_2 $$
Genericamente l'algoritmo di de Casteljau è definito come: $$B_i^r(t)=(1-t)B_i^{r-1}(t) + tB_{i+1}^{r-1}(t).$$ Esiste un'altra formulazione delle curve di Bézier non ricorsiva, che si ottiene a partire dall'algoritmo di De Casteljau, si può osservare infatti che risolvendo: $$B_i^r(t)=(1-t)B_i^{r-1}(t) + tB_{i+1}^{r-1}(t).$$ fino a ottenere la formulazione in punti si ottiene:
$$B_i^r(t)={r\choose 0} t^0 (1-t)^{r}P_0 + {r\choose 1} t^1 (1-t)^{r-1}P_1 + {r\choose 2} t^2 (1-t)^{r-2}P_2+ $$
$$...+ {r\choose r} t^{r-1} (1-t)^{1}P_{r-1}.$$
nel caso di una curva di Bézier di grado 2 ho: $$B^2(t)={2\choose 0} t^0 (1-t)^{2}P_0 + {2\choose 1} t^1 (1-t)^{1}P_1 + {2\choose 2} t^2 (1-t)^{0}P_2.$$ Nel caso di una curva di 3° grado si ottiene: $$B^3(t)={3\choose 0} t^0 (1-t)^{3}P_0 + {3\choose 1} t^1 (1-t)^{2}P_1 + {3\choose 2} t^2 (1-t)^{1}P_2 + {3\choose 3} t^3 (1-t)^{0}P_3.$$ Se si definisce ogni termine moltiplicativo \(b_i^r(t)\) dei punti \(P\) come: $$b_i^r(t)={r\choose i} t^i (1-t)^{r-i}.$$ otteniamo i coefficienti di Bernstein, e possiamo quindi scrivere la curva come: $$B_i^r(t)=\sum_{i=0}^r b_{i}^r(t)P_i.$$
Superficie di Bézier
Le superfici di Bézier sono una generalizzazione delle curve, esse operano in \([0,1]^2\) piuttosto che in \([0,1]\), perciò abbiamo due lati su cui dobbiamo definire i punti di controllo, abbiamo perciò una matrice di punti del tipo: $$\begin{bmatrix} P_{00} & P_{01} \\ P_{10} & P_{11} \end{bmatrix}.$$ Una superficie di Bézier viene quindi definita come: $$B(u,v)=\sum_{i=0}^n\sum_{j=0}^m b_{i}^n(u) b_{j}^m(v) P_{i,j}.$$ attraverso questa definizione vengono composte due curve su due diversi intervalli, ciò genera una superficie.Derivata di una superficie
Derivando la funzione possiamo osservare che: $$ \frac {\partial} {\partial u} B^{m,n}(u,v)= \sum_{j=0}^n \left[ \frac {\partial} {\partial u } \sum_{i=0}^{m} b_i^m(u)P_{i,j} \right] b_j^n(v) $$ La parte interna dipende solo da \( u \) è corrisponde alla derivata di una curva di Bézier. $$ \frac {\partial} {\partial u} B^{m}(u)= \frac {\partial} {\partial u } \sum_{i=0}^{m} b_i^m(u)P_{i} $$ $$ \frac {\partial} {\partial u} B^{m}(u)= \sum_{i=0}^{m} \frac {\partial} {\partial u } \left( {m\choose i} u^i (1-u)^{r-i}P_{i} \right) $$ $$ \frac {\partial} {\partial u} B^{m}(u)= \sum_{i=0}^{m} \left( {m\choose i} i u^{i-1} (1-u)^{m-i}P_{i} - {m\choose i}(m-i)u^i (1-u)^{m-i-1}P_{i} \right) $$ Possiamo notare come il primo termine sinistro e l'ultimo termine destro vanno a 0 $$ \frac {\partial} {\partial u} B^{m}(u)= \sum_{i=1}^{m-1} \left( \frac {m!} {(m-i)!i!} i u^{i-1} (1-u)^{m-i}P_{i} - {m\choose i}(m-i)u^i (1-u)^{m-i-1}P_{i} \right) $$ $$ -{m\choose 0} m (1-u)^{m-1}P_{0}+{m\choose m} m (u)^{m-1}P_{0} $$ Se raccogliamo un \( m \) dalle combinazioni \( {m\choose i} \): $$ \frac {\partial} {\partial u} B^{m}(u)= \sum_{i=1}^{m-1} \left( \frac {m(m-1)!} {(m-i)!(i-1)!} u^{i-1} (1-u)^{m-i}P_{i} - \frac {m(m-1)!} {(m-i-1)!i!} u^i (1-u)^{m-i-1}P_{i} \right) $$ $$ -{m\choose 0} m (1-u)^{m-1}P_{0}+{m\choose m} m (u)^{m-1}P_{0} $$ possiamo ottenere i coefficienti di Bernstein \( b_{i}^{m-1}(t)={m-1\choose i} t^i (1-t)^{m-i} \) per \(m-1\): $$ \frac {\partial} {\partial u} B^{m}(u)= m \sum_{i=1}^{m-1} \left( b_{i-1}^{m-1} P_{i} - b_{i}^{m-1} P_{i} \right) $$ $$ -m b_0^{m-1}(u)P_{0}+m b_{m-1}^{m-1}(u)P_{0} $$ Se si espande la sommatoria si ottiene: $$ \frac {\partial} {\partial u} B^{m}(u)= m ((b_{0}^{m-1}(u)P_{1}+ \cdots + b_{m-1}^{m-1}(u)P_{m-1}) $$ $$ - (b_{1}^{m-1}(u)P_{1}+b_{1}^{m-1}(u)P_{1}+ \cdots + b_{m-1}^{m-1}(u)P_{m-1})) $$ $$ -m b_0^{m-1}(u)P_{0}+m b_{m-1}^{m-1}(u)P_{m-1} $$ Se si raccolgono i coefficienti di Bernstein si ottiene che: $$ \frac {\partial} {\partial u} B^{m,n}(u,v)= m\sum_{i=0}^{m-1} (P_{i+1} - P_{i}) b_{i}^{m-1}(u) $$ Perciò la derivata di una superficie è: $$ \frac {\partial} {\partial u} B^{m,n}(u,v)= m \sum_{j=0}^n \sum_{i=0}^{m-1} (P_{i+1,j} - P_{i,j}) b_{i}^{m-1}(u)b_{j}^{n}(v) $$ Si può dimostrare che la derivata \(r\)-esima corrisponde a: $$ \frac {\partial} {\partial u} B^{m,n}(u,v)= \frac {m!}{(m-r)!} \sum_{j=0}^n \sum_{i=0}^{m-r} \Delta^{r,0}P_{i,j} b_{i}^{m-r}(u)b_{j}^{n}(v) $$ dove \( \Delta^{r,0}P{i,j} = \Delta^{r-1,0}P_{i+1,j}-\Delta^{r-1,0}P_{i,j} \) e similmente la derivata \(s\)-esima su \(v\) è: $$ \frac {\partial} {\partial u} B^{m,n}(u,v)= \frac {m!}{(m-s)!} \sum_{i=0}^m \sum_{j=0}^{n-s} \Delta^{0,s}P_{i,j} b_{j}^{n-s}(u)b_{i}^{m}(u) $$ dove \( \Delta^{0,s}P_{i,j} = \Delta^{0,s-1}P_{i+1,j}-\Delta^{0,s-1}P_{i,j} \)Camera
La camera è l'oggetto che ci permette di visualizzare gli
oggetti tridimensionali in una finestra bidimensionale dello schermo.
Una camera prospettica utilizza delle proiezioni prospettiche in modo che nella scena come nella realtà gli oggetti vicini si vedono più grandi che gli oggetti lontani. Un'altra proiezione utilizzata è quella ortogonale dove la distanza tra i punti rimane la stessa anche quando ci si allontana dalla sorgente di visione, la proiezione ortogonale è utile quando si vuole visualizzare un oggetto in una particolare angolazione, per esempio dall'alto o da destra, in modo da comprendere la posizione dei punti senza la distorsione provocata dalla distanza.
La tecnica utilizzata è quella usata dalle più importanti librerie grafiche OpenGL o le Direct3D e si chiama Frustum View.
Una frustum view è definita dai seguenti parametri \( (near,far,right,left,top,bottom) \) che definiscono i piani nei quali la scena è racchiusa, quindi \(near\) è la distanza tra la camera e il piano più vicino, \(far\) è la distanza con il piano più lontano, \( (right,left,top,bottom) \) sono le distanze dal piano destro, sinistro, il piano alto e il piano basso.
Gli ultimi 4 parametri possono essere sostituiti con 2 parametri più significativi, il primo è \(aspect \) che corrisponde a \(aspect= \frac{width}{height} \) dove \(right-left=width\) e \(top-bottom=height\).
Il secondo è FOV (Field of View o campo di visione) \( 0\leq FOV<180 \), che rappesenta quanto largo è l'angolo di visione, variando il FOV si può notare un effetto zoom.
Il concetto basilare è il mantenimento dei rapporti, quindi con un ipotetico punto \(P\) viene proiettato a distanza \(d\) attraverso la seguente legge: $$ \frac {p_x} {p_z}=\frac {q_x}{-d} $$
cioè il rapporto \(x/z\) del punto \(P\) con il punto proiettato \(Q\) è lo stesso, perciò si ha che: $$ q_x= -d \frac {p_x} {p_z} $$ L'idea è che la matrice deve dare il senso di distanza ma deve anche restituire dei punti compresi in un quadrato con \(x,y,z\) compresi tra \([-1,+1]\). A causa della distanza un punto \(P\) che giace su un piano \(near\) avrà \(z=-n\) e \(x\) e \(y\): $$ x= - \frac {n} {P_z}P_x $$ $$ y= - \frac {n} {P_z}P_y $$ Ora per ridurre i punti a quelli compresi nel View Frustum deve valere anche: $$ x'=2 \frac {x-l} {r-l} -1 $$ $$ y'=2 \frac {y-l} {r-l} -1 $$ Sostituendo si ottiene: $$ x'=2 \frac { - \frac {n} {P_z}P_x -l} {r-l} -1 $$ $$ x'=2n \frac {1} {r-l} \frac {-P_x} {P_z} - \frac {2l} {r-l} - \frac {r-l} {r-l} $$ $$ x'=2n \frac {1} {r-l} \frac {-P_x} {P_z} - \frac {r+l} {r-l} $$ Ugualmente per la \(z\) se vogliamo mantenere le relazioni di distanza dobbiamo fare in modo che il piano del \(far\) vada a \(-f \rightarrow 1\) e del \(near\) vada a \(-n \rightarrow -1\) attraverso un interpolazione lineare, perciò scriviamo: $$ -1 = \frac {A}{-n}+B $$ $$ 1 = \frac {A}{-f}+B $$
Dalla prima equazione otteniamo: $$ A = (-1-B)(-n) $$ Sostituendo la \(A\) nella seconda equazione: $$ 1 = \frac {n+nB}{-f}+B $$ $$ 1 = \frac {n+nB-fB}{-f} $$ $$ \frac {nB-fB}{-f} = 1 + \frac {n}{-f} $$ $$ \frac {nB-fB}{-f} = 1 + \frac {n}{+f} $$ $$ \frac {f-n}{f}B = \frac {f+n}{f} $$ $$ B = \frac {f+n}{f-n} $$ Da cui otteniamo \(A\): $$ -1 = \frac {A}{-n}+\frac {f+n}{f-n} $$ $$ \frac {A}{n} = \frac {f+n}{f-n}+1 $$ $$ \frac {A}{n} = \frac {f+n+f-n}{f-n} $$ $$ A = \frac {2fn}{f-n} $$ Otteniamo quindi una matrice del tipo: $$ P = \begin{bmatrix} \frac {2 n}{r-l} & 0 & \frac {r+l} {r-l} & 0 \\ 0 & \frac {2 n} {t-b} & \frac {t+b} {t-b} & 0 \\ 0 & 0 & -\frac {n+f} {f-n} & -\frac {2 n f} {f-n} \\ 0 & 0 & -1 & 0 \end{bmatrix} $$ Si può trovare anche una definizione diversa a seconda di come è stato orientato l'asse \(z\): $$ P = \begin{bmatrix} \frac {2 n}{r-l} & 0 & -\frac {r+l} {r-l} & 0 \\ 0 & \frac {2 n} {t-b} & -\frac {t+b} {t-b} & 0 \\ 0 & 0 & \frac {n+f} {f-n} & \frac {2 n f} {f-n} \\ 0 & 0 & 1 & 0 \end{bmatrix} $$
O altriementi esiste una formulazione equivalente attraverso i parametri \(aspect\) e \(FOV\): $$ P = \begin{bmatrix} \frac {1}{aspect \text{ } tan(FOV/2)} & 0 & 0 & 0 \\ 0 & \frac {1} {tan(FOV/2)} & 0 & 0 \\ 0 & 0 & -\frac {n+f} {f-n} & - \frac {2 n f} {f-n} \\ 0 & 0 & -1 & 0 \end{bmatrix} $$
Ora che abbiamo capito come sono fatte le matrici di proiezione, esponiamo i passaggi che trasformano le coordinate di un punto nelle coordinate di una finestra di una scena bidimensionale. Il primo passaggio sposta le coordinate di un punto nelle coordinate della camera, attraverso una matrice di trasposizione $$ T = \begin{bmatrix} 1 & 0 & 0 & -eye_x \\ 0 & 1 & 0 & -eye_y \\ 0 & 0 & 1 & -eye_z \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ una matrice ortonormale trasforma il sistema di riferimento di un punto nel mondo nel sistema di riferimento della camera. $$ R = \begin{bmatrix} S_x & S_y & S_z & 0 \\ U_x & U_y & U_z & 0 \\ F_x & F_y & F_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ dove \(F,S,U\) sono i vettori unitari che definiscono il sistema di riferimento della camera: $$ F=\frac {at - eye}{||at - eye||} $$ $$ S = F \times up $$ $$ U = S \times F $$ \(F\) rappresenta il vettore dall'\(eye\) verso il \(target\), mentre \(S\) è il vettore ortogonale a \(F\) e a un vettore che indica la direzione verticale \(up=(0,1,0)\), il quale serve per ottenere \( S \) da \( F \), successivamente si ottiene \(U\) che rappresenta il vettore dell'asse verticale ed è ortogonale a \(F\) e a \(S\).
Si ottiene la proiezione \(P'\) a partire da un punto \( p=(x,y,z) \) calcolando: $$ P' = P R T p $$ Ottenuto \(P'\) abbiamo un punto \(x,y,z,w\) con \(x,y,z\) compresi tra \([-1,1]\), il passo successivo è dividere l'intero vettore per \(w\), e calcolare le coordinate della finestra \(x'',y''\) come: $$ x''=(1+x)\frac {width} 2 $$ $$ y''=(1+y)\frac {height} 2 $$
Una camera prospettica utilizza delle proiezioni prospettiche in modo che nella scena come nella realtà gli oggetti vicini si vedono più grandi che gli oggetti lontani. Un'altra proiezione utilizzata è quella ortogonale dove la distanza tra i punti rimane la stessa anche quando ci si allontana dalla sorgente di visione, la proiezione ortogonale è utile quando si vuole visualizzare un oggetto in una particolare angolazione, per esempio dall'alto o da destra, in modo da comprendere la posizione dei punti senza la distorsione provocata dalla distanza.
La tecnica utilizzata è quella usata dalle più importanti librerie grafiche OpenGL o le Direct3D e si chiama Frustum View.
Una frustum view è definita dai seguenti parametri \( (near,far,right,left,top,bottom) \) che definiscono i piani nei quali la scena è racchiusa, quindi \(near\) è la distanza tra la camera e il piano più vicino, \(far\) è la distanza con il piano più lontano, \( (right,left,top,bottom) \) sono le distanze dal piano destro, sinistro, il piano alto e il piano basso.
Gli ultimi 4 parametri possono essere sostituiti con 2 parametri più significativi, il primo è \(aspect \) che corrisponde a \(aspect= \frac{width}{height} \) dove \(right-left=width\) e \(top-bottom=height\).
Il secondo è FOV (Field of View o campo di visione) \( 0\leq FOV<180 \), che rappesenta quanto largo è l'angolo di visione, variando il FOV si può notare un effetto zoom.
Il concetto basilare è il mantenimento dei rapporti, quindi con un ipotetico punto \(P\) viene proiettato a distanza \(d\) attraverso la seguente legge: $$ \frac {p_x} {p_z}=\frac {q_x}{-d} $$
cioè il rapporto \(x/z\) del punto \(P\) con il punto proiettato \(Q\) è lo stesso, perciò si ha che: $$ q_x= -d \frac {p_x} {p_z} $$ L'idea è che la matrice deve dare il senso di distanza ma deve anche restituire dei punti compresi in un quadrato con \(x,y,z\) compresi tra \([-1,+1]\). A causa della distanza un punto \(P\) che giace su un piano \(near\) avrà \(z=-n\) e \(x\) e \(y\): $$ x= - \frac {n} {P_z}P_x $$ $$ y= - \frac {n} {P_z}P_y $$ Ora per ridurre i punti a quelli compresi nel View Frustum deve valere anche: $$ x'=2 \frac {x-l} {r-l} -1 $$ $$ y'=2 \frac {y-l} {r-l} -1 $$ Sostituendo si ottiene: $$ x'=2 \frac { - \frac {n} {P_z}P_x -l} {r-l} -1 $$ $$ x'=2n \frac {1} {r-l} \frac {-P_x} {P_z} - \frac {2l} {r-l} - \frac {r-l} {r-l} $$ $$ x'=2n \frac {1} {r-l} \frac {-P_x} {P_z} - \frac {r+l} {r-l} $$ Ugualmente per la \(z\) se vogliamo mantenere le relazioni di distanza dobbiamo fare in modo che il piano del \(far\) vada a \(-f \rightarrow 1\) e del \(near\) vada a \(-n \rightarrow -1\) attraverso un interpolazione lineare, perciò scriviamo: $$ -1 = \frac {A}{-n}+B $$ $$ 1 = \frac {A}{-f}+B $$
Dalla prima equazione otteniamo: $$ A = (-1-B)(-n) $$ Sostituendo la \(A\) nella seconda equazione: $$ 1 = \frac {n+nB}{-f}+B $$ $$ 1 = \frac {n+nB-fB}{-f} $$ $$ \frac {nB-fB}{-f} = 1 + \frac {n}{-f} $$ $$ \frac {nB-fB}{-f} = 1 + \frac {n}{+f} $$ $$ \frac {f-n}{f}B = \frac {f+n}{f} $$ $$ B = \frac {f+n}{f-n} $$ Da cui otteniamo \(A\): $$ -1 = \frac {A}{-n}+\frac {f+n}{f-n} $$ $$ \frac {A}{n} = \frac {f+n}{f-n}+1 $$ $$ \frac {A}{n} = \frac {f+n+f-n}{f-n} $$ $$ A = \frac {2fn}{f-n} $$ Otteniamo quindi una matrice del tipo: $$ P = \begin{bmatrix} \frac {2 n}{r-l} & 0 & \frac {r+l} {r-l} & 0 \\ 0 & \frac {2 n} {t-b} & \frac {t+b} {t-b} & 0 \\ 0 & 0 & -\frac {n+f} {f-n} & -\frac {2 n f} {f-n} \\ 0 & 0 & -1 & 0 \end{bmatrix} $$ Si può trovare anche una definizione diversa a seconda di come è stato orientato l'asse \(z\): $$ P = \begin{bmatrix} \frac {2 n}{r-l} & 0 & -\frac {r+l} {r-l} & 0 \\ 0 & \frac {2 n} {t-b} & -\frac {t+b} {t-b} & 0 \\ 0 & 0 & \frac {n+f} {f-n} & \frac {2 n f} {f-n} \\ 0 & 0 & 1 & 0 \end{bmatrix} $$
O altriementi esiste una formulazione equivalente attraverso i parametri \(aspect\) e \(FOV\): $$ P = \begin{bmatrix} \frac {1}{aspect \text{ } tan(FOV/2)} & 0 & 0 & 0 \\ 0 & \frac {1} {tan(FOV/2)} & 0 & 0 \\ 0 & 0 & -\frac {n+f} {f-n} & - \frac {2 n f} {f-n} \\ 0 & 0 & -1 & 0 \end{bmatrix} $$
Da punto a coordinate finestra
L'origine di una camera in una frustum view è definita a partire da due punti \(eye\) e \(target\) e rappresentano rispettivamente il punto di origine della camera e il punto in cui essa punta.Ora che abbiamo capito come sono fatte le matrici di proiezione, esponiamo i passaggi che trasformano le coordinate di un punto nelle coordinate di una finestra di una scena bidimensionale. Il primo passaggio sposta le coordinate di un punto nelle coordinate della camera, attraverso una matrice di trasposizione $$ T = \begin{bmatrix} 1 & 0 & 0 & -eye_x \\ 0 & 1 & 0 & -eye_y \\ 0 & 0 & 1 & -eye_z \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ una matrice ortonormale trasforma il sistema di riferimento di un punto nel mondo nel sistema di riferimento della camera. $$ R = \begin{bmatrix} S_x & S_y & S_z & 0 \\ U_x & U_y & U_z & 0 \\ F_x & F_y & F_z & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ dove \(F,S,U\) sono i vettori unitari che definiscono il sistema di riferimento della camera: $$ F=\frac {at - eye}{||at - eye||} $$ $$ S = F \times up $$ $$ U = S \times F $$ \(F\) rappresenta il vettore dall'\(eye\) verso il \(target\), mentre \(S\) è il vettore ortogonale a \(F\) e a un vettore che indica la direzione verticale \(up=(0,1,0)\), il quale serve per ottenere \( S \) da \( F \), successivamente si ottiene \(U\) che rappresenta il vettore dell'asse verticale ed è ortogonale a \(F\) e a \(S\).
Si ottiene la proiezione \(P'\) a partire da un punto \( p=(x,y,z) \) calcolando: $$ P' = P R T p $$ Ottenuto \(P'\) abbiamo un punto \(x,y,z,w\) con \(x,y,z\) compresi tra \([-1,1]\), il passo successivo è dividere l'intero vettore per \(w\), e calcolare le coordinate della finestra \(x'',y''\) come: $$ x''=(1+x)\frac {width} 2 $$ $$ y''=(1+y)\frac {height} 2 $$
Movimento della pallina
Scopo della pallina è muoversi discendendo giù per la
superficie di Bézier modellata dall'utente, la tecnica che
ho utilizzato per il movimento della pallina è il concetto di discesa del gradiente.
Dalle serie di Taylor sappiamo che:
$$f(x+h) = f(x)+\bigtriangledown f(x)h+o(h) $$
dove \(h\in\mathbb{R}\).
Se \( \bigtriangledown f(x)<0 \) significa che muovendosi di
\(h>0\) la funzione decresce, ne deduciamo che ci muoveremo in
direzione \( x_{t+1}=x_{t} + \Delta \), mentre se
\( \bigtriangledown f(x)>0 \) significa che la funzione
sta crescendo, dobbiamo quindi muoverci in direzione opposta
\( x_{t+1}=x_{t} - \Delta \).
Definiamo quindi \( \Delta=-\delta \bigtriangledown f(x) \), dove \( \delta \) è un fattore di scala, io l'ho impostato a \(0.0001\). Un passo di discesa del gradiente è quindi: $$ x_{t+1}=x_{t} - \delta \bigtriangledown f(x) $$ Nel nostro specifico problema però \(f\) è definita come \(f: (u,v) \rightarrow (x,y,z) \), perciò ho dovuto calcolare il gradiente attraverso le derivate su \( u \) e \( v \), ottengo quindi: $$ \frac {\partial f(u',v')} {\partial u} = \begin{pmatrix} x_u \\ y_u \\ z_u \end{pmatrix} $$ $$ \frac {\partial f(u',v')} {\partial u} = \begin{pmatrix} x_v \\ y_v \\ z_v \end{pmatrix} $$ Cioè le 2 derivate parviali su \(u\) e \(v\) nel punto \( (u',v') \), volendo muovere la pallina verso il basso ho considerato solo l'asse verticale cioè \( y \) ed ho escluso quindi i valori \(x_u,z_u,z_u,z_v\) che rappresentano il piano orizzontale, ho ottenuto quindi: $$ u_{t+1}=u_{t} - \delta \bigtriangledown f(u_t,v_t) $$ $$ v_{t+1}=v_{t} - \delta \bigtriangledown f(u_t,v_t) $$ A questo punto calcolando in \(f(u_{t+1},v_{t+1}) \) si ottiene la posizione della pallina all'iterazione successiva e tale che \(f(u_{t+1},v_{t+1}).y < f(u_{t},v_{t}).y \).
Per dare un maggior effetto di movimento, ho creato un vettore velocità \( vel \) il quale è la somma dei vettori di direzione ad ogni iterazione, all'inizio \(vel = (0,0) \), ad ogni iterazione: $$ vel.u_{t+1}=vel.u_{t} - \delta \bigtriangledown f(u_t,v_t) $$ $$ vel.v_{t+1}=vel.v_{t} - \delta \bigtriangledown f(u_t,v_t) $$ Poi ottengo: $$ u_{t+1}=u_{t} + t*vel.u_{t+1} $$ $$ v_{t+1}=v_{t} + t*vel.v_{t+1} $$ Ciò aumenta la lunghezza del vettore di direzione in funzione dei passi precedenti, se la pallina scende la lunghezza aumenta e la pallina va più veloce, se la pallina sale per effetto del vettore allora la lunghezza diminuisce.
Per evitare che la pallina si muovi di movimento perpetuo all'interno di una valle, ho creato un effetto di atrito, il risultato è: $$ vel.u_{t+1}=vel.u_{t} - vel.u_{t}*norm.y*friction - \delta \bigtriangledown f(u_t,v_t) $$ $$ vel.v_{t+1}=vel.v_{t} - vel.v_{t}*norm.y*friction - \delta \bigtriangledown f(u_t,v_t) $$ dove \(norm = || {\mathrm d v} \times {\mathrm d u}|| \) mentre \(friction\) è un valore che indica il coefficiente di atrito che ho impostato a \(0.03\).
Infine, se la pallina oltrepassa il bordo della superficie cade per effetto della gravità.
Definiamo quindi \( \Delta=-\delta \bigtriangledown f(x) \), dove \( \delta \) è un fattore di scala, io l'ho impostato a \(0.0001\). Un passo di discesa del gradiente è quindi: $$ x_{t+1}=x_{t} - \delta \bigtriangledown f(x) $$ Nel nostro specifico problema però \(f\) è definita come \(f: (u,v) \rightarrow (x,y,z) \), perciò ho dovuto calcolare il gradiente attraverso le derivate su \( u \) e \( v \), ottengo quindi: $$ \frac {\partial f(u',v')} {\partial u} = \begin{pmatrix} x_u \\ y_u \\ z_u \end{pmatrix} $$ $$ \frac {\partial f(u',v')} {\partial u} = \begin{pmatrix} x_v \\ y_v \\ z_v \end{pmatrix} $$ Cioè le 2 derivate parviali su \(u\) e \(v\) nel punto \( (u',v') \), volendo muovere la pallina verso il basso ho considerato solo l'asse verticale cioè \( y \) ed ho escluso quindi i valori \(x_u,z_u,z_u,z_v\) che rappresentano il piano orizzontale, ho ottenuto quindi: $$ u_{t+1}=u_{t} - \delta \bigtriangledown f(u_t,v_t) $$ $$ v_{t+1}=v_{t} - \delta \bigtriangledown f(u_t,v_t) $$ A questo punto calcolando in \(f(u_{t+1},v_{t+1}) \) si ottiene la posizione della pallina all'iterazione successiva e tale che \(f(u_{t+1},v_{t+1}).y < f(u_{t},v_{t}).y \).
Per dare un maggior effetto di movimento, ho creato un vettore velocità \( vel \) il quale è la somma dei vettori di direzione ad ogni iterazione, all'inizio \(vel = (0,0) \), ad ogni iterazione: $$ vel.u_{t+1}=vel.u_{t} - \delta \bigtriangledown f(u_t,v_t) $$ $$ vel.v_{t+1}=vel.v_{t} - \delta \bigtriangledown f(u_t,v_t) $$ Poi ottengo: $$ u_{t+1}=u_{t} + t*vel.u_{t+1} $$ $$ v_{t+1}=v_{t} + t*vel.v_{t+1} $$ Ciò aumenta la lunghezza del vettore di direzione in funzione dei passi precedenti, se la pallina scende la lunghezza aumenta e la pallina va più veloce, se la pallina sale per effetto del vettore allora la lunghezza diminuisce.
Per evitare che la pallina si muovi di movimento perpetuo all'interno di una valle, ho creato un effetto di atrito, il risultato è: $$ vel.u_{t+1}=vel.u_{t} - vel.u_{t}*norm.y*friction - \delta \bigtriangledown f(u_t,v_t) $$ $$ vel.v_{t+1}=vel.v_{t} - vel.v_{t}*norm.y*friction - \delta \bigtriangledown f(u_t,v_t) $$ dove \(norm = || {\mathrm d v} \times {\mathrm d u}|| \) mentre \(friction\) è un valore che indica il coefficiente di atrito che ho impostato a \(0.03\).
Infine, se la pallina oltrepassa il bordo della superficie cade per effetto della gravità.
Riferimenti
F. Yamaguchi: "Curves and Surfaces in Computer Aided Geometric Design", ed. Springer Verlag, Berlin, 1988.
Lengyel, Eric, Mathematics for 3D Game Programming and Computer Graphics,
Second Edition, Charles River Media, 2003.
http://www.mat.unimi.it/users/alzati/Geometria_Computazionale_98-99/apps/liquido/