1

Ottimizzazione della scena

Daniele Marini

2

Esigenze del RT rendering

• maggiori frame /sec

• risoluzione più alta

• oggetti più accurati e realistici

3

Limiti?

• Dimensioni e risoluzioni di frame buffere e display crescono

• complessità della scena cresce, ci sono modelli con 5 Mtriangoli o più

• qualità del rendering cresce

• quindi: occorre accelerare gli algoritmi

4

Escogitare strutture dati spaziali

• 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 n-dimensionale per accelerare il problema di ricerca, es: da O(n) a O(logn)

5

Soluzioni

• tre tipi principali di strutture dati spaziali:– gerarchia di volumi di contenumento -

bounding volume hierarchy BVH– alberi a partizione binaria dello spazio binary

space partition trees BSP trees– alberi a otto rami octrees

6

Bounding Volumes

• possono essere:– sfere– AABB– OOBB– k-DOP

• E’ la soluzione più comune

7

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

8

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)

9

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 nodidi 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• più alto è k minore è l’altezza dell’albero• l’albero binario è il più sesmplice da trattare• si è verificato che l’efficienza maggiore si ottien con alberi

di ordine 4 o 8

10

Alberi BV

• con alberi BV la ricerca di intersezioni è semplificata, se un raggio non interseca un BV non interseca neppure la geometria contenuta

• la ricerca nel sottoalbero può terminare

11

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

12

aa BSP trees

1. l’intera scena viene racchiusa in un AABB2. la scatola viene suddivisa ricorsivamente con piani

allineati alle facce del AABB3. 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 soglia1. può essere l’altezza massima dell’albero2. può essere il numero minimo di primitive contenuto in

un sottospazio

13

aa BSP trees

• la strategia nella ricorsione può essere:– ciclare a turno con piani orientati con gli assi:

k-d trees– trovare il lato massimo del volume e

suddividerlo• in tal caso per avere un albero bilanciato bisogna

dividere inmodo che i due semispazi abbiano circa lo stesso numero di primitive, ma ha un costo

14

aa BSP trees

• come è ordinata approssimatamente la geometria secondo il punto di vista?– sia N il nodo attraversato– 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 termina quando qualche BV è dietro

l’osservatore

15

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

16

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

17

pa BSP trees

• strategia di scelta bilanciata:– si sceglie a caso un numero di candidati– tra essi si scegli 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

18

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

– determinare 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 divide davanti/dietro– si crea un ordinamento di poligoni dal più vicino al più lontano

adatti a un algoritmo del pittore

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 rendeering du 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 è 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– 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 (continuous level of detail CLOD)

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

tesxture questo è fastidioso)