Continua e si conclude l'lo speciale in due parti di Game Developer: potete consultare la prima metà al seguente link.
STRATEGIE DI TRAVERSAL
Sono stati sviluppati degli efficienti algoritmi di ray traversal per i ray tracers poligonali e possiamo usare uno qualsiasi di questi algoritmi come punto di partenza. La differenza principale è nell'intersezione interna dei nodi foglia: invece di un'intersezione con una lista di triangoli, intersechiamo con un voxel brick, che comporta solamente passare attraverso il brick e accumularne i voxel estratti – più semplice e più veloce di intersecare raggi con triangoli. Timo Aila, insieme ad altri, ha pubblicato un'eccellente comparazione tra diversi metodi di traversal nelle moderne schede video (nvidia): “Understanting the Efficiency of Ray Traversal on GPUs” (
www.tml.tkk.fi/~timo/publications/aila2009hpg_paper.pdf ).
Comparano i ray tracers triangolari usando una rappresentazione di una gerarchia di bounding volume (BVH – Bounding Volume Hierarchy), ma il loro risultato è comunque rilevante per qualunque metodo di ray traversal. Il Ray Traversal potrebbe essere implementato negli shaders del DirectX or OpenCL ed è generalizzabile nelle odierne schede AMD, ma la mia implementazione e tutte le altre qui discusse sono implementate con CUDA di Nvidia, e alcune delle considerazioni sulle performance potrebbero essere specifiche in base alla piattaforma. Per essere breve, prenderò per scontata la familiarità con l'architettura CUDA – l'ultima documentazione può essere reperita dal sito Nvidia.
Esistono due principali problemi di performance quando si parla di ray traversal in una scheda video: le strutture a stack e il branching divergente. Un Ray Traversal diretto richiede una struttura dati stack per ogni raggio, il che risulta difficile su una scheda video a causa della scarsa (o inesistente) memoria locale. Ci sono un paio di opzioni utilizzando l'architettura della CUDA di Nvidia: memoria condivisa (on-chip), o memoria globale (off-chip, esiste anche la memoria locale ma per i nostri intenti è lo stesso con la globale). Aila ha ottenuto delle performance sorprendentemente buone memorizzando lo stack in memoria globale, anche se questo richiede costantemente scrivere e leggere dalla memoria off-chip. Il mio meotodo per il voxel tracing su octree evita la necessità di stack, come fa la tecnica di GigaVoxels, utilizzando invece un metodo di restart che non necessita stack, come vedremo. L'altro buco nero per quanto riguarda la performance è la divergenza dei thread, il quale rappresenta un vero problema. Entrambi i lati di branch divergenti devono essere esaminati, il che può sfociare in tanti sprechi a causa dell'ampiezza del SIMD (16 per la GT200 CUDA). Esistono numerose variazioni, ma il traversal while-while senza stack utilizzato in GigaVoxels può essere efficiente per le strutture M-tree con brick:
while-while restart trace( )
while ray non determinato
setta il nodo corrente come nodo radice
while profondità nodo corrente è minore della profondità del LOD target
visita il nodo seguente
while ray è all'interno del voxel brick del nodo
estrai il voxel corrente dall'interno del brick e accumulalo
Il metodo di traversal con restart evita la necessità di uno stack e di qualsiasi altra logica extra che passa attraverso i nodi vicini. Effettivamente visita in modo ridondante dalla radice alle foglie rilevanti continuamente, il che è dispendioso, ma dei brick abbastanza larghi e degli alberi poco profondi possono compensare questo spreco. Per esempio, con M = 4 e B = 16, occorreranno meno di dieci steps per arrivare a un nodo foglia, e questo tempo viene ammortizzato grazie a circa una dozzina di voxel samples. Ovviamente, dei voxel bricks così larghi sprecano memoria e incrementano i costi di streaming e generazione di dati dinamica. Per brick piccoli, una strategia di traversal neighbor-hopping (che salta tra nodi confinanti) potrebbe rendere meglio:
if-while stack trace( )
settare il nodo corrente come nodo radice
while ray non è determinato
if profondità nodo corrente è minore della profondità del LOD target
visita il nodo seguente
while ray è all'interno del voxel brick del nodo
estrai il voxel corrente dall'interno del brick e accumulalo
visita il seguente nodo vicino
Questo traversal neighbor hopping richiede un po' di memoria e logica extra, ma riduce il tempo speso per passare dalla rott al nodo foglia rilevante. Però, dovremmo considerare il costo rilevante di alcune di queste operazioni di pseudocodice. Arrivare a un nodo figlio è estremamente semplice in un octree standard e può essere fatto con una manciata di istruzioni vettoriali. Passare e prelevare all'interno di un brick è ugualmente molto semplice e veloce. Visitare un nodo vicino è più complicato, ma possiamo accelerare i tempi con una tabella di ricerca.
Come alternativa al neighbor-hopping, maggiori ottimizzazioni allo schema di restart sono possibili riducendo i passi necessari per saltare dalla radice a una foglia, arrivando a un processo molto semplice e senza divergenze:
branchless stackless restart trace ( )
while ray non determinato
setta il nodo corrente come nodo radice
trasferisci dal nodo radice al nodo foglia del target LOD
estrai il voxel corrente dall'interno del brick e accumulalo
Ovviamente sto offuscando un po' di dettagli con “trasferisci il nodo radice al nodo foglia del target LOD”, ma quest'operazione può essere fatta con un piccolo numero determinato di passi in un albero poco profondo e con un'altezza massima nota. Quest'ultimo schema si dimostra più veloce con brick piccoli ed è meno suscettibile a problemi che riguardano raggi divergenti, al costo di una media maggiore di stepping per estrazione di voxel.
PERFORMANCE E DUE GRANDI OTTIMIZZAZZIONI
Una strategia tipica degli shader consiste nell'allocare un thread per pixel, e dunque un thread per ray. Nella CUDA questi vengono poi raggruppati all'interno di blocchi user-sized che vengono inviati ai core della scheda video (che nella Nvidia si chiamano multiprocessori).Un'allocazione diretta di tiles in blocchi funziona bene per le task omogenee, come lo shading, ma è meno appropriata per compiti eterogenei come il ray tracing, dove il tempo di esecuzione di un thread varia profondamente. Aila propone una semplice ed efficace soluzione: thread persistenti. Invece di allocare abbastanza thread per blocco fino a formare l'intera immagine, si alloca un blocco di trhead per multiprocessore e si implementa il lavoro dinamico utilizzando delle atomic operation (operazioni atomiche). In questo modo nessun multiprocessore “rimane a secco”. Si è scoperto che questo metodo in media raddoppia le performance, e mi sono reso conto che è vero a anche per i metodi di visita degli octree.
La strategia di cone tracing illustrata sopra permette un altro grande guadagno di performance grazie a semplice tracing gerarchico. Con questo l'immagine viene creata in modo piramidale passando dallo stato grezzo a quello finale, cominciando con una versione a bassa risoluzione, per esempio 64x64. L'immagine è tracciata fino a quando i raggi accumulano un alpha value al di sopra di un certa soglia di y, dopodiché terminano prima e restituiscono la profondità. Quando comincia il tracing del livello successivo della piramide, i raggi possono cominciare dalla profondità restituita dal livello precedente invece di cominciare dalla camera, riducendo di molto la distanza da tracciare per i livelli di migliore qualità della piramide. Questa strategia è abbastanza semplice da implementare in un sistema di cone tracing usando il linear filtering, ed è possibile anche se considerevolmente più difficile, implementarlo all'interno de ray tracers discreti.
Con queste ottimizzazioni, ho trovato che un ray traversal di una scena di 720p con molte centinaia di milioni di voxel su una 8800 GT può durare dai 5 ai 16ms. Queste senza dynamic shading, solamente con un ray casting. Piuttosto sorprendentemente, una fonte primaria di variabilità è l'anistropia, perché con angoli molto luminosi i raggi impiegano molto più tempo per passare ai nodi foglia ottenendo meno benefici dal tracing gerarchico. La complessità geometrica non costituisce un problema insormontabile (dato che per rappresentare qualsiasi scena la quantità di voxel è sempre la stessa). E' abbastanza veloce – non veloce come una tipica rasterizzazione dello scenario di un gioco sullo stesso hardware, ma stiamo parlando di ordini di grandezza più geometricamente complessi rispetto ai tipici scenari di gioco, dunque è molto più veloce rispetto alla rasterizzazione in quel senso – e potrebbe essere significativamente più veloce con maggiori ottimizzazioni.
Questi risultati sono comparabili, su hardware simili, con i risultati pubblicati da GigaVoxel (30-90 fbs su una varietà di scene in una finestra 512x512) e con la demo del SIGGRAPH 2008 di Jon Olick (30-60 fps a 720p in una scena con un singolo modello complesso) Per comparare, questi tempi rappresentano un output netto che va da 50 a 200 millioni di raggi al secondo. Inoltre, il triangle tracer BVH di Aila, altamente ottimizzato, raggiunge circa 70-140 milioni di raggi ali secondo, su una GTX 285, che è veloce quasi il doppio di una 8800 GT, dunque il voxel cone tracing può essere più veloce rispetto al triangle tracing – oltre ai grandi benefici precedentemente menzionati comportati dal tracciare coni su raggi.
CONCLUSIONI
L'octree voxel tracing è già possibile con delle performance ragionevolmente alte su schede video che sono avanti di una sola generazione rispetto alle console odierne, dunque possiamo aspettarci performance adeguate per il ray tracing su risoluzioni considerevolmente più alte e/o per tracciare raggi dinamici secondari significativi sulle console next-generation e le prossime schede video hi-end. Il costo di memoria può essere un fattore limitativo e la compressione, l'active memory management, e lo streaming, che vanno oltre l'area d'interessa di questo articolo, sono tutti molto importanti per un sistema completo.
Il voxel tracing può essere combinato con delle strategie di deferred shading, o shading e la generazione di secondary ray possono persino essere integrati all'interno degli uber-kernel, come succede nell'architettura di triangle ray tracing della OptiX Nvidia. Una sfida particolare, qui non analizzata, è il problema dei dynamic updates, i quali rappresentano una nuova area di ulteriori ricerche nell'entusiasmante regno della grafica. Ho parlato delle basi delle strutture dati ad albero per voxel e delle strategia di traversal, che sono il nocciolo delle fondamenta del ray (o cone) tracing, ma questa è solo la punta dell'iceberg. Penso che gli engine per il voxel tracing daranno ai rasterizzatori poligonali del filo da torcere negli anni a venire e infine domineranno nei task di rendering grazie alla loro potenza, scalabilità e generalità.
JAKE CANNEL ha recentemente lavorato come graphics programmer per Pandemic Studios ed ha creato motori grafici e demo per lavoro o a casa per quasi dieci anni. Ha un blog che si occupa di grafica raggiungibile al link www [dot] enterthesingularity [dot] com.
