Motore 3D in C++ – Raycasting parte II – texture mapping

Nella prima parte abbiamo visto come implementare un motore 3D basato su raycasting. Il motore realizzato è abbastanza spartano e prevede colori piatti sia per i muri che per soffitto e pavimento. Aggiungiamo ora le texture.

Prendiamo una immagine quadrata 256×256 pixel, ad esempio questa:

stone

Questa sarà la nostra texture che andremo ad applicare ai muri nel rendering finale della scena 3D. Siccome abbiamo stabilito che l’ambiente 3D è composto unicamente da semplici cubi una texture quadrata è l’ideale per texturizzare tutte le facce.

Come funziona il texture mapping?

L’idea base è quella di considerare questa volta non soltanto la lunghezza del raggio ma calcolare anche lo scostamento rispetto alla faccia del blocco. In figura si mostra il raggio uscente (in giallo), la collisione con il blocco e lo scostamento (in nero) rispetto alla faccia del blocco stesso:
raycasting - texture mapping

Lo scostamento ci serve per recuperare la “striscia” verticale di texture (1 x 256 pixel) da riscalare opportunamente (in funzione della lunghezza del raggio, come visto nella prima parte) e applicare al posto della semplice riga verticale monocolore. Ripetendo il processo per ogni singolo raggio otteniamo il texture mapping completo della scena.

Caricamento della texture da file esterno

Per prima cosa occorre caricare la texture da una immagine esterna. Nel mio caso ho utilizzato il formato non compresso TGA perchè estremamente semplice da leggere (una collezione lineare di triple RGB).

Aggiungiamo al codice dei define per le dimensioni della texture:

#define TEXT_W 256
#define TEXT_H 256

definiamo la struttura dati Texture: altezza, larghezza e puntatore al vettore di pixel RGB.

struct Texture
{
	uint32_t width;
	uint32_t height;
	TrueColorPixel *data;
};

Modifichiamo la struttura dati RayHit aggiungendo lo scostamento di cui parlavamo prima: blockOffset e wallX. Il primo è lo scostamento in coordinate texture (i pixel di scostamento rispetto alla dimensione della texture), il secondo è lo scostamento in coordinate mappa 2D (un valore floating point compreso tra 0 ed 1).

struct RayHit
{
	double distance;
	int mapX;
	int mapY;
	double wallX;
	double rayDirX;
	double rayDirY;
	int side;
	uint32_t blockOffset;
};

Definiamo la variabile globale stone

Texture stone;

Nel main() carichiamo la texture. Si tratta di aprire e leggere il file “stone.tga” e allocare un vettore di 65536 byte (246×256) in stone.data. Per i dettagli della funzione LoadTexture basta dare un’occhiata al sorgente.

	if (!LoadTexture("stone.tga", &stone))
	{
		printf("\nError loading texture file!");
		exit(0);
	}

A questo punto, nella funzione RenderScence, subito dopo aver calcolato la lunghezza del raggio, calcoliamo lo scostamento (sia wallX che blockOffset):

		// calcola wallX ovvero l'offset x del blocco colpito dal raggio
		double wallX;
		if (side == 1)
		{
			wallX = rayPosX + ((mapY - rayPosY + (1 - stepY) / 2) / rayDirY) * rayDirX;
		}
		else
		{
			wallX = rayPosY + ((mapX - rayPosX + (1 - stepX) / 2) / rayDirX) * rayDirY;
		}
		wallX -= floor((wallX));

		// riga della texture (in coordinate texture) 
		int texX = int(wallX * double(TEXT_W));
		
		// inverti in base alla posizione del raggio
		if (side == 0 && rayDirX > 0)
		{
			texX = TEXT_W - texX - 1;
		}
		if (side == 1 && rayDirY < 0)
		{
			texX = TEXT_W - texX - 1;
		}

		// carica RayHit con le informazioni per disegnare la colonna
		RayHit what;
		what.distance = perpWallDist;
		what.blockOffset = texX;
		what.mapX = mapX;
		what.mapY = mapY;
		what.side = side;
		what.rayDirX = rayDirX;
		what.rayDirY = rayDirY;
		what.wallX = wallX;

Nella DrawColumn anzichè disegnare una colonna di pixel piatti, disegnamo una striscia verticale di texture opportunamente riscalata:

	// disegna colonna
	for (uint32_t c = cropup; c < (colh - cropdown); c++)
	{
		// calcola il pixel da prelevare nella texture
		double d = (double)c / (double)colh;
		int texY = ((int)(d * TEXT_H)) % TEXT_H;
		TrueColorPixel t = texture.data[what.blockOffset + texY * TEXT_W];

		// disegna il pixel della texture
		frame.data[index].r = t.r;
		frame.data[index].g = t.g;
		frame.data[index].b = t.b;

		index += frame.width;
	}

Il risultato finale è questo:
raycasting - texture mapping

A questo punto diventa abbastanza banale creare più di una immagine texture, caricarle tutte in memoria e texturizzare i blocchi utilizzando la texture oppurtuna (in funzione ad esempio numero intero associato al blocco, nel file world.txt).

Questo il codice sorgente completo con texture mapping

Il risultato finale:

Pavimento e soffitto

Il pavimento e soffitto possono essere rendirizzati con una tecnica analoga. Innanzitutto, siccome abbiamo visto che la geometria del rendering finale è simmetrica rispetto all’asse verticale dello schermo allora lo sarà anche il pavimento rispetto al soffitto. Una volta che sappiamo texturizzare il pavimento basta “ribaltarlo” in verticale per ottenere il soffitto (magari cambiando immagine texture).

Procediamo con il redenring del pavimento: per ogni colonna di pixel dello schermo e immediatamente dopo aver disegnato la riga muro, occorre procedere in questo modo:

Si considera il segmento di pixel verticale rimanente per raggiungere il fondo dello schermo. Si calcolano le coordinate mondo di ogni pixel di questo segmento. Ad ogni coordinata mondo corrisponde un preciso punto nella texture 256×256 di pavimento. Si disegna quel pixel con il colore della texture in quel punto. Ripetendo per tutte le colonne otteniamo la texture completa del pavimento.

Per disegnare il soffitto non occorre ricalcolare altri punti. Sapendo che è simmetrico rispetto al pavimento è sufficiente cambiare texture ed usare gli stessi punti trovati per il pavimento. Ovviamente avendo cura di ribaltare il plot sull’asse verticale.

	// posizione X,Y del texel della texture proprio sotto il muro
	double floorXWall, floorYWall;

	// 4 possibili direzioni del muro
	if (what.side == 0 && what.rayDirX > 0)
	{
		floorXWall = what.mapX;
		floorYWall = what.mapY + what.wallX;
	}
	else if (what.side == 0 && what.rayDirX < 0)
	{
		floorXWall = what.mapX + 1.0;
		floorYWall = what.mapY + what.wallX;
	}
	else if (what.side == 1 && what.rayDirY > 0)
	{
		floorXWall = what.mapX + what.wallX;
		floorYWall = what.mapY;
	}
	else
	{
		floorXWall = what.mapX + what.wallX;
		floorYWall = what.mapY + 1.0;
	}

	double distWall, distPlayer, currentDist;
	distWall = what.distance;
	distPlayer = 0.0;

	// disegna pavimento e soffitto
	uint32_t c = (colh + frame.height) / 2;
	
	while (c < frame.height) // per ogni pixel al di sotto della colonna muro
	{
		// calcola la distanza
		currentDist = frame.height / (2.0 * c - frame.height);
		double weight = (currentDist - distPlayer) / (distWall - distPlayer);

		// calcola il punto X,Y nel blocco corrente
		double currentFloorX = weight * floorXWall + (1.0 - weight) * state.posx;
		double currentFloorY = weight * floorYWall + (1.0 - weight) * state.posy;
		
		// calcola il punto X,Y nella texture del pavimento
		int floorTexX, floorTexY;
		floorTexX = int(currentFloorX * 256) % 256;
		floorTexY = int(currentFloorY * 256) % 256;
		
		if(CAST_FLOOR)
		{
			// pixel di pavimento (relativo alla colonna column)
			TrueColorPixel f = tiles.data[floorTexX + floorTexY * 256];
			frame.data[index].r = f.r;
			frame.data[index].g = f.g;
			frame.data[index].b = f.b;
		}

		if(CAST_CEILING)
		{
			// pixel di soffitto (relativo alla colonna column)
			TrueColorPixel g = ceiling.data[floorTexX + floorTexY * 256];
			frame.data[column + (frame.height - c - 1) * frame.width].r = g.r;
			frame.data[column + (frame.height - c - 1) * frame.width].g = g.g;
			frame.data[column + (frame.height - c - 1) * frame.width].b = g.b;
		}
		
		index += frame.width;
		c++;
	}

codice sorgente con texture mapping muri, terreno e soffitto.

Qui potete trovare il sorgente completo (progetto eclipse, immagini texture)

Motore 3D in C++ – Raycasting parte I

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:

Wolfenstein_3D_Screenshot

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):

nmap

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):

raycasting - algoritmo

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).

rayhit1

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:

raycasting - miss

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:

raycast - nomiss

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:

player

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):

lowFOV

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

highFOV

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):

castrays

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.

somma_vettori

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 64×64 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

asciimap

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 il passo di rotazione (in radianti), la rotazione avviene moltiplicando il vettore direzione per  la classica matrice di rotazione 2×2:

rot

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 linea 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:

raycast - flat landscape

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).