Informatica Grafica a.a. 2010-2011 DICGIM – University of Palermo Dipartimento di Ingegneria...

Informatica Grafica a.a. 2010-2011

DICGIM – University of Palermo

Dipartimento di Ingegneria Chimica, Gestionale, Informatica e Meccanica

Determinazione delle superfici visibili

Prof. Roberto Pirrone

31 maggio 2011



Sommario

GeneralitàTipologie di algoritmi DSV

PreprocessingConfronto tra volumi includenti

Back-face culling

Algoritmi principaliRoberts

Z-buffer

Depth sort

BSP tree

Scan-line

Wieler-Atherton

31 maggio 2011



Generalità

Il processo di rendering di un’immagine sintetica è molto oneroso dal punto di vista computazionale. Risultano necessarie delle tecniche per ridurre quest’onere di calcolo.

Gli algoritmi che svolgono quest’analisi vanno sotto il nome di tecniche di determinazione delle superfici (o delle linee) visibili (DSV), noti anche con la denominazione di eliminazione delle superfici (o delle linee) nascoste.

31 maggio 2011



Generalità (2)

Tali algoritmi consistono nell’eliminiazione di ciò che non è effettivamente visibile dall’osservatore.

Trovano applicazione anche nella generazione delle ombre poiché per determinare un’ombra bisogna valutare quali siano le superfici visibili dal punto di vista della sorgente luminosa.

Essi vengono applicati dopo il clipping ed assumendo una proiezione parallela, eventualmente avendo trasformato il volume di vista canonico prospettico in quello ortografico.

31 maggio 2011



Tipi di algoritmi

Algoritmi di tipoImage space/precision

Object space/precision

Tecniche di pre-elaborazioneConfronto tra volumi includenti

Back face culling

31 maggio 2011



Confronto tra volumi includenti

Si confrontano i minimi parallelepipedi o le minime sfere includenti per escludere oggetti totalmente invisibili.

Possibilità di falsi positivi.



Back-face culling

Si calcola prodotto scalare della normale uscente dal poligono con il versore dell’asse z negativo (0,0,-1):

. Se questo prodotto è positivo, cioè se la normale Np ha componente z<0, allora il poligono non guarda verso l’osservatore e può essere scartato. l’algoritmo DSV si applicherà solo sui rimanenti.



Algoritmi DSV

Algoritmi per la visibilità di linee (object space)Algoritmo di Roberts

Algoritmi per la visibilità di singoli pixel (image space)Z-buffer e suoi derivati

Algoritmi basati sull’ordinamento di liste di poligoni (di tipo ibrido object/image space)

Depth sortBSP tree

Algoritmi di tipo scan line, di tipo image space che combinano la DSV con la scansione raster.Algoritmi a suddivisione di aree (object space o image space) si suddivide il piano di proiezione in aree sempre più piccole fino a quando si può determinare con esattezza la visibilità in ciascuna.

Algoritmo di Wieler-Atherton.

31 maggio 2011



Algoritmo di Roberts

calcolo della cosiddetta “invisibilità quantitativa” dei lati di un poligono che è 0 per le linee visibili, cresce per ogni intersezione entrante con una linea di contorno che sia davanti al lato su cui ci si sta muovendo e decresce per ogni intersezione uscente.

l’algoritmo utilizza il calcolo dell’intersezione tra il triangolo formato dagli estremi del segmento in considerazione e dal punto di vista con una qualunque linea di contorno per vedere se questa passa davanti o dietro al lato stesso.



Z-buffer

L’algoritmo Z-buffer è, forse, l’approccio più usato per la DSV.

E’ semplice, si può integrarlo con il processo di rendering, di calcolo delle ombre e di estenderlo con caratteristiche di anti-aliasing. Inoltre è possibile realizzarne una versione di tipo scan-line per ridurre la memoria utilizzata.

lo Z-buffer consente di effettuare il rendering di nuovi oggetti nella scena senza dover ri-calcolare tutto dall’inizio.

31 maggio 2011



Z-Buffer

Si usano due buffer di dimensione pari all’immagine da visualizzare: il frame buffer F(x,y) che contiene il colore dei singoli pixel e lo Z-buffer o depth buffer Z(x,y) che contiene i valori di profondità di ogni punto proiettato sull’immagine.

Se la z del punto appartenente al poligono in esame, che si proietta in (x’,y’), è maggiore (più vicina) di quella presente in Z(x’,y’) allora viene sostituita al valore di Z(x’,y’) ed il colore di quel punto viene scritto nel frame buffer in F(x’,y’).

31 maggio 2011



Traccia dello Z-Buffer

Ripeti per x che va da 1 a larghezza_immagineRipeti per y che va da 1 a altezza_immagine

F(x,y)=BACKGROUNDZ(x,y)=-1 // profondità del back-plane del

// volume di vista normalizzatoFine ripeti

Fine ripetiRipeti per ogni poligono

Ripeti per ogni punto p(x,y,z) proiettato in (x,y)Se z>Z(x,y)

Z(x,y)=zF(x,y)=p

Fine ripetiFine ripeti

31 maggio 2011



Calcolo di z(x,y) all’interno di un poligono

Forma

incrementale

Interpolazione bilineare (usata anche nello shading)

31 maggio 2011



Esempio di Z-Buffer31 maggio 2011



Algoritmo Depth-Sort

Ordina i poligoni per valori decrescenti di z // dal più vicino al più lontanoRipeti per ogni poligono p dall’ultimo al primo

Ripeti per tutti i poligoni q precedentiSe l’estensione in x dei poligoni non si sovrappone

Vai al prossimo poligono nella listaAltrimenti se l’estensione in y dei poligoni non si sovrappone

Vai al prossimo poligono nella listaAltrimenti se p si trova totalmente sul lato back-facing di q

Vai al prossimo poligono nella listaAltrimenti se q si trova totalmente sul lato front-facing di p

Vai al prossimo poligono nella listaAltrimenti se le proiezioni in (x,y) dei due poligoni non si

sovrappongonoVai al prossimo poligono nella lista

Altrimenti // probabile occlusioneSe q si trova totalmente sul lato back-facing di p OR p si trova totalmente sul lato front-facing di q

scambia q e pAltrimenti

Dividi q e p intersecandoliOrdina i nuovi poligoni nella lista

Reinizializza la scansione della listaFine ripeti

Fine ripeti

31 maggio 2011



Algoritmo Depth-Sort31 maggio 2011



Algoritmo BSP tree

l’algoritmo BSP (Binary Space Partition) tree, crea un albero di partizioni dello spazio in coppie di semispazi front-facing e back-facing, rispetto alla normale ogni poligono della lista.

A partire da un poligono radice, in ogni partizione sono raccolti i poligoni che si trovano interamente nei due semispazi, mentre quelli che sono intersecati dal piano cui appartiene il poligono radice vengono divisi in due.

Il processo si ripete, scegliendo un nuovo poligono radice per ogni semispazio.

31 maggio 2011



Esempio di BSP tree31 maggio 2011



Algoritmo di visita del BSP tree

Se il punto di vista è di fronte al poligono_radiceVisita il sottoalbero backMostra poligono_radiceVisita il sottoalbero front

AltrimentiVisita il sottoalbero frontMostra poligono_radiceVisita il sottoalbero back

31 maggio 2011



Algoritmo scan line

l’algoritmo scan-line per la DSV possiede molte caratteristiche in comune con l’equivalente algoritmo per la scansione raster dei poligoni nel caso bidimensionale: la principale differenza è che viene gestita una lista di poligoni e non un singolo poligono.

L’algoritmo impiega diverse strutture di dati:Tabella degli edge (ET)Tabella dei poligoni (PT)Tabela degli edge attivi (AET)

31 maggio 2011



Algoritmo scan line

La ET è un array di liste di lati di tutti i poligoni, indicizzata con la ymin (ordinata dell’estremo inferiore) di ognuno di essi. Ogni lato contiene:

ID del poligono di appartenenzaL’ascissa dell’estremo inferiore x(ymin)L’ordinata dell’estremo superiore ymax

L’incremento ∆x=1/m per il tracciamento del lato in maniera incrementale: x(y + 1) = x (y) + 1/m

La PT è una lista i cui elementi contengono:ID del poligonoI coefficienti dellequazione del pianoI parametri di shading del poligono o il suo colore unicoUn flag booleano in, inizialmente posto a false, per indicare se la linea di scansione è interna al poligono

31 maggio 2011



Edge table31 maggio 2011



Tracciamento raster incrementale di una retta (DDA)

Una retta sul raster può essere tracciata attraverso la sua equazione y=mx+q

Le coordinte raster sono intere quindi:ynew=m(x+1) + q=mx + q + m=y + m

Vale solo per |m|<=1 per cui ad ogni passo x si incrementa certamente di 1

Nel caso di |m|>1 è certo che y ad ogni passo si incrementa di 1 quindi:

xnew=(y+1)/m - q/m=(y - q)/m + 1/m = x + 1/m

31 maggio 2011



Algoritmo scan line

Per ogni linea di scansione di quota yc, la AET è costruita dalla ET aggiungendo i lati tali che ymin<=yc e rimuovendo quelli per cui ymax<yc.

Gli elementi della AET sono ordinati secondo x crescente

L’algoritmo non tiene conto di poligoni che si intersecano: i poligoni vengono suddivisi lungo le loro intersezioni in modo da ottenere sempre poligoni tutti avanti o dietro gli altri ed utilizzare la coerenza della linea di scansione per ogni tratto che va da un lato allaltro di AET.

Per il tracciamento da un lato all’altro di AET si usa il “colore” (colore solido, tessitura, shading, altra tecnica di rendering) del poligono a z massima tra tutti quelli che si proiettano nel pixel considerato

31 maggio 2011



Traccia dell’algoritmo scan-line31 maggio 2011

y=y0 //minima linea di scansioneRipeti finché AET==null e ET==null

Inserisci gli elementi di ET(y) ordinatamente in AET Rimuovi ET(y)

Ripeti per ogni elemento i di AETSe AET(i).ymax<y Rimuovi AET(i)Altrimenti Aggiorna AET(i).x= AET(i).x+ AET(i).∆xFine ripetiRipeti per ogni elemento i di AET

PT(AET(i).ID).in=not(PT(AET(i).ID).in)Se PT(AET(i).ID).in==true AND z(PT(AET(i).ID),x,y) è la massima z di tutti i poligoni “in”

Traccia la linea di scansione fino a AET(i+1).x-1 con il colore di PT(ID)

Altrimenti Traccia la linea di scansione fino a

AET(i+1).x-1 con il colore di PT(IDzmax)Fine ripetiY=y+1

Fine ripeti



Algoritmo scan line (3)31 maggio 2011



Algoritmo di Wieler-Atherton31 maggio 2011

L’algoritmo di Wieler-Atherton è un approccio basato sull’idea che si possa procedere per successive suddivisioni del piano di proiezione della scena, cercando di individuare delle regioni in cui si possa decidere, senza alcun dubbio, sulla visibilità o meno.

Al contrario di altri approcci di tipo image space, come l’algoritmo di Warnock che suddivide il piano in quadranti sempre più piccoli, al più coincidenti con il singolo pixel, questa tecnica “ritaglia” le porzioni sovrapposte dei vari poligoni della scena.




Ogni poligono della lista, ordinata in senso crescente per massima z di ogni poligono, è utilizzato per effettuare il clipping di tutti gli altri.

Tutte le porzioni ritagliate, cioè quelle la cui proiezione ricade all’interno della proiezione del poligono corrente, che si trovano dietro al poligono, sono certamente invisibili e vanno scartate.




Se ci sono porzioni ritagliate che stanno davanti, allora si effettua un’operazione in cui il poligono contenente la porzione ritagliata viene usato per fare il clipping del poligono corrente al fine di determinare la porzione visibile di quest’ultimo, cioè la sua porzione esterna rispetto al poligono di taglio.

Questa operazione è, in genere, ricorsiva perché potrebbero esserci più porzioni ritagliate che stanno davanti al poligono corrente.




Alla fine sono disponibili tutte le porzioni visibili che ricadono nell’area del poligono corrente le quali vengono mostrate e si passa al successivo poligono della lista.

Per effettuare il clipping si considerano sempre i poligoni originali e non le porzioni visibili.

Informatica Grafica a.a. 2010-2011 DICGIM – University of Palermo Dipartimento di Ingegneria...

Documents

Transcript of Informatica Grafica a.a. 2010-2011 DICGIM – University of Palermo Dipartimento di Ingegneria...