Le rappresentazioni tramite voxel sono molto utilizzate nel rendering di film hi-end e nelle rappresentazioni scientifiche, ma solitamente sono troppo esigenti in termini di calcoli e memoria per essere usate nei videogiochi. Questo sta per cambiare. In questo articolo, esaminerò la possibilità di una transizione imminente dalla rasterizzazione poligonale al voxel tracing come il paradigma di rendering dominante mentre ci avviciniamo ad hardware capaci di sopportare scene sempre più complesse, e inoltre parlerò di alcuni approcci per mettere in pratica il voxel tracing nei processori grafici odierni, con un occhio particolare verso gli engine completamente basati sui voxel per le console di prossima generazione.
Le rappresentazioni poligonali sono molto efficienti per modellare superfici lisce, funzionano meno in presenza di un'alta complessità di scena e dimensioni frattali. Per passare a scenari molto complessi sono necessarie delle tecniche di livello del dettaglio, e questo è vero sia per le rappresentazioni tramite poligoni sia per quelle tramite voxel. Il caso limite, quando desideriamo una rappresentazione di una scena enorme senza nessun tipo di perdita, delle geometrie complesse composte da numerose superfici alla fine devono essere semplificate in un solo triangolo, che è considerevolmente più complesso di un singolo voxel.
La vegetazione rappresenta un tipico caso difficile: ha una grande dimensione frattale (rapporto tra area e volume della superficie) e dunque una rappresentazione quasi senza perdite richiederà pressappoco un numero equivalente di poligoni o voxel. Per di più, i voxel si prestano naturalmente per fenomeni pienamente volumetrici come nuvole, fumo, fuoco ecc. Dunque avendo dei voxel methods funzionanti, avremo il considerevole vantaggio di una singola rappresentazione unificata.
Possiamo rintracciare un'analogia con la storia della grafica 2D, quando a un certo punto la grafica basata sulle immagini diventò troppo dispendiosa e dominò la grafica vettoriale. La grafica con i voxel è il prossimo stadio delle tecniche visive nel 3D e alla fine ne otterrà tutti i vantaggi. Come ultima prova, basta pensare a come le moderne schede video non stiano più avanzando nel throughput “poligono”, anche se FLAP e bandwidth crescono esponenzialmente. Le schede video hi-end presenti oggi nel mercato presenterebbero dei rallentamenti in scene con centinaia di milioni di triangoli, ma possono facilmente tracciare una versione della stessa scena in tempo reale utilizzando i voxel.
APPROCCI PER IL VOXEL TRACING
I voxel sono solamente una rappresentazione di dati e come i triangoli si prestano alla resterizzazione o al tracing. Le rasterizzazioni voxel tramite splatting o proiezione sono sicuramente fattibili, ma non molto interessanti. La sfida chiave nel rendering di altà qualità è l'illuminazione, e il tracing è un semplice ma potente framework per degli effetti di luce complessi. Anche se la generazione di ray primari fosse semplice, i raggi secondari superano enormemente il numero di raggi primari quando ci si dirige verso un'illuminazione di alta qualità.
Esistono numerose strutture ad accelerazione spaziale che possono essere usate per il ray tracing: octrees, trees di axis aligned bounding box (AABB) e gerarchie di bounding volumes (BHV) per nominarne alcune. Qualsiasi struttura ad albero che normalmente memorizza dei triangoli all'interno dei suoi nodi può facilmente memorizzare anche i voxel. Nelle schede video è preferibile usare un'implementazione semplice e regolare, dunque mi sono concentrato su delle varianti dei trees abituali , o M-trees, che sono semplicemente alberi con dei nodi di dimensione uniforme e con un numero di branches pari a M. Con M = 2, otteniamo il tree familiare. Un M alto conferisce un compenso tra memoria e costo delle query, permettendo alberi poco profondi che possono essere attraversati velocemente, a scapito di una minore efficienza in memoria. I voxel vengono poi memorizzati in ciascun nodo, che possono essere aggregati in “bricks” (mattoncini) composti da BxBxB voxel per ridurre ancora la profondità dell'albero. Queste strutture sono molto comuni nella ricerca – per il trattato più recente si veda il progetto GigaVoxels di Cyril Crassin che descrive un'architettura simile nel dettaglio (
http://artis.imag.fr/Publications/2009/CNLSE09/ ).
Jon Olick ha sviluppato un'altra variante all'interno dello schema generale degli octree per voxel, che è stato descritto nella sua presentazione SIGGRAPH 2008: “parallelismo odierno e di prossima generazione nei videogiochi” (
http://s08.idav.ucdavis.edu/olick-current-and-next-generation-parallelism-in-games.pdf ). Il sistema di Olick non è brick-based, ciò comporta dei compensi abbastanza diversi rispetto agli schemi basati sui dei brick come quello di GigaVoxel o come il mio (che descriverò a breve).
Memorizzare un singolo voxel per nodo può effettivamente essere più efficiente in termini di memoria e compressione e permette delle tecniche specializzate di visita molto veloci, ma, come vedremo, ha uno svantaggio significativo quando si considera il filtering. Olick utilizza anche un octree irregolare più complesso che può essere ottimizzato offline per adattarsi meglio ai dati, al costo di aggiornamenti dinamici e di visita più complessi. Nella mia ricerca, ho preso indipendentemente una strada molto simile all'approccio di GigaVoxels, influenzato dalla stessa ricerca sui sistemi di M-tree brick-based per voxel.
STRUTTURE DATI
Esistono molti modi per implementare una struttura M-tree di voxel con B-brick. Io uso una struttura che distingue esplicitamente tra nodi interni (che hanno dei puntatori a figlio MxMxM) e nodi foglia (che non li hanno) – principalmente per risparmiare memoria. Tutti i nodi sono associati a un brick BxBxB di voxel per permettere il MIP mapping. Io adotto principalmente un approccio orientato su strutture di array con indici comuni.
La struttura che domina in termini di memoria è l'array di voxel bricks, seguito dall'array di bricks puntatori a figli, ma uso anche un array di puntatori a parent e un array di dati accessori compressi (posizione, profondità, score e alcune flag), arrivando a circa il 30% di eccesso rispetto a un dato voxel brick. In più, anche se M solitamente è 4, conservo sempre un array extra del puntatore a figlio 2x2x2, dato che questa struttura octree basica è molto più facile da manipolare durante gli update. L'array puntatore a figlio più grande può facilmente essere generato dall'octree base. I puntatori sono tutti indici a 32-bit, ma dato che ci sono al massimo qualche milione di nodi, alcuni di questi bit vengono usati per memorizzare flag addizionali. Dei valori ragionevoli per M e B sono 4 e 8, il che vuol dire che un voxel brick memorizza 512 voxel e un brick di puntatori memorizza 64 puntatori.
Questo schema permette una discesa veloce attraverso la struttura e non usa troppa memoria extra. Nello specifico, la memoria sprecata è direttamente proporzionale al valore di B, dato che brick grandi tendono a sprecare tanto nel padding dei voxel che vengono mappati in spazi vuoti o interni. Il sistema di Crassin, come tutti quelli GigaVoxels, adottano un approccio di memorizzazione differente, con nodi che memorizzano o un puntatori indiretto a un voxel brick o un valore costante di colore per l'interno nodo.
FILTERING E CONE TRACING
Il vantaggio più significativo di memorizzare un brick di BxBxB voxel per nodo è che questo permette un filtering dei voxel veloce e di alta qualità utilizzando l'hardware del filtering delle texture nativo della scheda grafica. Implementare manualmente un filtro lineare 3D richiederebbe otto accessi di memoria e parecchie dozzine di istruzioni, dunque rimpiazzare questo medoto con una singola componente nativa è un grande guadagno. Inoltre, un linear filtering pulito permette un'accumulazione diretta del valore alpha, premettendo un tracing approssimato di interi coni invece che di raggi.
L'esatta intersezione di un cono con un voxel è complessa, ma un cono può essere ragionevolmente approssimato con una serie di sfere, che a loro volta possono essere approssimate con una serie di box filters – che sono semplicemente singoli texture filters lineari 3D. Quest'approssimazione successiva non è così malvagia come potrebbe sembrare a primo impatto, per due ragioni: primariamente perché i coni sono tipicamente abbastanza stretti, e in secondo luogo, il frustum di un box è ragionevole quasi come un cono come scelta per modellare un flusso di luce che viene proiettato su un pixel.
Il cone tracing può essere molto più efficiente rispetto al ray tracing. I raggi sono discrete approssimazioni e il loro tracing richiede l'accumulo di dozzine di raggi che convergono correttamente e riducono l'aliasing. Effetti come ombre morbide, anti-aliasing, filtering anisotropico, profondità di campo, blurry reflection appropriate, e anche l'ambient occlusion, possono essere implementati con un numero esponenzialmente minore di coni rispetto ai raggi. La suddivisione dello schermo o del ray space può ridurre il numero di raggi richiesti per alcuni effetti, ma il vantaggio dipende dalla complessità della scena e può causare dei break down in scene complesse (giungle, erba e simili). Nel complesso, i coni sono molto più efficienti, e non sono significativamente lenti da tracciare per l'octree di brick che stiamo analizzando – dunque essenzialmente tutti questi effetti altrimenti difficili, li otteniamo gratuitamente.
[l'articolo continua e si conclude al seguente link]
