Ottimizzazione della scena
Daniele Marini
1
Esigenze del RT rendering
• maggiori frame /sec
• risoluzione più alta
• oggetti più accurati e realistici
2
Limiti?
• Dimensioni e risoluzioni di frame buffer e
display crescono
• complessità della scena cresce, ci sono
modelli con 500 Mtriangoli o più
• qualità del rendering cresce
• quindi: occorre accelerare gli algoritmi
3
Escogitare strutture dati adeguate
• il problema della accelerazione è determinato dalla
complessità computazionale di un problema di
ricerca:
– trova gli elementi della scena che devono certamente
venire visualizzati (oppure che non devono certamente
venire visualizzati)
• lo scopo è di ridurre il numero di elementi da
esaminare e trasformare
• organizzare la geometria in qualche spazio ndimensionale per accelerare il problema di ricerca,
es: da O(n) a O(logn)
4
Soluzioni: strutture dati spaziali
• tre tipi principali di strutture dati spaziali:
– gerarchia di volumi di contenimento - bounding
volume hierarchy BVH
– alberi a partizione binaria dello spazio binary
space partition trees BSP trees
– alberi a otto rami octrees
5
Bounding Volumes
• possono essere:
– Sfere
– Scatole (box)
• AABB
• OOBB
• k-DOP
• E’ la soluzione più comune
6
Bounding Volumes
• La gerarchia di BV è organizzata ad albero,
le foglie contengono l’effettiva geometria,
nodi interni contengono puntatori a nodi
figli o a nodi foglia
• ogni nodo, incluse le foglie, comprende il
BV della geometria contenuta
• la radice ha un BV che contiene l’intera
geometria della scena
7
Alberi di BV
• in generale alberi a k figli, k-ary trees
• è definito il concetto di livello: la radice ha livello
0, una foglia discendente dalla radice ha livello 1
etc.
• un albero è bilanciato se tutti i nodi foglia sono al
livello h
• in un albero bilanciato il livello massimo è
floor(logkn) con n numero totale nodi (interni e
foglie)
8
Alberi di BV
• un albero è pieno (full) se tutti i nodi foglia sono alla stessa
altezza h (k è l’ordine dell’albero)
• il numero totale di nodi di un albero pieno è:
n=k0+k1+..+kh=(kh+1-1)/(k-1)
• il numero delle foglie è: l=kh il numero dei nodi interni è:
i=n-l
• se l’albero è binario k=2 e n=2l-1=2*2h-1
• più elevato è k minore è l’altezza dell’albero, più rapido
l’attraversamento
• l’albero binario è il più semplice da trattare
• si è verificato che l’efficienza maggiore si ottiene con
alberi di ordine k=2 o k=4 o k=8
9
Alberi BV
• La costruzione di un albero con k=8 si fa semplicemente
dividendo lo spazio lungo i tre assi principali
• con alberi BV la ricerca di intersezioni è ricorsiva dalla
radice; se un raggio non interseca un BV non interseca
neppure la geometria contenuta, e la ricerca nel sottoalbero
può terminare
• Nel caso di scene dinamiche la gerarchia BV deve venire
aggiornata: se il volume è spostato si controlla se
appartiene ancora allo stesso BV, altrimenti si rimuove il
volume e si ricomputa il padre, risalendo se necessario la
gerarchia fino alla radice
• Per computare un BV occorre trovare una scatola che
racchiude in modo efficiente i volumi della scena.
10
BSP trees
• due varianti principali:
– allineati agli assi axis aligned (aa)
– allineati ai poligoni polygon aligned (pa)
• si crea un BSP tree bisecando ricorsivamente lo
spazio con piani
• un vantaggio è che se l’albero è percorso in modo
opportuno, il contenuto geometrico dell’albero
può venire ordinato secondo qualunque punto di
vista (approssimato con aa esatto con pa)
– questo non è possibile con alberi BV
11
aa BSP trees
1. l’intera scena viene racchiusa in un AABB
2. la scatola viene suddivisa ricorsivamente con
piani allineati alle facce del AABB
3. i piani possono essere scelti in modo:
1. dividere il volume esattamente a metà
2. mettere nei sottovolumi circa la metà della geometria
4. la ricorsione termina quando si giunge a una
soglia
1. può essere l’altezza massima dell’albero
2. oppure il numero di primitive contenuto in un
sottospazio è inferiore a una soglia
12
aa BSP trees
• la strategia nella ricorsione può essere:
– ciclare a turno con piani orientati con gli assi: k-d trees
• si incomincia dividendo lungo x, poi i figli vengono suddivisi
lungo y e i nipoti lungo z, e si ripete il ciclo
– trovare il lato massimo del volume e suddividerlo
• in tal caso per avere un albero bilanciato bisogna dividere in
modo che i due semispazi abbiano circa lo stesso numero di
primitive, ma questo ha un costo
13
aa BSP trees
• come è ordinata approssimatamente la geometria
secondo il punto di vista?
– sia N il nodo in esame
– N diviene la radice da cui continua l’esplorazione
dell’albero
– l’attraversamento dell’albero prosegue nel semispazio
in cui si trova il punto di vista
– l’attraversamento di questo semispazio termina quando
qualche BV è dietro l’osservatore (il piano near)
– Si affronta poi l’attraversamento dell’altro semispazio
– L’attraversamento produce un ordinamento vicinolontano degli oggetti
14
pa BSP trees
1. si sceglie un poligono come luogo di divisione
dello spazio (il piano del poligono è il piano di
divisione)
2. ogni poligono intersecato dal piano di divisione
viene suddiviso un due sotto poligoni
3. ricorsivamente in ciascun semispazio si sceglie
un nuovo poligono che definisce il nuovo piano
di divisione
15
pa BSP trees
• il processo termina quando tutti i poligoni sono
stati esaminati
• è costoso, in genere si usa per scenari statici e
viene pre-computato
• si cerca di creare alberi bilanciati, scegliendo
poligoni che dividono circa a metà il sottospazio
16
pa BSP trees
• strategia di scelta bilanciata:
– si sceglie a caso un numero di candidati
– oppure si sceglie quello il cui piano suddivide
meno poligoni
• è stato dimostrato che in una scena con
1000 poligoni, 5 poligoni scelti a caso
bastano per creare un albero bilanciato
17
pa BSP trees
• ordinamento secondo il punto di vista
– dato il punto di vista l’albero può essere attraversato in ordine
secondo la direzione di vista, dal più lontano al più vicino
– si determina da che parte si trova il punto di vista rispetto al
nodo corrente (radice corrente)
– i poligoni nell’altro semispazio sono dietro l’osservatore
– si cerca ricorsivamente nel semispazio visibile un nuovo piano
che è più vicino al punto di vista
– si crea un ordinamento di poligoni dal più vicino al più lontano
adatti a un algoritmo del pittore (non si usa lo z-buffer)
18
F
A
C
B
C
G
A
B
D
E
F
G
D
E
Ordinamento di occlusione (non di distanza):
G C FAE BD
19
Octrees
• simile a un aa BSP tree
• suddivisione uniforme dello spazio: il punto
di divisione in tre piani ortogonali è sempre
al centro del sottospazio
• gli oggetti sono sempre nei nodi foglia
(criterio di terminazione)
• si tratta come aa BSP tree
20
Scene graph
• Anche scene graph possono essere usati per
organizzare lo spazio
• oltre alla geometria possono registrare
informazioni per il rendering e trasformazioni
• può essere organizzato ad albero
• i nodi possono avere associato anche un BV
• i nodi possono avere associato un intero albero di
qualunque tipo (organizzazione gerarchica di
scene complesse con oggetti in movimento anche
gerarchici: le trasformazioni sono nei nodi!)
21
Livelli di dettaglio LOD
• usare versioni semplificate di un modello in
funzione della distanza di osservazione
• spesso con LOD si usa effetto fog per
mascherare i minori dettagli
• tre parti:
– generazione dei LOD
– scelta del LOD
– switching tra LOD
22
Livelli di dettaglio LOD
• la generazione dei modelli LOD avviene in
fase di modellazione o in modo manuale o
automatico con algoritmi di semplificazione
• la selezione del LOD avviene stimando
l’area di schermo utilizzata, fissando soglie
– si sfruttano anche criteri di percezione visiva
23
Livelli di dettaglio LOD
• lo switching può provocare effetti di
popping
• diverse tecniche:
–
–
–
–
a geometria discreta,
blending,
alpha
CLOD e geomorphing
24
Livelli di dettaglio LOD
• geometria discreta
– si usano modelli a dettaglio differente e distinti
– quando necessario avviene lo switching
– manifesta effetti di popping
25
Livelli di dettaglio LOD
• blending
– si può interpolare geometricamente tra i due modelli ottenendo un
blending
– è costoso, si fa il rendering di due oggetti invece che di uno solo
– avviene solo per alcuni oggetti quindi il costo può essere
accettabile
– ci sono problemi per l’ordine con cui gli oggetti vengono trattati
nello z-buffer (artefatti)
– un modo per passare da LOD1 a LOD2 riducendo l’effetto
popping è di usare alpha buffer facendo crescere la visibilità di
LOD2 e decrescere quella di LOD1
26
Livelli di dettaglio LOD
• alpha
– gli oggetti sono tutti allo stesso LOD
– in funzione dell’area schermo utilizzata si controlla la
trasparenza dell’oggetto: al crescere della distanza e al
ridursi del numero di pixel coinvolti, la trasparenza
dell’oggetto cresce (operando su alpha buffer) fino a
scomparire
– dà luogo a un effetto gradevole e molto continuo, senza
artefatti;
– accelerazione effettiva nel rendering si ha solo quando
l’oggetto scompare (sotto la soglia di visibilità fissata)
27
Livelli di dettaglio LOD
• CLOD (continuous level of detail CLOD)
– la semplificazione che si usa per generare
diversi LOD viene sfruttata animando il
processo di semplificazione stesso
– si anima il collasso di ogni edge
– se i valori intermedi vengono salvati il processo
si può invertire (vertex split)
– richiede una precisa definizione del numero di
poligoni di ciascun livello
28
Livelli di dettaglio LOD
• geomorph
– si crea l’insieme dei modelli a diversi LOD
conservando la connettività tra i vertici
– al cambiare del LOD si sfrutta la connettività per
animare la trasformazione per interpolazione
– alla fine della trasformazione si opera solo sul nuovo
LOD
– l’interpolazione ha un costo
– gli oggetti sono in continua trasformazione (con le
texture questo è fastidioso)
29
Point based rendering
• Inventata nel 1985 da Marc Levoy, ora ha trovato
nuovi sviluppi
• Una superficie è rappresentanta da un insieme di
punti
• Il rendering avviene sui punti
– Un filtraggio gaussiano riempi i “buchi” tra i punti
• Si possono usare altri filtri
• I punti possono essere organizzati in gerarchie di
sfere che li contengono
– I punti sono resi come sfere (splat)che li contengono e i
30
buchi ancora riepniti con filtri
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
QuickTime™ e un
decompressore TIFF (Non compresso)
sono necessari per visualizzare quest'immagine.
31