MOTORE 3D IN C RAYCASTING

20/03/2014

Ecco una mia semplice implementazione C++ di un engine 3D basato sul metodo raycasting.

Il raycasting è una tecnica di rendering 3D particolarmente semplice e veloce in grado di creare viste tridimensionali a partire da mappe 2D.

Il motore grafico impone alcuni vincoli sul mondo da rappresentare ad esempio l'ortogonalità dei muri tra di loro e l'ortogonalità rispetto al pavimento, riuscendo quindi ad essere estremamente veloce: non è richiesta l'accelerazione GPU e nemmeno le librerie per il rendering 3D quali OpenGL o DirectX. Tutto il lavoro viene svolto in CPU disegnando la scena in un framebuffer in memoria.

Il raycasting è stato utilizzato per molto tempo come tecnica di rendering nei primi videogiochi 3D quali Wolfentein 3D, Rise Of The Triad, e con alcune modifiche minori anche DOOM, DOOM II e Duke Nukem 3D. Al tempo i computer non erano molto veloci (parliamo della fascia di processori che va dai primi Intel 286 fino ai 486-586) e quindi il raycasting ben si adattava alle limitate capacità di calcolo. Tuttavia ancora oggi troviamo esempi di motori 3D raycasting specialmente nelle architetture più limitate (ARM embedded, e anche calcolatrici).

Questo è il classico Wolfenstein 3D:

Come si vede chiaramente il rendering finale è abbastanza spartano se comparato con i moderni motori 3D. Come dicevo il raycasting lavora su una rappresentazione estremamente semplificata dell'ambiente 3D: una semplice collezione di cubi di pari dimensioni disposti all'interno di una griglia 2D. I cubi hanno stesse dimensioni e quindi stessa altezza, sono tutti ortogonali tra di loro e non possono sovrapporsi. Tutti questi vincoli permettono la rappresentazione del mondo 3D tramite una semplice griglia quadrata bidimensionale: ogni cella della griglia può essere o vuota (spazio vuoto) o piena (blocco solido). Ad ogni blocco solido può essere associato un colore o una texture (ad esempio associando ad ogni cella della griglia un numero intero).

Ecco come si presenta l'editor delle mappe in Wolfentein 3D (primo livello):

L'intero ambiente 3D è rappresentabile da una mappa bidimensionale con vista dall'alto. I vincoli rendono impossibli elementi come piani obliqui, saltare, guardare in alto, in basso o accovacciarsi. Motori grafici tipo Build (utilizzato in Duke Nukem 3D), sebbene basati esclusivamente sul raycasting, hanno introdotto tutti questi elementi pur essendo trattati nel codice come casi speciali (qui un'ottima review del motore Build).

Come funziona il raycasting?

Definiti la posizione e la direzione del punto di vista all'interno della griglia-mondo il raycasting procede in questo modo: per ogni riga di pixel verticale dello schermo viene "lanciato" un raggio (da qui il termine ray-casting) che parte dalla posizione corrente del giocatore e prosegue in avanti ad esso. Ad esempio, con una risoluzione di 1024 pixel in orizzontale verranno lanciati 1024 raggi in avanti ma ognuno ad una angolazione leggermente differente. Il raggio prosegue all'interno della griglia-mondo (in avanti rispetto al giocatore) fino a che non incontrerà una cella piena (un blocco-muro). A quel punto viene calcolata la lunghezza del raggio che corrisponde alla distanza effettiva del giocatore da quel muro. Il valore distanza viene utilizzato per calcolare quanto lunga dovrà essere disegnata la linea di pixel sullo schermo a quella data riga; più il raggio è lungo più corta sarà la linea verticale disegnata (muro lontano), più il raggio è corto più la linea sarà disegnata lunga (muro vicino). In figura si mostra come procede l'algoritmo: la vista è dall'alto, il punto verde è il giocatore, la riga nera è il piano di camera (lo schermo). Alcuni raggi (in giallo) campionano la mappa (notare le differenti lunghezze rilevate):

Ad ogni passo si prende la prossima riga verticale dello schermo e si lancia il raggio corrispondente con l'opportuna angolazione. L'algoritmo termina quando sono state disegnate tutte le linee sullo schermo: il rendering della scena è completato.

Qui sotto in figura viene mostrato come un singolo raggio si traduce in linea verticale sullo schermo. Notare che l'altezza della linea sul rendering finale (la linea gialla sullo schermo) dipende unicamente dalla lunghezza del raggio. Il colore della linea può essere dato dal "colore" del blocco (in questo caso o blu o rosso).

Notare che il rendering finale è sempre simmetrico rispetto all'asse verticale.

Per rilevare la collisione tra raggio e muro si può procedere in questo modo: facciamo partire il raggio dal punto in cui si trova il giocatore (punto verde in figura) e poi via via ne aumentiamo la lunghezza controllandone l'eventuale collisione con un muro. Aumentare la lunghezza del raggio di una costante fissa non è la soluzione corretta in quanto può accadere di "non vedere" il muro, come mostrato in figura:

Infittire i punti di check non risolve il problema perchè si può dimostrare che per qualsiasi costante di incremento esisterà sempre una certa probabilità di non rilevare la collisione (sebbene tale probabilità si possa ridurre a piacere). Un modo teorico per avere la certezza assoluta sarebbe quello di considerare infiniti punti di check (incremento infinitesimo) il che ovviamente non è implementabile.

Un metodo pratico ed anche estremamente veloce per risolvere il problema è quello di considerare solo i punti del raggio che cadono sulle righe della griglia. Sapendo che il raggio si muove sempre all'interno di una griglia di quadrati (pieni o vuoti) possiamo effettuare il test di collisione solo nei punti di intersezione tra il raggio e la griglia: questo metodo garantisce una accuratezza assoluta senza margine di errore. In figura l'algoritmo:

Per una mappa di NxN blocchi l'algoritmo richiede al più 2N controlli di collisione per singolo raggio il che lo rende abbastanza efficiente. Da notare che stanze molto grandi richiedono più tempo per essere spazzate dai raggi (più controlli di collisione).

Gli engine raycasting non ammettono "spazi aperti" ossia configurazioni di blocchi che non separano completamente lo spazio esterno dall'interno. Mappe aperte non lasciano terminare l'algoritmo (il raggio potenzialmente può non intersecare mai alcun blocco pieno) e quindi non sono ammesse. Una soluzione è quella di creare blocchi "invisibili" che chiudono la mappa come richiesto ma che poi non vengono disegnati su schermo.

Posizione, direzione del giocatore e piano di camera

Prima di poter creare l'algoritmo vero e proprio occorre definire esattamente cosa è il giocatore. Il giocatore è definito da tre parametri:

posizione all'interno della mappa (posX, posY)
vettore di direzione (dirX, dirY)
piano di camera (camX, camY)

Il primo è banalmente la posizione del giocatore nella mappa, sono sufficienti due valori posX, posY. Il secondo è il vettore direzione ed indica appunto la direzione nella quale "sta guardando" il giocatore, un vettore nel piano è indentificato univocamente da due valori dirX, dirY. L'ultimo è il piano di camera, ossia il piano ortogonale al vettore direzione che rappresenta lo schermo del giocatore. Anche in questo caso due valori camX, camY sono sufficienti: il termine "piano" è improprio in quanto lavoriamo già su un piano (la mappa 2D), sarebbe più opportuno definirlo "segmento di camera" perchè rappresenta lo schermo del giocatore come visto dall'alto.

In figura la rappresentazione dall'alto delle tre componenti del giocatore:

Il modulo del vettore segmento di camera rappresenta l'estensione orizzontale dello schermo (la lunghezza del segmento nero) rispetto all'ambiente circostante (la mappa 2D). Per convenzione posizioniamo sempre il giocatore al centro del segmento nero (centro dello schermo).

Il modulo del vettore direzione (la sua lunghezza) viene interpretato come distanza del giocatore dal piano di camera. In geometria proiettiva tale distanza viene chiamata focale. Alterando la focale si altera automaticamente il FOV o campo visivo, ossia la massima area visibile in un dato instante.

Grandi valori del modulo del vettore direzione (vettore rosso) generano una FOV stretta (zoom-in):

Piccoli valori del modulo del vettore direzione generano una FOV ampia (zoom-out):

Per un motore grafico una buon valore del modulo direzione è quello che genera una FOV di circa 66 gradi. Valori più grandi generano forti distorsioni all'immagine mentre valori troppo piccoli danno l'impressione di vedere tramite un forte zoom.

Generazione dei raggi

La generazione di un raggio uscente dal giocatore si traduce nella somma dei due vettori direzione e segmento di camera. Ad esempio, per uno schermo di 1024 pixel in orizzontale dobbiamo lanciare 1024 raggi aventi origine in posX, posY (posizione giocatore) ed intersecanti il segmento di camera ognuno in un punto differente. Il primo raggio (raggio 0) interseca il segmento di camera all'estrema sinistra: questo sarà il raggio lanciato per la riga 0 dello schermo (prima riga a sinistra, x=0). Il 1023 raggio (l'ultimo) interesecherà il segmento di camera all'estrema destra (ultima riga di pixel dello schermo, x=1023). Gli altri raggi saranno calcolati tramite uno scostamento progressivo e lineare lungo il segmento di camera.

In figura si mostrano i raggi relativi ad alcuni scostamenti di esempio (x=0, x=12, x=304 e x=1023):

In generale, per generare l'x-esimo raggio (vettore rayX, rayY) basta suddividere la lunghezza del segmento di camera in 1024 parti, calcolare in funzione di x il vettore scostamento dal centro del segmento e sommare tra loro vettore direzione e vettore scostamento.

Algoritmo di rendering

Definito il giocatore e i raggi possiamo finalmente chiarire l'algoritmo di rendering vero e proprio. Il rendering di un singolo frame prevede i seguenti passi:

passo 1) colorare lo schermo di nero (per eliminare il frame precedente)

passo 2) per ogni riga di pixel dello schermo:

calcolo dello scostamento sul segmento di camera
calcolo direzione del raggio rayX, rayY (somma vettore direzione e scostamento)
allungare il raggio avanzando di un blocco alla volta fino alla collisione con un muro
calcolo della lunghezza del raggio
tracciare una linea verticale alta h pixel. h è scelto in funzione della lunghezza del raggio (più il raggio è lungo, più h è basso e viceversa). Il colore della linea verticale può essere dato dal tipo di blocco incontrato (blocco blu, blocco rosso, blocco verde, etc... etc... possiamo definire quanti tipi di blocchi vogliamo)

Definizione della mappa

La mappa può essere definita da un semplice file di testo. Ad esempio, nel mio caso le prime due righe indicano rispettivamente la larghezza e la lunghezza (in blocchi) della mappa. In questo caso 64x64 blocchi. Le righe successive definiscono graficamente la mappa 2D. Ogni numero corrisponde ad un blocco solido di tipo (colore) diverso, blocco 1, 2, 3 e 4. Gli spazi bianchi definiscono i blocchi vuoti (spazi vuoti). world.txt

definiamo ad esempio il blocco tipo '1' verde, il blocco tipo '2' bianco, il blocco tipo '3' blu e il blocco tipo '4' rosso.

Movimento

Il giocatore può muoversi in due modi distinti:

avanti/indetro
girare in senso orario/antiorario

Per il movimento avanti e indietro è sufficiente aggiornare in maniera opportuna la posizione corrente posX, posY rispetto al vettore direzione. Definito un passo di movimento P il cambio di posizione si traduce nel sommare tra loro vettore posizione e vettore direzione moltiplicato per il passo di movimento. Quindi, nel caso di movimento in avanti:

posX = posX + dirX \* P;
posY = posY + dirY \* P;

Nel caso di movimento all'indietro:

posX = posX - dirX \* P;
posY = posY - dirY \* P;

Per girare in senso orario o antiorario occorre ruotare il vettore direzione dirX, dirY. La posizione ovviamente rimane invariata. Detto R il passo di rotazione (in radianti), la rotazione avviene moltiplicando il vettore direzione per la classica matrice di rotazione 2x2:

ossia:

dirX = dirX \* cos(R) - dirY \* sen(R)
dirY = dirX \* sen(R) + dirY \* cos(R)

cambiando segno ai coefficienti della matrice si inverte la rotazione (da oraria ad antioraria).

Codice sorgente - prima versione: raycasting senza texture mapping

Per disegnare a video ho utilizzato la libreria PixelToaster. Molto semplice da usare, basta aprire un display grafico di dimensione MxN pixel, in finestra o fullscreen, e settare individualmente i singoli pixel RGB. La libreria non fornisce alcuna primitiva grafica, ad esempio per disegnare rette, cerchi o rettangoli, se non quella per accendere o spengere singoli pixel sullo schermo (del colore RGB desiderato). Una comodo set di API aggiuntive permette di catturare gli eventi della tastiera (tasti premuti) e del mouse (coordinate x,y del cursore, stato dei bottoni).

In questa prima versione ho implementato l'engine raycasting nella sua versione più semplice, ossia senza texture mapping: ogni quadrato nella mappa (file world.txt) ha associato un numero intero e tale numero rappresenta un blocco solido di un dato colore.

source code (raycaster_ver01.cpp)

Per iniziare definiamo alcune costanti, risoluzione dello schermo, FOV, passo di movimento (P) e rotazione (R).

// risoluzione
#define SCREEN_W 640
#define SCREEN_H 480

// Field Of View
#define FOV 0.66

// Pi
#define PI 3.14159

// passo di movimento e rotazione
#define MOVSPEED 0.1
#define ROTSPEED 0.05

definiamo poi le strutture dati che ci serviranno, il framebuffer dove disegnare, i dati della mappa, stato del giocatore (telecamera) e il generico raggio:

// framebuffer
struct Frame
{
    uint32_t width;
    uint32_t height;
    TrueColorPixel *data;
};

// mappa
struct World
{
    uint32_t width;
    uint32_t height;
    uint8_t *data;
};

// stato della telecamera (posizione, direzione, piano di proiezione)
struct State
{
    double posx;
    double posy;
    double dirx;
    double diry;
    double camx;
    double camy;
};

// informazioni sul raggio
struct RayHit
{
    double distance;
    int mapX;
    int mapY;
    double rayDirX;
    double rayDirY;
    int side;
};

Il main() è abbastanza semplice, non facciamo altro che aprire una finestra delle dimensioni desiderate, inizializzare il framebuffer (delle stesse dimensioni della finestra), inzializzare la posizione del giocatore e caricare i dati della mappa dal file world.txt. Entriamo poi nel loop infinito while(1) nel quale facciamo ciclicamente il rendering della scena nel frambuffer (un semplice array di pixel RGB) e il disegno su video:

int main()
{
    // init schermo
    Display display(&quot;Raycaster&quot;, SCREEN_W, SCREEN_H, Output::Windowed);
    display.open();
    Listen l;
    display.listener(&amp;l);

    // init framebuffer
    Frame frame;
    frame.data = new TrueColorPixel[SCREEN_W * SCREEN_H];
    frame.width = SCREEN_W;
    frame.height = SCREEN_H;

    // init stato
    State state;
    state.posx = 3;
    state.posy = 3;
    state.dirx = -1;
    state.diry = 0;
    state.camx = 0;
    state.camy = FOV;

    // caricamento mappa
    World world;
    if (!LoadWorld(&quot;world.txt&quot;, &amp;world))
    {
        printf(&quot;\nError loading world file!&quot;);
        exit(0);
    }

    // init del listener
    l.state = &amp;state;
    l.world = &amp;world;
    l.moveSpeed = MOVSPEED;
    l.rotSpeed = ROTSPEED;

    while(1) // loop principale (rendering e disegno della scena)
    {
        RenderScene(state, world, frame);
        DrawScene(display, frame);
    }
}

La funzione RenderScene() prende lo stato attuale del giocatore (state), i dati della mappa (world) e crea il rendering della scena nel framebuffer (frame). Drawscene() prende semplicemente il frame e lo mostra a video.

RenderScene() è il cuore dell'algoritmo. Per prima cosa lo schermo viene colorato completamente in nero al fine di cancellare il frame precedente:

for(i = 0; i < (frame.width * frame.height); i++)
{
    frame.data[i].r = 0; // R
    frame.data[i].g = 0; // G
    frame.data[i].b = 0; // B
}

Fatto ciò inizia il ciclo for principale che per ogni riga verticale dello schermo lancia un raggio uscente dal giocatore:

for (uint32_t column = 0; column < frame.width; column++) // per ogni riga

calcoliamo la posizione e direzione del raggio in funzione di column:

// calcola la posizione e la direzione del raggio
double cameraX = 2 * column / double(frame.width) - 1;
double rayPosX = state.posx;
double rayPosY = state.posy;
double rayDirX = state.dirx + state.camx * cameraX;
double rayDirY = state.diry + state.camy * cameraX;

Lanciamo ora il raggio dopo un breve setup dei valori iniziali. Il ciclo while() incrementa la lunghezza del raggio fino alla collisione con un muro:

// il blocco attuale dove siamo
int mapX = int(rayPosX);
int mapY = int(rayPosY);

// lunghezza del raggio dalla posizione attuale al blocco successivo
double sideDistX;
double sideDistY;

// lunghezza del raggio da un blocco ad un altro
double deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
double deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
double perpWallDist;

// direzione nella quale andare (+1 o -1), sia per X che per Y
int stepX;
int stepY;
int side; // faccia del cubo incontrata (faccia Nord-Sud o faccia Ovest-Est)

if (rayDirX < 0)
{
    stepX = -1;
    sideDistX = (rayPosX - mapX) * deltaDistX;
}
else
{
    stepX = 1;
    sideDistX = (mapX + 1.0 - rayPosX) * deltaDistX;
}

if (rayDirY < 0)
{
    stepY = -1;
    sideDistY = (rayPosY - mapY) * deltaDistY;
}
else
{
    stepY = 1;
    sideDistY = (mapY + 1.0 - rayPosY) * deltaDistY;
}

// lanciamo il raggio
while ((world.data[mapX + mapY * world.width] == 0)) // finche' non incontriamo un muro...
{
    // andiamo al prossimo blocco nella mappa
    if (sideDistX < sideDistY)
    {
        sideDistX += deltaDistX;
        mapX += stepX;
        side = 0;
    }
    else
    {
        sideDistY += deltaDistY;
        mapY += stepY;
        side = 1;
    }
}

mapX e mapY sono le coordinate intere del blocco dove si trova la punta del raggio ad ogni iterazione. Finchè la mappa restituisce zero (nella nostra convenzione 0 rappresenta un blocco vuoto) incrementiamo la lunghezza del raggio. Una volta incontrato un blocco solido usciamo dal ciclo while() e calcoliamo la lunghezza esatta del raggio:

// calcolo lunghezza del raggio
if(side == 0)
{
    perpWallDist = fabs((mapX - rayPosX + (1 - stepX) / 2) / rayDirX);
}
else
{
    perpWallDist = fabs((mapY - rayPosY + (1 - stepY) / 2) / rayDirY);
}

Fatto ciò chiamiamo DrawColumn() che si occuperà di disegnare una linea larga 1 pixel e alta h. L'altezza h della colonna è funzione della lunghezza del raggio appena calcolato: più il raggio era lungo più la linea disegnata sarà corta, più il raggio era corto più la linea disegnata sarà alta. Il colore della linea di pixel è data dal tipo di blocco che il raggio ha incontrato. Tutte queste informazioni sono caricate nella struct RayHit e passate alla funzione DrawColumn() che la disegnerà nel framebuffer. Il ciclo for() riparte quindi con una nuova iterazione per il disegno della prossima linea di pixel e cosi' via fino al margine destro dello schermo. Quando tutte le righe verticali dello schermo sono state disegnate il frame è finalmente completo e può essere passato alla funzione DrawScene() che lo mostrerà sul display (finestra o fullscreen che sia). La funzione DrawColumn() disegna una linea sullo schermo. Ma come viene disegnata questa colonna? E come viene calcolata esattamente l'altezza? Vediamo come.

Per prima cosa viene recuperato il tipo di blocco solido incontrato dal raggio:

// tipo di blocco rilevato
uint8_t type = world.data[what.mapX + what.mapY * world.width];

poi viene scelto un colore RGB in funzione del tipo blocco:

// seleziona colore in base al tipo di blocco
uint8_t r, g, b;
switch (type)
{
case 1:
{
    r = 0;
    g = 255;
    b = 0;
    break;
}
case 2:
{
    r = 155;
    g = 155;
    b = 155;
    break;
}
case 3:
{
    r = 0;
    g = 0;
    b = 255;
    break;
}
case 4:
{
    r = 255;
    g = 0;
    b = 0;
    break;
}
}

Calcoliamo ora l'altezza h della linea di pixel da disegnare, in funzione della lunghezza del raggio.

// calcola altezza colonna

uint32_t colh = abs(int(frame.height / what.distance));

uint32_t cropup = 0;
uint32_t cropdown = 0;
uint32_t index = 0;

if (colh > frame.height) // se e' piu' alta dello schermo, taglia
{
    index = column;
    cropup = (colh - frame.height) / 2;
    cropdown = cropup + 1;
}
else
{
    index = column + ((frame.height - colh) / 2) * frame.width;
    cropup = 0;
    cropdown = 0;
}

e finalmente viene disegnata la colonna di pixel:

// disegna colonna
for (uint32_t c = cropup; c < (colh - cropdown); c++)
{
    // disegna il pixel del colore selezionato
    frame.data[index].r = r;
    frame.data[index].g = g;
    frame.data[index].b = b;
    index += frame.width;
}

Risultato finale

La nostra prima implementazione del raycaster. Qui trovate il codice sorgente completo.

Aggiungere terreno e cielo

Possiamo aggiungere una prima forma di terreno e soffitto al motore grafico. Esattamente come in Wolfenstein 3D, possiamo farlo semplicemente coorando le zone nere in alto (sopra la metà schermo) di blu e le zone nere in basso (sotto la metà schermo) di marrone. E' molto più oneroso riempire le poche zone di schermo nere rimaste a rendering ultimato che non colorare a priori tutto lo schermo metà blu e metà marrone e poi applicare sopra il rendering stesso.

Quindi, prima del rendering della scena disegnamo lo schermo metà blu e metà marrone. Lo facciamo all'inizio della RenderScene().

Al posto del ciclo for che colora lo schermo completamente di nero:

for(i = 0; i < (frame.width * frame.height); i++)
{
    frame.data[i].r = 0;
    frame.data[i].g = 0;
    frame.data[i].b = 0;
}

mettiamo un ciclo for modificato che colora la metà alta dello schermo di blu (cielo) e la metà bassa di marrone (terreno):

// flat sky
for(i = 0; i < (frame.width * frame.height / 2); i++)
{
    frame.data[i].r = 135;
    frame.data[i].g = 206;
    frame.data[i].b = 250;
}

// floor
for(i = (frame.width * frame.height / 2); i < (frame.width * frame.height); i++)
{
    frame.data[i].r = 102;
    frame.data[i].g = 51;
    frame.data[i].b = 0;
}

Questo nuovo ciclo for non fa altro che colorare lo schermo in questo modo:

A rendering ultimato il risultato finale è questo:

Questo il sorgente della versione con soffitto e terreno.

Nel prossimo articolo vedremo come implementare il texture mapping sia per i muri verticali che per il pavimento e soffitto (in gergo floor-casting e ceiling-casting). In più vedremo come aggiungere un primo abbozzo di skydome (cielo aperto).

Torna alla home