% % \articolo{VoXel --- teoria generale ed approccio alla programmazione di un motore di rendering}{Francesco Leonardi e Giuliano Pochini} \index{Leonardi!articolo di} \index{Pochini!articolo di} %\noindent(Voxel Space type-1, Black Blade software design, 1996) %\begin{flushleft} %\includegraphics[width=2cm]{leonardi/pics/bbdlogo.eps} %\end{flushleft} \paragrafo{Introduzione} Su \A sono state ormai implementate pressoché tutte le più famose tecniche di rendering di ambienti tridimensionali basate su poligoni e texture mapping. Tuttavia non hanno mai preso campo alcuni algoritmi di resa molto interessanti. Tra questi una particolare tecnica per disegnare paesaggi di grande effetto e ad alta velocità, solitamente denominata Voxel\index{Voxel} space. La parola Voxel deriva dalla fusione di due termini: volume e pixel. Come si può intuire tende ad associare un volume ben preciso, il nostro mattoncino base, ad un pixel del raster di generazione, cioè ad un'entità che sappiamo essere strettamente bidimensionale, ma questo verrà spiegato nel dettaglio in seguito. Il primo passo rilevante nella tecnologia VoxelSpace\TM{} applicata ad un gioco lo dobbiamo alla NovaLogic e ad i suoi bestseller della serie {\it Comanche\index{Comanche}}. Premetto che i sorgenti mostrati nel seguito sono scritti usando la sintassi standard del BlitzBasic 2 e per compattezza non ho riportato le parti relative alle inizializzazioni di schermi, finestre, eccetera. \paragrafo{Teoria} Sebbene apparentemente complesso, il Voxel si basa su un'idea molto semplice ed intuitiva: non è altro che un algoritmo di texture mapping per superfici piane orizzontali, con la differenza che per ogni punto, oltre ad avere un colore, abbiamo anche l'altitudine assoluta dell'elemento base rispetto al piano. Iniziamo allora con il texture mapping. D'ora in poi seguirò per comodità questa convenzione per gli assi cartesiani nello spazio: $X$ verso destra, $Z$ verso l'alto e $Y$ verso la profondità (ponendo il sistema fronte a me). \begin{center} \includegraphics{leonardi/pics/assi3d.1} \end{center} Assumiamo inoltre un piano base per la generazione dello spazio di dimensione pari a $320\times256$ pixel. Data una bitmap, la nostra texture, userò le classiche formule: % \begin{eqnarray*} x\ped{video} = {\rm zoom} \times {X\over Y} + 160\\ y\ped{video} = {\rm zoom} \times {Z\over Y} + 128 \end{eqnarray*} % dove 160 e 128 sono le coordinate del centro dello schermo. Le formule sono ricavate da una semplice similitudine tra triangoli per trasformare le coordinate spaziali in coordinate sul video. Prendendo ad uno ad uno i punti della bitmap, calcolando le coordinate sul video e stampandoli, si potrà osservare un primo primitivo texture mapping sul nostro piano di riferimento: \begin{codestyle} Sorgente 1 ; Texture in Txtr(256,64) Z = 50 For Y = 0 To 255 Step 1 For X = -128 To 127 Step 1 tb0 = Txtr(X + 128, -Y AND 63) ;Legge un punto della texture vY = 128 + 256 * Z / Y ;Calcola le vX = 160 + 256 * X / Y ;coordinate sul ;video Plot vX, vY, tb0 ;Traccia il punto Next X Next Y \end{codestyle} Bisogna però considerare che questo approccio ha due grossi difetti. Per prima cosa, nelle zone più vicine all'osservatore i punti non sono contigui. Di conseguenza non si ha una texture di buona qualità ma solo una ``puntinatura''. L'altro difetto è che nelle parti più lontane, per lo stesso motivo di prima, vengono tracciati più punti del necessario rallentando fortemente l'operazione. Per eliminare questi difetti, invece di scandire la bitmap e calcolare direttamente le coordinate sul video, occorre scandire prima un'area sul video e successivamente calcolarne le coordinate sulla bitmap. A questo punto occorre ottenere $X$ e $Y$ in funzione di $Z$, $v_x$ e $v_y$. Partendo dalle formule usate nel listato precedente si ha % \begin{eqnarray*} v_x &=& 160 + 256 {X\over Y} \\ v_y &=& 128 + 256 {Z\over Y} \end{eqnarray*} % ed eseguendo alcuni semplici passaggi algebrici, otteniamo: % \begin{eqnarray*} X &=& Z {v_x - 160\over v_y - 128}\\ Y &=& Z {256\over v_y - 128} \end{eqnarray*} % % (GG): Queste sono le formule originali. % % (1) vX - 160 = (256 * X) / Y % (2) vY - 128 = (256 * Z) / Y % % dalla (1) ricavo X: (3) X = Y * (vY - 128) / 256 % dalla (2) ricavo Y: (4) Y = (256 * Z) / (vY - 128) % sostituisco la (4) nella (3): % X = ((256 * Z) / (vY - 128)) * ((vY - 128) / 256) % % Quindi: % % Y = (256 * Z) / (vY - 128) % X = Z * ((vX - 160) / ( vY - 128)) Ora siamo finalmente in grado di calcolare le coordinate $X$ e $Y$ sulla bitmap, date le coordinate $v_x$ e $v_y$ sul video. Aggiungo inoltre il calcolo della rotazione attorno all'asse $Z$ in modo da poter ruotare la visuale in tutte le direzioni parallele al piano. \begin{codestyle} Sorgente 2 ; Texture in Txtr(256,64) PosX = 128 PosY = 0 AngZ = 10 * 6.2832 / 360 ;Rotazione ;attorno a Z Z = 50 ;Altitudine For vY = 255 To 129 Step -1 For vX = 0 To 319 Step 1 Y0 = 256 * Z / (vY - 128) ;Calcola le coordinate ;sulla texture X0 = Z * (vX - 160) / (vY - 128) X = X0 * Cos(AngZ) - Y0 * Sin(AngZ) ;Effettua la rotazione Y = X0 * Sin(AngZ)+ Y0 * Cos(AngZ) ;attorno all'asse Z tb0 = Txtr((X + PosX) AND 255, (-Y + PosY) AND 63) ;Legge il ;colore Plot vX, vY, tb0 ;Lo stampa a video Next vX Next vY \end{codestyle} Bene, a questo punto il risultato è decisamente migliore, ma il programma è divenuto molto lento. Un metodo comunemente usato per calcorare rapidamente una serie di valori (in questo caso le coordinate sulla texture) che variano linearmente, è quello di calcolare i valori che la variabile assume all'inizio ed alla fine del ciclo; poi assegnare alla variabile il valore iniziale e calcolare tutti i successivi sommando una quantità fissa, calcolata con: % $$ {\mbox{valore finale} - \mbox{valore iniziale}}\over{\mbox{numero di cicli}} $$ % Si possono un questo modo risparmiare molti calcoli (in questo caso circa 640 divisioni, moltiplicazioni, seni e coseni per ogni linea). \begin{codestyle} Sorgente 3 ; Texture in Txtr(256,64) PosX = 128 PosY = 0 AngZ = 0 * 6.2832 / 360 Z = 50 For vY = 255 To 129 Step -1 iY0 = 256 * Z / (vY - 128) ;Calcola coordinate iniziali... iX0 = Z * (0 - 160) / (vY - 128) fY0 = 256 * Z / (vY - 128) ;...e quelle ;finali fX0 = Z * (319 - 160) / (vY - 128) ;sulla ;texture iX = iX0 * Cos(AngZ) - iY0 * Sin(AngZ) ;Ora le ruota iY = iX0 * Sin(AngZ) + iY0 * Cos(AngZ) fX = fX0 * Cos(AngZ) - fY0 * Sin(AngZ) fY = fX0 * Sin(AngZ) + fY0 * Cos(AngZ) dX = (fX - iX) / 320 ;Calcola il passo dY = (fY - iY) /320 X = iX + PosX ;Posizione iniziale sulla Y = iY + PosY ;texture relative al ;punto di vista For vX = 0 To 319 Step 1 tb0 = Txtr(X AND 255, (-Y) AND 63) ;Legge il colore Plot vX, vY, tb0 ;Stampa il punto X + dX ;Calcola le nuove Y + dY ;coordinate nella texture Next vX Next vY \end{codestyle} Ora il programma è circa sette volte più veloce di prima. Naturalmente ci sono molte altre ottimizzazioni da poter fare, ma ciò esula dagli scopi di questo articolo. Procediamo dunque a trasformarlo in un Voxel vero e proprio. Occorre anzitutto realizzare un ``paesaggio'' su cui lavorare. Lo si può creare facilmente generando un frattale di tipo ``plasma'', per le altitudini, e manipolando quest'ultimo opportunamente con un programma di disegno per ottenere la mappa dei colori. Altre vie per ottenere risultati migliori possono essere quelle che prevedono l'utilizzo di programmi di manipolazione GIS o {\it painter} a 24\unit{bit}. In questo modo è possibile ricreare un paesaggio in maniera fotorealistica, l'ideale per una simulazione. Il tracciamento della scena avviene allo stesso modo descritto nel sorgente del programma 3, ma con la differenza sostanziale che ora occorre anche considerare l'altitudine del punto rispetto al terreno. Data l'altitudine, si opera la trasformazione da 3D a 2D in modo analogo a come si è visto prima: % $$ v\ped{Alt} = {{\mbox{Scala Verticale}\times\mbox{Altitudine del punto}} \over\mbox{Distanza}} $$ % Ogni punto della mappa cromatica (che prima era la texture del piano) viene ora disegnato con una linea verticale che parte del livello del terreno, di coordinate $(v_x, v_y)$, e arriva fino all'altezza del punto appena calcolato $(v_x, v_y + v\ped{Alt})$. È inoltre consigliabile disegnare il paesaggio dall'osservatore verso la profondità. Questo permette, tenendo memorizzato il profilo dei monti, di tracciare solo la parte effettivamente visibile del paesaggio (circa il 60\% in totale, secondo mie stime) risparmiando una quantità notevole di tempo di CPU. \begin{codestyle} Sorgente 4 ; Mappa cromatica in Col(256,256) ; Mappa altimetrica in Map(256,256) Dim MaxVY.w(319) PosX = 174 ;Coordinata X PosY = 138 ;Coordinata Y AngZ.f = 20 * 6.2832 / 360 ;Angolo Z Z = 19 ;Coordinata Z Ridis: For t.w = 0 To 319 ;Inizializza il profilo dei monti MaxVY(t) = 255 ;alla coordinata Y Next t ;dell'ultima riga dello schermo vY = 600 Repeat iY0 = 256 * Z / (vY - 128) ;Calcola le ;coordinate iX0 = Z * (0-160) / (vY-128) ;iniziali... fY0 = 256 * Z / (vY - 128) ;... e quelle ;finali fX0 = Z * (319-160)/(vY-128) ;sulla mappa iX = iX0 * Cos(AngZ) - iY0 * Sin(AngZ) iY = iX0 * Sin(AngZ) + iY0 * Cos(AngZ) fX = fX0 * Cos(AngZ) - fY0 * Sin(AngZ) fY = fX0 * Sin(AngZ) + fY0 * Cos(AngZ) dX = (fX - iX) / 320 ;Calcola il passo dY = (fY - iY) / 320 X = iX + PosX ;Coordinate iniziali Y = iY + PosY ;sulla mappa For vX = 1 To 319 X AND 255.99998 ;X = X mod 256 Y AND 255.99998 ;Y = Y mod 256 Alt.w = Map(X,Y) - 128 ;Altitudine ;del punto videoY.w = vY + 64 * Alt / iY0 ;Altitudine sul video (vY+vAlt) If videoY < MaxVY(vX) ;Se una parte è ;visibile la ;disegna Line vX, MaxVY(vX), vX, videoY, Col(X,Y) MaxVY(vX) = videoY - 1 ;Aggiorna il ;profilo dei ;monti EndIf X + dX Y + dY Next vX If Joyb(1) Then End vY - (vY ASR 8) ;Prossima linea video Until vY <= 130 \end{codestyle} Il Voxel ha però alcuni difetti. Uno dei più evidenti è che non è possibile realizzare gli effetti di rollio\index{rollio} (rotazione lungo l'asse $Y$) e di beccheggio\index{beccheggio} (rotazione lungo l'asse $X$) in modo semplice, ovvero senza perdere il vantaggio principale del Voxel rispetto alle consuete tecniche vettoriali: la sua estrema velocità in rapporto all'alta qualità raggiunta (ricordo che non stiamo parlando di velocità assoluta). Per questa ragione bisogna ricorrere a dei trucchi per risolvere, almeno in parte, questi problemi. L'effetto del rollio si può realizzare ruotando l'intera immagine solo dopo aver terminato il rendering del singolo fotogramma. Oppure si ricorre ad uno ``stiramento'' dell'immagine, cosa che evita la dispendiosa rotazione. Sebbene quest'ultimo possa sembrare un metodo un po' grezzo ed impreciso (ed in effetti lo è\ldots), in pratica la distorsione introdotta si nota molto poco per rotazioni sino a circa 35 gradi, a meno che non ci si trovi davanti a dei profili quasi verticali, cosa praticamente improbabile in paesaggi montuosi. Anche il beccheggio si può realizzare con un trucco. Semplicemente si trasla l'immagine verticalmente e anche in questo caso per inclinazioni contenute è difficile notare che non si tratta di una vera rotazione attorno all'asse $X$. A questo punto tutto il lavoro per rendere il nostro motore Voxel adatto ad usi pratici riguarda esclusivamente le ottimizzazioni. Tuttavia per poterlo utilizzare nella realizzazione di un gioco, occorre risolvere un altro problema: come disegnare gli oggetti statici e quelli in movimento (missili, aerei, etc.) in modo che appaiano con la giusta priorità (sia che si utilizzino allo scopo oggetti bitmap che vettoriali)? A causa della decisione di disegnare il paesaggio partendo dall'osservatore, l'algoritmo del ``pittore'' non è direttamente applicabile. Una soluzione consiste nel preparare, prima di inziare a tracciare il paesaggio, un elenco ordinato dal più vicino al più lontano di tutti oggetti da tracciare. La routine Voxel dovrà controllare, alla fine di ogni linea, se la prossima linea sarà più lontana del primo oggetto. Se lo è, allora memorizza il profilo dei monti (che non corrisponde alla sezione del paesaggio!) e passa a considerare il prossimo oggetto nella lista. Gli oggetti più lontani della massima profondità di campo del paesaggio dovranno essere trattati a parte. La fase successiva consiste nel tracciare gli oggetti. Si procede dunque in senso inverso, cioè a partire da lontano ed avvicinandosi, sfruttando perciò l'algoritmo del pittore, e disegnando ogni oggetto tenendo conto del rispettivo profilo dei monti precedentemente memorizzato, rispetto al quale l'oggetto deve apparire dietro. Qui di seguito potete osservare ancune immagini relative al Voxel space utilizzato per la realizzazione di un gioco. % % \newdimen\voxelfigwidth \voxelfigwidth=\columnwidth \divide\voxelfigwidth by 2 \advance\voxelfigwidth by -0.1cm % \begin{center} \includegraphics[width=\voxelfigwidth]{leonardi/pics/y1.eps} \includegraphics[width=\voxelfigwidth]{leonardi/pics/y2.eps}\\ \includegraphics[width=\voxelfigwidth]{leonardi/pics/y3.eps} \includegraphics[width=\voxelfigwidth]{leonardi/pics/y4.eps} \end{center} % e qui le corrispondenti mappe per la generazione del Voxel. % \begin{center} \includegraphics[width=\voxelfigwidth]{leonardi/pics/mapcroma.eps} \includegraphics[width=\voxelfigwidth]{leonardi/pics/mapeleva.eps} \end{center} \autore{Francesco Leonardi\\ e-mail: \c{leonardi@denise.shiny.it}\\[2ex] Giuliano Pochini}{} \citazione{\selectlanguage{english}Americans get paid for being clever, not for being right}{Donald Norman}