RAYTRACING E METODI DI MONTE CARLO

Aggiornato il 11/08/2004

INTRODUZIONE

Il raytracing unito ai metodi di Monte Carlo, ha raggiunto un elevato grado realismo; soprattutto grazie all'utilizzo di modelli fisici sempre più accurati e sempre meno basati su metodi empirici. Questo lavoro nel suo piccolo seppur solo di implementazione (infatti è finalizzato alla creazione di software), ha lo scopo di esplorare le estensioni principali del raytracing per la sintesi di immagini sintetiche realistiche. Per questione di  sintesi verranno presentati  le estensioni storiche del raytracing, accenando alle altre.

Il raytracing puro è una tecnica per la generazione di immagini fotorealistiche al calcolatore partendo da una descrizione formale di una scena tridimensionale; ed è stato introdotto nel 1980 da Turner Whitted. Ancora oggi riveste un ruolo importante grazie ai vantaggi rispetto alle metodologie a scansione lineare:

1) La geometria può essere procedurale senza il bisogno di triangolarizzazioni;
2) Le ombre posso essere calcolate in modo preciso senza un elevato consumo di memoria e di tempo di cpu, rispetto a tecniche classiche come: pojection plane shadow, shadow map, e alle stencil volume shadow;
3) L'elevata precisione, determinata a pixel;
4) Riflessioni e rifrazioni perfette;

L'idea alla base del raytracing è che il percorso della luce può essere seguito in senso contrario; dall'osservatore alla sorgente luminosa. La correttezza di tale idea è dovuta a due proprietà della luce:
1) La luce si muove in modo rettilineo nello spazio vuoto;
2) La simmetria o reciprocità; se il senso di percorrenza della luce è invertito (cioè si inverte la direzione di uscita con quella di entrata), il valore del BRDF non cambia.

Infatti nel raytracing, per ogni pixel dello schermo o dell'immagine, si "lanciano" dei raggi, e si verifica l'eventuale intersezione più vicina con gli oggetti presenti nella scena. Ogni raggio ha la seguente forma:

dove:
O è la posizione di lancio del raggio ( il raggio si dice primario se la posizione di lancio coincede con quella dell'osservatore);
D è la direzione del raggio;

Una volta trovata un'intersezione con un oggetto ad un certo punto x con normale N, si calcola l'illuminazione in quel punto usando un BRDF f basandosi sulle proprietà del materiale dell'oggetto intersecato. Per esempio ecco una formula generale per il calcolo dell'intensità luminosa diretta:

dove:

w' è il vettore normalizzato che congiunge il punto x con la posizione della luce;
w è il vettore normalizzato ottenuto dalla riflessione w' rispetto ad n;

Può accadere che degli oggetti (occlusori) si frappongano tra x e i raggi luminosi della sorgente creando così ombra. I punti d'ombra sono privi di illuminazione; quindi il calcolo dell'intensità luminosa va effettuata solo nei punti liberi dagli occlusori. Tale verifica si effettua facendo un test di intersezione con un raggio dove O corrisponde al punto x, e con D corrispondente al vettore w'. Una nota particolare va in caso di sorgenti luminose continue (una linea, un rettangolo, una sfera), in quel caso la sorgente va campionata in tanti punti  di emissione secondo la distribuzione di emissione per raggiungere migliori risultati.
Nel caso in cui l'oggetto con intersezione x, abbia proprietà speculari viene calcolato il contributo speculare. Ricorsivamente si ripete la procedura utilizzando come nuova O il punto e x e come nuova D il raggio D riflesso o rifratto (a seconda del tipo di superficie speculare).
Una delle prime estensioni effettuate al raytracing fu il raytracing distribuito introdotto da Robert L. Cook, Thomas Porter e Loren Carpenter nel 1984. Il raytracing distribuito consiste nella sovracampionatura dei pixel, così facendo si possono ottenere molti effetti tra i quali: anti-aliasing, profondità di campo, riflessioni fuzzy (sovracampionatura delle riflessioni), sfuocatura di movimento (integrazione del tempo).

Ecco un frammento di pseudo-codice per capire la procedura, la funzione Render illumina un determinato pixel ( i , j ) dell'immagine:

Function Render ( raggio )
Begin
    esiste:= TrovaInteresezione ( raggio );
    colore:=  Nero;
    if ( esiste ) then
          Begin
             colore:= CalcolaIntensitaLuminosa ( x, n );
             if ( speculare ) then
                Begin
                   colore:= colore + Render ( raggio riflesso / raggio rifratto );
                end
          end
    ret colore;
end

Il Path Tracing, introdotto da James T. Kaijya nel 1984, è un estensione del raytracing che permette di ottenere effetti di illuminazione globale come color bleeding (riflessi diffusi) o caustiche (anche se queste necessitano un gran numero di campioni per essere rappresentate). L'idea alla base è molto semplice, ogni qual volta che si interseca una superficie lambertiana o diffusa in un punto x, si lancia un nuovo raggio, che parte da x, in una direzione casuale dell'emisfero determinato dalla normale n in x. Ad ogni nuova intersezione si calcola l'illuminazione locale e la si somma a quella del pixel corrente. Il procedimento termina perchè in genere si forza ad un numero determinato di rimbalzi, o si effettua la roulette russa.
La procedura crea praticamente un percorso, e maggiore è il numero di percorsi fatti per pixel maggiormente il valore in quel pixel convergerà al calcolo dell'integrale della Rendering Equation di Kaijya (il rumore è molto elevato utilizzando meno di 100 percorsi per pixel). Il punto di partenza dei percorsi non è sempre lo stesso ma varia, infatti si sceglie in genere una posizione casuale all'interno dell'intorno della posizione standard di partenza del raytracing.
Da notare che nel Path Tracing non si campiona ogni direzione dell’emisfero di x ma solo una direzione casuale, perché altrimenti la complessità sarebbe esponenziale, e il calcolo dell'illuminazione di una semplice scena quale una Cornell Box sarebbe proibitivo.

3. - IL PHOTON MAPPING

Il Photon Mapping, introdotto da Henrik Wann Jensen tra il 1995 e il 1996, è un algoritmo che estende il raytracing e l'idea del Pathtracing di Kaijya, in particolar modo può essere visto come un Bidirectional Pathtracing con cache. Infatti anche in questo caso, invece di effettuare solo il percorso inverso della luce cioè dall'oggetto alla sorgente luminosa, si traccia anche il percorso naturale della luce; ossia dalla sorgente luminosa agli oggetti.
I percorsi "vengono salvati" (in realtà non si conserva informazione del percorso ma dei punti del percorso) in una struttura chiamata mappa dei fotoni per evitare ogni volta il lancio dei fotoni. La mappa dei fotoni è un KD-tree (fig.3.1), e la scelta per tale struttura è dovuto al fatto che è molto efficiente per la localizzazione di n punti vicini rispetto ad un punto di riferimento. Ogni qual volta che si salva un fotone nella mappa dei fotoni si salva la sua posizione, direzione di arrivo e la potenza luminosa che trasporta.


L'algoritmo di Jensen è un algoritmo a due passate. La prima passata è il lancio dei fotoni (che rappresentano il flusso di energia) dalle sorgenti presenti nella scena; per ogni sorgente vengono lanciati un determinato numero di fotoni che trasportano una quantità di potenza, pari alla potenza della sorgente luminosa divisa per il numero dei fotoni emessi. I fotoni possono essere lanciati da qualsiasi  tipo di sorgente luminosa (fig.3.2), infatti basta conoscere la funzione di distribuzione dei fotoni di un determinato tipo di sorgente.


Ogni fotone lanciato può essere perso (cioè non collide con nessun oggetto della scena e scappa) o può collidere; in questo caso vi sono varie possibilità (fig.3.3):
1) il fotone viene assorbito e viene salvato nella mappa dei fotoni;
2) il fotone viene riflesso diffusamente e la sua collsione attuale viene salvata nella mappa dei fotoni;
3) il fotone viene riflesso in modo speculare.
La natura reale dei fotoni consente loro infiniti rimbalzi a seguito di una collisione, però nel nostro modello ciò sarebbe impraticabile, infatti la passata di lancio dei fotoni non potrebbe terminare. Quindi ad ogni rimbalzo si decide con il meccanismo della roulette russa che farne del fotone (fig.3.4): assorbirlo, rifletterlo in modo diffuso o speculare. Se il fotone viene riflesso si scala la sua potenza per la capacità di riflessione diffusa o speculare del materiale dell'oggetto con cui è avvenuta la collisione.

fig.3.3- un esempio di percorso dei fotoni.

fig.3.4- la roulette russa semplificata.

Nella seconda passata viene calcolata l'illuminazione per un determinato punto; riflessioni e rifrazioni vengono gestite come in un normale Raytracer, mentre il calcolo dell'intensità luminosa diretta, indiretta e delle caustiche vengono calcolate tramite la stima di densità (una tecnica nata in ambito statistico).
La stima di densità può essere vista come una descritizzazione dell'equazione dell'intensità riflessa (il cui dominio di integrazione è una semisfera, vedi fig.3.5)::


La stima di densità ha la seguente forma:
dove:
  è il flusso di energia da la fotone p.
r         è il raggio della sfera in cui sono contenuti gli n fotoni della stima (fig.3.6).

NOTA: Nella stima di densità la proiezione dell’area dell’angolo solido dell'equazione dell’intensità riflessa, viene sostituita dall’area della del cerchio con il raggio di ricerca degli n fotoni vicini.

La stima di densità è valida in quanto tra radiazione e flusso sussiste la seguente relazione:
Sostituendo tale relazione all'equazione dell’intensità riflessa si ottiene:

Per migliorare la qualità dei risultati, si può calcolare il termine dell'illuminazione indiretta diffusa con il Final Gathering. Il Final Gathering consiste nel calcolare l'intensità luminosa (tramite stima di densità) di tutti i punti visibili da punto x preso in esame (cioè campionare attorno al suo emisfero) e quindi farne la media. E' una procedura molto costosa, che può essere velocizzata utilizzando delle cache (fig.7). L'uso di cache è giustificato dal fatto che la luce indiretta diffusa al contrario di quella speculare, cambia lentamente nello spazio, e quindi si possono riutilizzare i valori vicini tramite interpolazione. Questa idea sviluppata da Ward, è alla base del famoso software Radiance.


Un altro metodo per migliorare i risultati è quello di utilizzare un Raytracer per il calcolo dell'illuminazione diretta, quindi la stima di densità viene utilizzata in "modo puro" solo per il calcolo delle caustiche che non necessitano particolari condizioni. Per la realizzazione della divisione del calcolo dell'illuminazione nelle tre componenti viste ora (diretta, indiretta, caustiche) vi è la necessità di avere tre Photon Map, una per i fotoni diretti, uno per quelli indiretti, e uno per le caustiche. Questa strategia risulta ottimale in quanto, non vi sono interferenze di altre tipi di illuminazione durante la stima di densità; diminuendo significatamente il rumore.

4. - LA STRUTTURA DEL RAYTRACER

Il raytracer è stato sviluppato con il paradigma ad oggetti ed implementato in C++ utilizzando le OpenGL come libreria di previsualizzazione, e Diretc3DX come librerie di supporto per i calcoli vettoriali e matriciali. Il raytracer lavora fondamentalmente con i seguenti oggetti: i materiali, le luci, gli oggetti tridimensionali; il tutto contenuto e gestito nelle varie classi Scena che si differenziano per funzioni peculiari particolari. Nella scrittura del codice si è sfruttato molto l'ereditarietà, e i meccanismi di casting grazie ai quali l’aggiunta di nuovi tipi di luci, materiali e oggetti risulta molto facile.

4.1 GLI OGGETTI 3D
Gli oggetti tridimensionali del raytracer non sono altro che descrizioni formali, e fanno tutti capo ad una classe base Oggetto, che definisce i metodi comuni che verranno utilizzati dalle varie classi Scena. Questi metodi sono:

1) CheckRay() per calcolare l'intersezione dell'oggetto con un raggio;
2) C_Normale() per calcolare la normale in un punto dell'oggetto;
3) CaricaOggetto() per caricare da file la descrizione dell'oggetto;
4) ChiSono() per sapere con quale specializzazione di Oggetto si stà lavorando;
5) ApplicaTrasformazioni() per effettuare traslazioni e rotazioni dell'oggetto.

Oltre a metodi in Oggetto vengono definite delle variabili comuni quali il nome dell'oggetto, il nome del materiale a cui va associato, il tipo di texture mapping, ed infine la posizione rispetto all'origine e la rotazione rispetto al centro dell'oggetto.
La maggior parte degli oggetti specialistici hanno una descrizione formale molto semplice: nel caso del Cubo (che è in realtà un parallelepipedo) si tiene conto solo delle estensioni nelle tre dimensioni, per la sfera solo del raggio, mentre per il piano non si ha bisogno di registrare niente dato che la posizione e la normale (rappresentata dal vettore di rotazione) sono già presenti in Oggetto.
L'oggetto Mesh invece è una mesh triangolare rappresentata a lista di vertici. Per velocizzare il test di intersezione mesh-raggio (infatti l'algoritmo di forza bruta effettua il test triangolo-raggio per ogni triangolo della mesh, ed è molto oneroso dal punto di vista computazionale) viene utilizzata una suddivisione spaziale. Nello specifico si utilizza un octree e quindi viene effettuato il test triangolo-raggio  solo per i triangoli contenuti nelle regioni di spazio candidate, selezionate dal test octree-raggio (un test ricorsivo cubo-raggio), l'utilizzo dell'octree ha velocizzato di circa otto volte il test mesh-raggio; anche se l'utilizzo dei BSP sarebbe ottimale.


4.2 LE LUCI
Gli oggetti luce sono descrizioni formali di fonti luminose, grazie alle quali ed a un modello di shading si possono illuminare gli oggetti presenti nella scena. Sono strutturati come gli oggetti 3D, in poche parole c'è una classe astratta Luce che definisce i metodi e le caratteristiche comuni.
Le caratteristiche comuni sono proprietà fisiche quali: il colore diffuso, il colore speculare, la potenza in Watt della luce, il nome, il tipo di luce specializzante, se è abilitata a calcolare ombre. Le caratteristiche specializzanti sono caratteristiche di natura geometrica che definiscono il tipo di luce.
I metodi delle classi figlie sono rivolti alla creazione delle ombre, infatti ogni tipo di luce avendo caratteristiche geometriche differenti hanno bisogno di metodi specifici per tale calcolo.
I metodi comuni sono:

1) BRDF_Blinn() per calcolare l'intensità luminosa con il BRDF di Blinn.
2) CaricaLuce() per caricare da file la descrizione della luce;
3) ChiSono() per sapere con quale specializzazione di Luce si stà lavorando;
4) SparaFotone() per sparare un insieme di fotoni nella scena;
5) FotonePath() per tracciare il percorso di un fotone.

Le tipologie di luci presenti sono abbastanza standard (point light, directional light, spot light, le hemisphere light presenti nelle pipeline di lighting di DirectX e OpenGL) e implementano il modello della luce di Jim Blinn (che si differenzia da quello di Phong per un migliore calcolo del fattore speculare).

Gli unici tipi di luce un po' ricercati sono la LLineare (il limite a infinito del numero di point light lungo una linea) e la LArea (il limite a infinito del numero di point light distribuite uniformemente su una superifice); queste due tipologie di luce sono molto pesanti dal punto di vista computazionale, ma rappresentano meglio le fonti di luci presenti in natura (infatti una LLineare può essere vista come un neon e una LArea come una finestra fig.4.1). Per effettuare il calcolo del modello di riflessione di Blinn e del calcolo delle ombre per la LLineare e per la LArea è stato deciso di campionarle con point light. Si potrebbe migliorare il calcolo del modello di riflessione, che è un integrale curvilineo nel caso di LLineare, e superificiale nel caso di LArea) svolgendolo in modo analitico, anzichè in modo numerico; ma lascio ciò a future implementazioni.

fig.4.1.a- Una luce LPunto.

fig.4.1.b- Una luce LArea.

I fotoni generati tramite la funzione SparaFotone vengono salvati in un'istanza della classe MappaFotoni, che è un KD-tree bilanciato. MappaFotoni svolge le normali operazioni di un KD-tree cioè bilanciamento di un insieme di punti, inserimento di un punto, e ricerca degli n-vicini. In più calcola l'illuminazione in un punto con il metodo della stima di densità.

4.3 I MATERIALI
I materiali nei programmi professionali di rendering quali fra tutti RenderMan, MentalRay, BMRT e LightFlow, vengono rappresentati con veri e propri linguaggi ad alto livello e spesso visualizzati come grafi. Purtroppo per questioni di complessità e di tempo ciò non è stato possibile, e quindi i materiali hanno opzioni fissate. Per quanto riguarda le proprietà fisiche i materiali hanno i seguenti attributi: un colore diffuso, uno speculare (entrambi una tripla RGB che assume valori da 0.0 a 1.0), un fattore di lucentezza, un indice di rifrazione, un indice di trasparenza.
Infine un materiale può contenere texture, nello specifico tre texture. La prima è una texture diffusa che viene moltiplicata con il colore diffuso, la seconda è una texture di rugosità per effettuare la perturbazione delle normali e quindi il bump mapping. Infine la terza texture è una texture di luminosità ossia è una fotografia alla quale viene applicata la convoluzione tra la mappa di radiazione e la funzione di riflessione della luce diffusa (utilizzando armoniche sferiche per abbattere la complessità); questa tecnica di Image Based Lighting consente di immergere la scena all'interno delle fotografie.


4.4 LA SCENA
La scena è stata suddivisa in una gerarchia di classi, dove ogni classe svolge delle funzioni logiche determinate; questo è stato fatto essenzialmente per avere una migliore pulizia del codice.
Alla radice della gerarchia abbiamo la classe base Scena che incorpora gli Oggetti 3D, le Luci, i Materiali, e la Telecamera. Scena svolge solo la funzione di calcolo dell'intersezione degli oggetti con il raggio tramite la funzione Intersezioni(). Oltre a trovare quale è l'intersezione più vicina (nel caso ci sia) Intersezioni() calcola la normale in quel punto e le coordinate di mapping.
L'immediata classe che eredita direttamente da Scena è ScenaLoader che svolge la funzione di caricare separatamente Luci, Oggetti 3D, e Materiali della scena.
La classe successiva che eredita da SceneLoader è ScenaRaytracer, essa prepara il setup delle matrici di proiezione e di vista, dell'immagine e dello z-buffer. Inoltre crea immagini sintetiche implementando l'algoritmo del Raytracing e del PathTracing presentati precedentemente.
Spesso il rendering di scene complesse può richiedere svariati minuti, quindi è stata inserita ScenaGL una classe di previsualizzazione via OpenGL derivata da ScenaRaytracer; questo è stato fatto per sfruttare la stessa pipeline di lighting, e quindi per avere risultati uguali, anzichè usare la pipeline di rendering di OpenGL. ScenaGL oltre che a renderizzare gli oggetti presenti nella scena, effettua la triangolazione degli oggetti parametrici quali sfere, piani, e cubi.
L'ultima classe che eredita da ScenaGL è ScenaGI. ScenaGI interfacciandosi con le classi MappaFotoni, e IrradianceCache crea immagini sintetiche implementando l'algoritmo del Raytracing combinato con il Photon Mapping e il Final Gathering. Seppur l'IrradianceCache sia un banale array di valori di intensità luminosa, è stata creata una classe a parte per poter facilitare la lettura e scrittura del codice.

BIBLIOGRAFIA

Per la realizzazione del progetto mi sono avvalso dei seguenti testi:

Jensen, Henrik Wann, “Realistic Image Synthesis Using Photon Mapping” . 2001, A K Peters.

Akenine-Möller, Tomas e Haines, Eric "Real-Time Rendering Second Edition". 2002, A K Peters.

Shirley, Peter “Realistic Ray Tracing”. 2000, A K Peters.

Hosted by www.Geocities.ws