Texture Mapping
Copyright © 1996 by Mark Feldman
Traduzione di Paris Cristiano
Questo rappresenta l'anteprima di un articolo che verrá pubblicato sulla The Win95 Game Programmer's Encyclopedia. La Win95GPE é attesa da ormai qualche anno e sará disponibile presso il sito http://www.oocities.org/SiliconValley/2151
Introduzione
Nella PCGPE, Sean Barret pubblicó un interessante articolo sul texture mapping. In questa versione elaboreró molte delle idee che egli sviluppó. (L'articolo originale peccava di alcuni errori, che comunque sono stati corretti in questa versione).
Parlare di Texture Mapping implica naturalmente parlare di matematica. Potreste quindi aver bisogno di richiamare qualcuno di questi concetti dando un'occhiata all'articolo sulla Matematica 3D.
Vorrei inoltre far notare che in questa sede discuteremo del solo Texture Mapping, ovvero di quella tecnica che permette di mappare i texel sullo schermo. Se il vostro problema riguarda il decidere quali pixel dovrebbero essere disegnati e quali no, allora avete bisogno di articoli sulla rimozione delle linee nascoste [Hidden Surface Removal].
Di seguito troverete una tabella sulle varie tecniche discusse in questo articolo, unitamente ad alcuni giudizi da me espressi su ognuna. Questi risultati sono stati ottenuti attraverso la mia personale esperienza e in nessun modo vanno presi in considerazione come oro colato. Inoltre, alcune di queste tecniche possono essere modificate per ridurne l'accuratezza in favore di una maggiore velocitá, e viceversa.
| Tecnica | Accuratezza | Velocitá | Implementazione |
| "Perfect" Mapping: | Eccellente | Pessima | Facile |
| Affine Mapping: | Pessima | Eccellente | Facile |
| Area Subdivision: | Ok | Scarsa | Ok |
| Scanline Subdivision: | Eccellente | Buona | Ok |
| Parabolic Mapping: | Scarsa | Buona | Facile |
| Hyperbolic Mapping: | Eccellente | Ok | Molto difficile |
| Constant-z Mapping: | Scarsa | Ok | Difficile |
Il seguente algoritmo implementa il "Perfect Mapping", un tipo di texture mapping corretto sotto il punto di vista della prospettiva. La prima volta che lo vidi fu nell'articolo di Sean Barrett nella PCGPE. Sean sfrutta 9 "numeri magici", che io amo presentare come 3 "vettori magici".
Innanzitutto avete bisogno di calcolare il vettore origine e i vettori perimetrali del poligono da mappare. Assumeró che il poligono sia un rettangolo. P1 sará il vertice in alto a sinistra, P2 quello in alto a destra e P3 quello in basso a sinistra. I vettori magici vengono calcolati cosí :
P = P1
M = P2 - P1 la direzione u nello spazio 3D
N = P3 - P1 la direzione v nello spazio 3D
A = P x N x é il prodotto vettoriale tra due vettori
B = M x P
C = N x M
(Osservate che M e N rappresentano la direzione che ciascuno degli assi percorre nello spazio. Io li ho calcolati automaticamente dai vertici del poligono, ma possono essere settati a valori differenti).
Per ogni pixel sullo schermo calcoliamo :
S = <screenx, screeny, DIST>
a = S * A
b = S * B
c = S * C
u = texturewidth * a / c ----> Larghezza della texture
v = textureheight * b / c ----> Altezza della texture
col = texture texel at <u, v> ----> Indica il pixel di coordinate (u,v) sulla texture
Draw pixel at <screenx, screeny> with color 'col' ----> Disegno il pixel
Una volta che la routine basilare é stata scritta, si puó cominciare ad ottimizzarla. Personalmente preferisco usare una classe C++ con alcuni operatori overloaded :
class CPoint3D
{
public:
// Costruttori
CPoint3D() {};
CPoint3D(CPoint3D &p) {*this = p};
CPoint3D(double xi, double yi, double zi) {x=xi; y=yi; z=zi;}
// Addizione e sottrazione vettoriale
// Prodotto scalare
// Prodotto vettoriale
// E finalmente le coordinate x,y,z
double x,y,z;
};
Qui ho mostrato solo gli operatori piú comuni, ma il codice completo contiene anche gli operatori +=, -=, di scala etc.
E' possibile inizializzare i nostri vettori magici cosí :
CPoint3D P(P1);
CPoint3D M(P2 - P1);
CPoint3D N(P3 - P1);
CPoint3D A(P % N);
CPoint3D B(M % P);
CPoint3D C(N % M);
Ho usato il simbolo di modulo (%) per denotare il prodotto vettoriale tra due vettori.
Il nostro loop piú interno per una singola linea dovrebbe essere simile a questo:
for (screenx=x1; screenx<x2; screenx++)
{
CPoint3D S(screenx, screeny, DIST);
double a = S * A;
double b = S * B;
double c = S * C;
u = texture.width*a/c;
v = texture.height*b/c;
color = texture.data[floor(v) * 256 + floor(u)];
SetPixel(screenx, screeny, color);
}
La prima cosa da osservare é che stiamo disegnando ogni linea da sinistra a destra, incrementando screenx di 1 ad ogni pixel disegnato. Possiamo usare questa osservazione per ottimizzare il calcolo di S e dell'indirizzo del pixel nel dispaly buffer. Ecco il nuovo loop:
CPoint3D S(x1, screeny, DIST);
char far * screen = &buffer[(100-screeny)*320+x1-160]; // o quello che volete
for (screenx=x1; x<x2; screenx++)
{
double a = S * A;
double b = S * B;
double c = S * C;
S.x++;
u = texture.width*a/c;
v = texture.height*b/c;
*screen++ = texture.data[floor(v) * 256 + floor(u)];
}
La prossima ottimizzazione riguarda gli scalari a, b e c. Espandiamo il primo prodotto scalare, ottenendo = S.x*A.x + S.y*A.y + S.z*A.z. L'unico valore che cambia durante la scansione di una linea é S.x. Sappiamo inoltre che S.x é incrementato di 1 ad ogni iterazione del loop, cosí non ci rimane che aggiungere A.x ad a. Lo stesso ragionamento si puó fare per b e c. A questo punto non abbiamo piú bisogno di S, cosí possiamo rimuvere la linea che lo incrementa:
CPoint3D S(x1, y, DIST);
char far * screen = &buffer[(100-screeny)*320+x1-160]; // o quello che volete
double a = S * A;
double b = S * B;
double c = S * C;
for (x=x1; x<x2; x++)
{
u = texture.width*a/c;
v = texture.height*b/c;
*screen++ = texture.data[floor(v) * 256 + floor(u)];
a += A.x;
b += B.x;
c += C.x;
}
L'ultimo passo é quello di provare ad eliminare le due moltiplicazioni. Questo puó essere effettuato premoltiplicando A e B fuori dal loop. Notate che dobbiamo premoltiplicarli fuori anche del loop y, altrimenti verranno moltiplicati ogni volta per ogni linea:
A *= texture.width;
B *= texture.height;
.
.
.
y loop starts somewhere here
.
.
.
CPoint3D S(x1, y, DIST);
char far * screen = &buffer[y*320+x1]; // o quello che volete
double a = S * A;
double b = S * B;
double c = S * C;
for (x=x1; x<x2; x++)
{
u = a/c;
v = b/c;
*screen++ = texture.data[floor(v) * 256 + floor(u)];
a += A.x;
b += B.x;
c += C.x;
}
A questo punto siamo pronti per convertire il tutto in assembly o cominciare ad applicare altre ottimizzazioni, come la suddivisione delle linee di scansione.
L'Affine Mapping fa uso dell'interpolazione bilineare per visualizzare i poligoni. Semplicemente bisogna calcolare i texel alle estremitá di ogni linea di scansione, interpolando poi tra i due in maniera lineare. L'Affine Mapping é perfetto per la proiezione ortonormale. Infatti funziona molto bene quando l'angolo che intercorre tra il vettore della vista e quello normale alla superficie da disegnare é piccolo, cosicché, durante ogni linea di scansione, la coordinata z dei texel proiettati non varia sensibilmente. Tuttavia, non appena l'angolo tra la vista e la normale aumenta, l'oggetto comincia ad essere distorto. Questo difetto é particolarmente pronunciato quando l'oggetto é vicino al punto di vista, o ha un angolo molto elevato.
Nonostante questo ovvio problema, l'Affine Mapping é un algoritmo estremamente utile. Quando viene combinato con altre tecniche, puó aumentare significativamente la velocitá del rendering senza distorcere pesantemente gli oggetti. Vedremo poi come questo sia possibile.
In alcuni casi invece, l'Affine Mapping puó essere addirittura usato da solo, soprattutto quando la distanza Z rimane costanto lungo un'interna linea di scansione. Considerate ad esempio uno sprite 3D che normalmente appare sempre lo stesso da qualsiasi direzione lo si guardi. Per visualizzarlo, basterá utilizzare le equazioni prospettiche per determinarne le dimensioni, e poi utilizzare l'Affine Mapping per mappare su di esso la texture.
La serie di Wing Commander fece ancora meglio. I programmatori prepararono immagini degli sprite da angolazioni differenti. Al momento della visualizzazione era sufficiente selezionare l'immagine appropriata basandosi sulla posizione e sull'orientamento del punto di vista. Wolfenstein 3D andó ancora oltre, usando l'Affine Mapping per disegnare i muri, che venivano disegnati usando una linea di scansione verticale, visto che lungo tale linea, la coordinata Z era costante.
Major Strike e DOOM ovviamente andarono oltre, applicando questi concetti al disegno dei pavimenti e dei soffitti. I pavimenti ad esempio erano disegnati usando linee di scansione orizzontali, lungo le quali la coordinata Z rimaneva costante. Ad un certo punto sembró che questa tecnica potesse essere utilizzata per qualsiasi poligono orientato genericamente, ma questo introdusse una serie di problemi che vedremo in seguito (vedi la sezione sul constant-z).
Mi ricordo di aver visto un interessante programma sul Discovery Channel, nel quale si affermava che gli esseri umani tendevano ad orientarsi "verso l'alto". Gli astronauti, i paracadutisti e gli atleti devono perferzionarsi al fine di superare questa naturale tendenza e destreggiarsi efficacemente nello spazio. Ció traspare con maggiore evidenza dalla nostra architettura : le superfici lungo le quali camminiamo tendono ad essere orizzontali, mentre i muri tendono ad essere verticali.
Tale caratteristica della natura umana si applica specialmente ai videogiochi. Personalmente ritengo giochi come DOOM, Duke Nukem e Quake molto piú semplici da manovrare, proprio per il loro spiccato orientamento verso l'alto. In altri giochi invece, come Descent e Wing Commander, nonostante essi siano veramente ottimi, occorre piú tempo per destreggiarsi e spesso mi lasciano un senso di disorientamento.
Ovviamente questa é una notizia stupenda per noi programmatori, perché la maggior parte delle superfici da visualizzare saranno orizzontali o verticali, soprattutto se progetteremo un engine che allineerá corretamente l'utente ogni qualvolta egli si troverá su una superficie piatta. Scrivere routine extra che tengano conto di questi casi speciali puó risultare noioso, ma il lavoro sará alla fine ben ricompensato.
Questa sezione deve ancora essere scritta. L'Area Subdivision é molto simile all'Affine Mapping : in pratica si dividono i piú poligoni in pezzi piú piccoli, in modo da minimizzare l'errore di approssimazione.
Il primo a parlarmi di questo sistema fu Jouni Mannonen (DarkShade on #coders). Risulta essere molto simile all'Area Subdivision, solo che invece di partizionare un'area, viene suddivisa una singola scan-line.
L'Affine Mapping é estremamente veloce, ma gli errori si accumulano lungo una linea di scansione. Cosí, l'accuratezza della visualizzazione dipende in larga parte dalla lunghezza della linea di scansione. Lo Scan-Line Subdivision compensa gli errori suddividendo i segmenti e eliminado la propagazione dell'errore. Si ottengono numerosi vantaggi applicandolo:
La maggior parte dei pixel puó essere disegnata utilizzando l'affine mapping, rendendo questa tecnica molto piú veloce del perfect mapping. Sono presenti poi ulteriori vantaggi in termini di accuratezza :
Il Parabolic Mapping utilizza la curva di una parabola per disegnare con maggiore accuratezza dell'Affine Mapping al costo di una maggiore lentezza.
Assumete di voler disegnare 11 pixels sullo schermo, andando da x=50 -> x=60. Per rendere le cose piú semplici, assumeró che sottraiate 50 da ciascuna coordinata, in modo tale che l'intervallo ora sia x0=0 -> x2=10. Assumeremo poi che x1 sia il punto medio, i.e. x1=x2/2.
Assumeró poi che l'espressione della quadrica sia u = a*x^2 + b*x + c (v ha un'equazione simile, ma non voglio annoiarvi). E' possibile calcolare le incognite (a, b and c) calclando u0, u1 e u2 per x0, x1 e x2 rispettivamente risolvendo poi il seguente sistema di equazioni :
u0 = a*x0^2 + b*x0 + c (1)
u1 = a*x1^2 + b*x1 + c (2)
u2 = a*x2^2 + b*x2 + c (3)
Sappiamo ora che x0=0 e x1=x2/2, cosí da semplicare le equazioni sostituendo tutti i termini con x2, alla quale mi riferiró semplicemente con x:
u0 = a*0 + b*0 + c (4)
u1 = a*(x/2)^2 + b*(x/2) + c (5)
u2 = a*x^2 + b*x + c (6)
Se espandiamo otteniamo:
u0 = c (7)
u1 = a * x^2 / 4 + b * x / 2 + c (8)
u2 = a * x^2 + b * x + c (9)
Sostituiamo (7) in (9):
u2 = a * x^2 + b * x + u0
b * x = u2 - u0 - a * x^2
b = (u2 - u0 - a * x^2) / x (10)
Sostituiamo (7) e (10) in (8) e riordiniamo :
a = 2*u0 + 2*u2 - 4*u1 (11)
x^2
Cosí le relazioni (11), (10) e (7) ci danno i coefficienti per l'equazione u=a*x^2 + b*x + c.
Il prossimo passo consisterá nell'estrapolare qualcosa da utilizzare durante i disegno dei pixel. Deriviamo :
du/dx = 2*a*x + b (12)
e ancora:
ddu/dx = 2*a (13)
A questo punto il nostro loop interno assomiglierá a qualcosa di simile a questo :
PutPixel(x, y, texture[v][u])
u += du
du += ddu (ricordiamoci di fare altrettando con v, dv e ddv)
Inizializziamo questo loop settando u1, ie u(0)=c. Tuttavia occorre inizializzare du al valore assunto in 0.5:
du(0) = 2*a*x+b
= 2*a*0.5+b
= a+b
Dobbiamo stare attenti ad aggiornare u prima di du; la nostra routine ora assomiglia a qualcosa di simile a questo :
// Inizializziamo
u = c; (ricordiamoci di fare altrettando con v, dv e ddv).
du = a + b;
ddu = 2 * a;
// Disegnamo la scan-line
for (x=x1; x<=x2; x++)
{
PutPixel(x,y,texture[floor(v)][floor(u)])
u += du;
du += ddu; (ricordiamoci di fare altrettando con v, dv e ddv).
}
Intendo innanzitutto ringraziare Jon Vondrak per avermi suggerito questa idea. Credo che Jan avesse postato un articolo su questa tecnica in qualche newsgroup, e, quando ne venni a conoscenza, aveva giá cambiato il suo indirizzo di E-Mail. Cosí, invece di riportare qui l'articolo originale senza il suo consenso, ho deciso di scrivere io stesso un nuovo articolo, dandogli comunque credito di averne parlato per primo.
Nel precedente paragrafo sul Perfect Mapping, ho dimostrato come la seguente equazione fosse in grado di realizzare un texture mapping corretto prospetticamente :
DIST * (u1 + (x-x1) * du)
u(x) = -------------------------
z1 + (x-x1) * dz
Per v l'equazione é molto simile. (Per colore che hanno bisogno di un ripasso in matematica, u(x) indica "il valore di u in funzione di x". E' un modo molto semplice per dire all'utente che si sta cercando di trovare il valore di u al variare di x).
Possiamo a questo punto scrivere un'equazione piú generale :
u = A * x + B
C * x + D
Risistemiamo ora il tutto in questo modo, moltiplicando per C*x + D :
u * (C * x + D) = A * x + B
A * x + B - u * (C * x + D) = 0
cioé
f(u,x) = A * x + B - u * (C * x + D) = 0
A questo punto abbiamo sistemato l'equazione in modo che essa dipenda dai parametri u e x, e facendo in modo che f(u,x) sia sempre nulla per ottenere il Perfect Mapping [una siffatta equazione prende il nome di "conica" NDT].
Coloro che hanno familiaritá con l'algoritmo di Bresenham sanno che egli sviluppo algoritmi molto simili a quello per le linee, in grado di disegnare un qualsiasi tipo di conica. Un'iperbole, come le paraboli e le ellissi, rappresentano infatti diverse sezioni di un cono. Se provassimo ad ottimizzare l'algoritmo di Bresenham per le iperboli, otterremmo qualcosa di simile all'equazione precedente. Tuttavia, l'algoritmo suddivide la conica in 8 quadranti e per ciascuno disegna f(x,y). Cosí, ad ogni passaggio nel loop piú interno, otterremo la nuova coppia (x,y) di coordinate da disegnare. Sfortunatamente questo non ci aiuta molto. Qualche volta infatti é necessario saltare molti punti, specialmente quando il poligono da disegnare é molto lontano dal punto di vista.
[This section is still being written]
Ricordiamo che, dal paragrafo precedente sul Perfect Mapping, il valore di c é stato ottenuto usando il prodotto scalare tra il punto sullo schermo e il vettore C cosí definito :
c = <x-160,y-100,DIST> * <Cx, Cy, Cz>
= (x-160)*Cx + (y-100)*Cy + DIST*Cz
E' possibile osservare che Cy sará sempre nulle per tutte le superfici verticali, cosí, scandendo una linea verso il basso (ovvero incrementando j) il valore di c rimarrá costante e uguale a (x-160)*Cx +DIST*Cz; possiamo quindi calcolarne il valore precedentemente e utilizzare delle trasformazioni affini lungo un linea verticale, proprio come fá Wolf3D.
Allo stesso modo Cx=0 per tutte le superfici orizzontale e c=j*Cy +DIST*Cz per ogni pixel sulla linea orizzontale. Di nuovo possiamo usare le trasformazioni affini lungo tali linee in modo simile a Doom.
Il Constant-z mapping [Mapping con z costante] estende questa idea scegliendo una direzione di scansione tale che Dx*Cx + Dy*Cz = 0. Dx*Dy rappresenta la pendenza di questa direzione sullo schermo, in modo tale che se ci spostiamo lungo linee aventi questa pendenza, potremo di nuovo utilizzare trasformazioni lineari.
E' una teoria invitante ma... é troppo bello per essere vero ! La teoria del campionamento ci dice che, ogni volta che effettuiamo un campionamento come abbiamo descritto, commettiamo un errore di circa 0.5 pixels. Nel Perfect Mapping, tale errore risulta concentrato nel punto medio del pixel vicino, cosí il risultante valore di uv cade nello stesso pixel. In questo caso invece vengono effettuate due scansioni, raddoppiando questo errore.
Un altro modo di gurdare al problema é quello di considerare la distanza tra le due linee successive di scansioni. Quando disegnamo il punto di una linea, approssimiamo la sua posizione al pixel piú vicino. Cosí, la distanda tra due linee di scansioni non rimane costante lungo l'intera linea, tranne che per angoli di 0, 45 e 90 gradi. Il Constant-z Mapping é basato invece sul fatto che tale distanza rimanga costante, mentre, come abbiamo visto, in un display bitmapped, non é possibile.
Gli errori derivano in pratica dall'aliasing. In realtá essi si possono minimizzare incrementando la grandezza dello schermo e delle texture, ma anche allora ci saranno comunque aree di notevole contrasto. Oppure si puó utilizzare questo effetto utilizzando tecniche di anti-aliasing come i filtri, sebbene questo riduca notevolmente la velocitá di rendering. L'MMX potrebbe fornire strumenti in grado di far questo in modo semplice e veloce, ma, probabilmente, al momento della sua apparizione, gli standard di accelerazione tridimensionale saranno molto elevati.
Come se tutto ció non bastasse, il constant-z presenta numerosi altri problemi molto difficili da risolvere. Tanto per cominciare, non si puó prendere il primo pixel di una scanline e iniziare la scansione. Questo farebbe sí che in mezzo alla texture apparirebbero delle aree vuote, mentre altre sarebbero disegnate due volte. Per risolvere questo problema bisognerebbe spostare tutte le linee di scansione "avanti e indietro" per allinearle correttamente, calcolare poi da dove, lungo la linea di scansione, iniziare a renderizzare, cosí come le coordinate (u,v) di quel particolare punto.
Insomma : non usate il constant-z, non ne vale la pena.
Digressione sulle Textures
Ecco un trucco che vi aiuterá a spremere fino all'ultimo ciclo di clock il vostro processore : utilizzate texture grandi 256x256 pixel. TALK ABOUT CACHE ISSUES, VERTICAL SCANLINES ETC. Se le vostre texture sono piú piccole, allora unitele insieme per risparmiare spazio. Se sono piú larghe, provate a rigirarle su ogni lato. Se la loro larghezza e la loro altezza sono piú grandi di 256 pixel, allora suddividetele in tante piccole texture, chiamando la routine di texturizzazione per ogni pezzettino.
Il motivo per fare questo é perché, in questo modo, risulta estremamente semplice calcolare l'offset per ogni pixel sulla texture : mettete in BH il valore di v e in BL il valore u; il risultato sará che BX conterrá : BH*256+BL = v*245+u, cioé l'offset del pixe. Questo risulta particolarmente utile quando aggiornate entrambe u e v nell'affine mapping o nello scanline subdivision, visto che il vostro loop piú interno assomiglierá ad una cosa come questa :
mov al,Texture[ebx] ; Caricate il pixel
mov [edi],al ; Disegnatelo
add eax,edx ; aggiornate u
adc bl,cl
add ah,dh ; aggiornate v
adc bh,ch
add ebp,ecx ; aggiornate screen (y++, x+=delta)
adc edi,esi
Non sará la routine piú veloce possibile, ma funziona.
Se le vostre texture devono per forza essere di grandezze diverse, vi suggerisco di creare una look up table per le coordinate y di ogni texture. Molte persone pensano che questo appesantirá l'uso di memoria delle loro applicazioni, ma non é vero. Ad ogni riga di una texture dovrebbe essere associata una dword che contenga il suo offset, cosí l'incremento di memoria é di appena 4 pixel su 256. Le mie texture hanno una grandezza di almeno 128x128 in modo tale che l'incremento sia minimo. Se la memoria invece risulta essere un vero problema, allora tenete a mente che texture della stessa larghezza, condividono la stessa tabella di offset. Tuttavia le texture che hanno una propria look-up table sono in grado di memorizza l'indirizzo di ogni linea, in modo da incrementare notevolmente le prestazioni.
Calcolare la distanza tra due punti
Quando avete calcolato i valori di u e v, calcolare dove é localizzato il punto nello spazio 3D é semplice. Basta semplicemente aggiungere l'origine alla distanza nella direzione u, u*M, e alla distanza nella direzione lungo l'asse v, v*N, cioé :
Q = P + u*M + v*N
In questa equazione si é supposto che le variabili u e v varino tra 0 e 1, cosí prima di usarle, moltiplicate per 128 (o altro). Si puó ottimizzare la routine per ottenere qualcosa come dist=d/c nel loop interno. Questo risulta efficace per effetti come depth cueing e lo z-buffering. Se il vostro engine 3D non produce ridisegni, allora potete semplicemente mettere i valori di distanza nello z-buffer mentre renderizzate. Dopo aver fatto questo con gli oggetti statici, avrete create uno z-buffer da utilizzare per utilizzare l'HSR sui vostri oggetti dinamici.