PREDIZIONE CAPITOLO 2

CAPITOLO 2

PREDIZIONE

Il computo della visibilità PVS tra un punto ed una regione di spazio (piastra) è un problema affrontato ormai da più di 10 anni in CG per studiare la luminosità di uno scenario data una sorgente luminosa. Uno degli algoritmi più semplici fa uso di una versione modificata degli alberi BSP, i cosiddetti SVBSP [14].

In essi, ad ogni nodo è associato un piano d’ombra (partizionatore), ovvero il piano passante per la sorgente di luce (il punto di vista, nel nostro caso) e uno spigolo di un poligono posto di fronte ad essa. La direzione della normale del piano determina il semispazio nel quale un generico oggetto può trovarsi. Costruendo l’albero rispetto a tutti gli spigoli del poligono, le foglie interne ed esterne marcheranno rispettivamente le regioni interne ed esterne alla zona d’ombra originata dal poligono.

Con l’algoritmo SVBSP, per ogni oggetto di fronte al punto di vista sono necessari due passi:

• la determinazione delle ombre: il poligono viene filtrato attraverso l’albero SVBSP per determinare quali parti sono ombreggiate e quali in vista;

• l’aggiornamento dell’albero SVBSP: viene creata una nuova zona d’ombra per ogni parte in vista del poligono e viene aggiunta all’albero SVBSP.

Queste due operazioni grazie all’approccio 2.5D vengono eseguite in ambiente 2D. In questo modo i poligoni (piastre) sono sostituti dai rispettivi top edge e i piani d’ombra saranno delle rette passanti per il punto di vista e uno degli estremi del top edge.

Il modo più semplice per verificare se un poligono è in ombra (completamente invisibile) è confrontarlo con le zone d’ombra proiettate da tutti gli altri. Le piastre più lontane dal punto di vista rispetto a quella sotto test non possono in alcun modo

CAPITOLO 2. PREDIZIONE

“gettare” ombra su di essa. Di conseguenza, se processiamo le piastre in ordine front-to-back rispetto a tale punto, ogni piastra dovrà essere confrontata soltanto con le zone d’ombra delle piastre che sono già state processate e che sono più vicine alla sorgente rispetto alla piastra corrente. Come già detto, la lista ordinata delle piastre da processare viene creata grazie all’opportuna visitazione dell’albero VP. Per evitare inutili ridondanze che aumenterebbero il tempo di esecuzione, anziché controllare se una piastra giace in una delle zone d’ombra di tutti i poligoni di fronte ad esso, è più efficiente mantenere ad ogni passo una zona d’ombra che step-by-step viene aggiornata unendola alla zona d’ombra generata da ogni nuova piastra estratta dalla lista ordinata front-to-back. Poiché ogni piastra è confrontata soltanto con quelle più vicine rispetto ad essa al punto di vista, non c’è bisogno di testarla con quei piani d’ombra che passano per il top edge di queste piastre; quindi questi piani possono essere scartati. La zona d’ombra ad ogni passo risulterà in 2D un insieme di settori angolari semi-infiniti che si irradiano da un singolo apice corrispondente al punto di vista. Si veda a proposito la fig. 2.1.

Figura 2. 1 – zona d’ombra indotta da un punto di vista

La determinazione di quali frammenti della piastra siano in ombra è ottenuta filtrandone il top edge lungo l’albero SVBSP, spezzandolo ogni qualvolta giaccia in entrambi i semipiani indotti dal partizionatore del nodo corrente. I segmenti che raggiungono una foglia interna sono in ombra (in 2D), mentre quelli che arrivano ad

una foglia esterna sono visibili. Se tutti i segmenti di una piastra giungono su foglie interne, si è verificata la condizione necessaria non sufficiente per classificare la piastra i-esima “completamente invisibile” rispetto al punto di vista: necessiteremo di un ulteriore controllo sulla singola terza dimensione (coordinata z) della piastra. Se invece anche un solo segmento raggiunge una foglia esterna, la piastra può essere classificata “parzialmente o completamente visibile” e l’albero SVBSP andrà aggiornato E’ inoltre chiaro che non è necessario filtrare quelle piastre che non vedono secondo il back/face culling il punto di vista, poiché sappiamo già che sono in ombra rispetto ad esso.

Soffermiamoci sul caso in cui almeno un segmento sia risultato visibile: l’albero SVBSP deve essere aggiornato per includere il nuovo frammento di zona d’ombra. Questo può essere fatto semplicemente creando l’insieme dei piani d’ombra passanti per gli estremi del segmento e costruendo un albero SVBSP elementare per essi. Tale albero andrà a sostituire la foglia esterna. Per meglio comprendere il procedimento si faccia riferimento alla fig. 2.2.

Figura 2.2 – zona d’ombra indotta da un punto di vista e sua rappresentazione attraverso l’albero SVBSP

Inizialmente, l’albero conterrà una singola cella esterna. I top edge delle piastre 1 e 3 sono filtrate attraverso l’albero senza che ci sia nessun evento “splitted”; quando ad essere processata è la piastra 2, il suo top edge è diviso dalla retta (piano d’ombra)

passante per b in due segmenti, eg e gf. Il primo è completamente dentro una cella interna (il sottoalbero sinistro di b in figura), di conseguenza non è necessario inserire nuovi piani d’ombra; il secondo invece giunge ad una cella esterna: la foglia corrispondente viene quindi sostituita con l’albero SVBSP elementare costituito dai piani d’ombra passanti per g e f.

2.2 Condizioni di visibilità e invisibilità

Come precedentemente accennato, esiste una condizione necessaria non

sufficiente per l’invisibilità di una piastra (ovvero per classificare la piastra

“completamente invisibile” rispetto al punto di vista): tutti i frammenti del top edge della piastra devono raggiungere una cella interna dell’albero SVBSP. Ciò equivale a dire che la piastra è completamente dentro la zona d’ombra. La condizione non è sufficiente poiché una piastra può risultare invisibile in 2D mentre la sua altezza fa si che sia visibile in 3D elevandola al di sopra di tutti gli ostacoli posti tra essa e il punto di vista. Di conseguenza dovremo introdurre una condizione complementare per

l’invisibilità da applicare a quella necessaria non sufficiente già esposta. Essa si basa

sul confronto tra le altezze del punto di vista, della piastra corrente e degli ostacoli posti tra di essi. Per ostacolo si intende qui una piastra già processata che sia risultata visibile rispetto al punto di vista e almeno un segmento del top edge della quale giace nella cella interna dove è giunta la piastra corrente (o un suo segmento). Gli ostacoli presenti in una cella interna sono organizzati in una lista il cui puntatore è tra i campi della struttura del nodo che permette di accedere alla cella. Per capire come viene verificata tale condizione, si faccia riferimento alla fig. 2.3.

Conoscendo l’altezza della piastra corrente e del punto di osservazione, e la distanza tra di essi (definita come la distanza tra il punto e il centro della piastra), si può calcolare il coefficiente angolare del raggio che passa per il punto e il vertice superiore della piastra, e grazie a questo, alla distanza e all’altezza degli ostacoli stabilire se questi ultimi lo intercettano. La condizione complementare può quindi essere espressa come: in tutte le celle interne il raggio che connette il punto di vista allo spigolo superiore della piastra deve essere intercettato dagli ostacoli presenti nella cella.

Parimenti possiamo determinare delle condizioni di visibilità per la piastra, partendo dalla considerazione che rispetto ad un punto di vista, una piastra che risulti visibile in 2D lo è anche in 3D. La condizione sufficiente non necessaria per la visibilità di una piastra è dunque che almeno un frammento del suo top edge raggiunga una foglia esterna dell’albero SVBSP. Oltre ad essa, possiamo determinare una

condizione supplementare per la visibilità: per almeno una cella interna dove è

giunto uno dei segmenti del top edge della piastra corrente si deve verificare che nessuno degli ostacoli intercetti il raggio che connette il punto di vista allo spigolo superiore della piastra; in questo caso la piastra è classificata “completamente o parzialmente visibile” rispetto al punto di vista. La Tabella 4 riassume queste condizioni.

INVISIBILITA’ VISIBILITA’

ANALISI 2D Condizione necessaria

non sufficiente

Condizione sufficiente non necessaria

OPERATORE

LOGICO AND OR

ANALISI ALTEZZE Condizione

complementare

Condizione supplementare Tabella 4 – condizioni di visibiltà e invisibilità dell’algoritmo SVBSP

Per meglio comprendere come agiscano queste condizioni, si prenda ancora l’esempio di fig. 2.2. La piastra 1 è la prima ad essere selezionata per la costruzione

dell’albero SVBSP, per cui sarà sicuramente visibile; si passa quindi alla piastra 3: il segmento cd giace sicuramente in una cella esterna, per cui la piastra viene classificata visibile e l’albero SVBSP aggiornato. Infine viene processata la piastra 2: il segmento gf giace in una cella esterna, e ciò è sufficiente a classificarla visibile; tuttavia se la piastra fosse stata formata dal solo segmento eg, che giace in una cella interna, avremmo dovuto fare un’analisi delle altezze tra essa, il punto di vista e la piastra 1 che si frappone che induce la zona d’ombra. La piastra verrebbe classificata visibile o invisibile a seconda di quale condizione (complementare o supplementare) sia stata verificata

2.3 Considerazioni preliminari sull’implementazione del SVBSP

E’ importante notare che nell’esecuzione del SVBSP si deve porre particolare attenzione a due problemi. Innanzi tutto, il tipo di zona d’ombra che si è scelto (a settore angolare) da origine ad un’ambiguità nella rappresentazione che se ne ottiene grazie all’albero BSP. Si è infatti visto che il settore angolare ha apice nel punto di vista e si estende nella regione di spazio che comprende la piastra interessata. Tuttavia, se come partizionatore (piano d’ombra) del nodo dell’albero BSP corrispondente si sceglie la retta passante per il punto di vista e uno degli estremi del top edge della piastra, la cella interna dell’albero descriverà una regione di spazio che comprende sia la zona d’ombra sia una regione speculare ad essa rispetto al punto di vista, come si può vedere in fig. 2.4.

Figura 2.4 – ambiguità indotta dalla rappresentazione tramite albero BSP

della zona d’ombra

Per eliminare l’ambiguità, si è scelto di suddividere lo scenario in due parti grazie ad una retta di riferimento passante per il punto di vista e che per semplicità coincide con una delle due rette parallele agli assi cartesiani: l’algoritmo computa le relazioni di

visibilità punto-piastra prima per le piastre che giacciono in una parte, poi per quelle dell’altra, eliminando l’ambiguità dovuta alla rappresentazione degli alberi BSP. Questa retta di riferimento origina degli eventi “spanned”, ovvero delle intersezioni con un certo numero di piastre che quindi andrà analizzato in entrambi le parti dello scenario, aumentando i tempi di esecuzione.

Per diminuire il numero di tali eventi si fanno due cicli per contare le piastre attraversate dall’asse parallelo ad x (ciclo 1) e quelle attraversate dall’asse parallelo ad y (ciclo 2): l’asse scelto è quello relativo al ciclo che conta meno piastre. Viene quindi fatto un nuovo ciclo sulle piastre di PIAS2D per selezionare quelle che vedono secondo il back/face culling il punto di vista; se la condizione è falsa, il campo ‘sp’ assume valore 2, altrimenti gli viene assegnato un valore che indica a quale parte dello scenario appartiene la piastra: 1 (semipiano destro o superiore), -1 (semipiano sinistro o inferiore), 0 (entrambi i semipiani). La tabella 5 riassume quanto detto.

pias2d(i)%sp Attributo della piastra associata _{all’i-esimo elemento di PIAS2D} 2 Invisibile dal punto di vista

1

(visibile) contenuta completamente nel semipiano destro o superiore

indotto dalla retta di riferimento

0 (visibile) contenuta in entrambi i _semipiani

-1 (visibile) contenuta completamente nel semipiano sinistro o inferiore indotto dalla retta di riferimento Tabella 5 – attributi associati al valore del campo ‘sp’ dell’elemento pias2d(i)

Gli svantaggi derivanti da questa soluzione sono minori rispetto a quelli che si avrebbero scegliendo la soluzione alternativa: usare anche i piani d’ombra passanti per il top edge delle piastre per definire il SVBSP. La struttura che implementa il generico nodo degli SVBSP è infatti diversa da quella vista per l’albero VP, poiché contiene campi REAL per memorizzare i coefficienti dell’equazione esplicita della retta (piano d’ombra) e le coordinate dell’estremo che giace su di essa, oltre

ovviamente ai puntatori al sottoalbero destro e sinistro e un altro puntatore alla lista degli ostacoli; la memoria richiesta per ogni singolo nodo varia quindi a seconda dei processori da 20 a 40 kbyte. Si tenga inoltre presente che adesso sono necessari 3 nodi per ogni albero SVBSP elementare (e quindi per ogni piastra o segmento di piastra), anziché i 2 della soluzione precedente; ciò significa che aumenta anche la probabilità che si verifichino eventi “splitted”, eventi che a questo punto non possono essere minimizzati essendo stabilito l’ordine di processamento delle piastre. Questo fatto aumenta il limite superiore del numero di nodi che l’albero SVBSP può avere, limite imposto dall’Equazione (0.5), nella quale in questo caso ad n deve essere sostituito il valore 3n. Come si è visto, tale limite è direttamente proporzionale alla massima quantità di memoria che può essere richiesta all’elaboratore. In definitiva, del tempo di esecuzione della fase di predizione risulta essere preferibile.

Il secondo problema al quale si accennava è dovuto alla finitezza della precisione del floating point. Infatti, poiché i frammenti dei top edge diventano progressivamente più piccoli, l’equazione delle rette che passano per gli estremi diventerà progressivamente più inaccurata. La collinearità dei punti che si ottengono dividendo un top edge può essere preservata, a scapito dell’accuratezza dell’algoritmo, introducendo una soglia sui coefficienti dell’equazione.

2.4 Implementazione del SVBSP nell’EMvironment3.0

La routine che implementa l’algoritmo SVBSP prende il nome di PREDIZIONE; la routine viene lanciata subito dopo la creazione e l’inizializzazione di MULTI_ULTIMO o MULTI_PRIMO. Come si è visto, tra le altre cose essa opera una selezione preliminare delle piastre da processare: tali piastre devono vedere secondo il back/face culling il punto di vista, che può essere un trasmettitore o un ricevitore; le informazioni usate per questa selezione sono contenute proprio nei vettori MULTI_PRIMO e MULTI_ULTIMO. Per evitare di dover scrivere codici diversi, si è scelto di far lavorare la routine PREDIZIONE per entrambi i tipi di punto di vista: quindi, oltre alla posizione, andrà passato come argomento anche la tipologia del punto. Questa specifica viene usata anche dalla pseudo-routine “pos_side” della routine FRONT_TO_BACK presentata nel Cap.1.

Si è infatti detto che per la visitazione dell’albero VP è necessario stabilire la posizione del punto di vista rispetto a ciascun nodo. Per evitare ridondanze, è sufficiente ancora una volta usare le informazioni contenute in MULTI_PRIMO e MULTI_ULTIMO.

Una volta effettuata la selezione e la classificazione delle piastre, viene invocato un ciclo di due loop per analizzare lo scenario, corrispondenti alla scansione del semipiano destro (superiore) e sinistro (inferiore) indotti dalla retta di riferimento. Per ognuno di questi cicli, viene invocata la routine FRONT_TO_BACK; in essa è contenuta la routine DISPLAY che contiene i controlli per inizializzare i nodi da aggiungere alla lista ordinata delle piastre da processare (output di FRONT_TO_BACK). Per eseguire queste funzioni, DISPLAY dovrà contenere tra i suoi argomenti l’indice del loop corrente. La pseudo-codifica è riportata di seguito.

SUBROUTINE DISPLAY(n: ciclo loop, i: indice piastra, l: lista piastre) ! a viene posto pari all’indice dell’elemento di PIAS2D che contiene le ! informazioni relative alla piastra di indice i

a=cerca_elemento_pias2d(i)

IF ((n=1).AND.(pias2d(a)%sp = 1) THEN

! alloca un nuovo nodo per la lista delle piastre e lo inizializza ! con le informazioni contenute nel nodo corrente dell’albero ALLOCATE(nuovo_nodo, nodo_albero)

CALL inizializza(nuovo_nodo, nodo_albero) ELSE IF ((n=1).AND.(pias2d(a)%sp = 0)) THEN

ALLOCATE(nuovo_nodo)

! la seguente pseudo-routine “controlla_spanned” controlla se il ! frammento di top edge è attraversarto dalla retta di riferimento: ! in caso affermativo “var” è posto a .TRUE., altrimenti .FALSE. ! Nel primo caso nuovo_nodo viene inizializzato con i vertici ! opportuni

var=controlla_spanned(nodo%vertici) IF (var) THEN

CALL reinizializza(nuovo_nodo) ELSE

CALL inizializza(nuovo_nodo, nodo_albero) ENDIF

ELSE IF ((n=2).AND.(pias2d(a)%sp =-1) THEN

ALLOCATE(nuovo_nodo, nodo_albero) CALL inizializza(nuovo_nodo, nodo_albero)

Usciti dalla routine FRONT_TO_BACK, inizia l’algoritmo SVBSP vero e proprio. Viene infatti lanciata una scansione sulla lista: il puntatore INDICE punterà al nodo della piastra corrente da esaminare. Grazie ad esso, viene inizializzata la variabile TEST che contiene le coordinate degli estremi del top edge (o del frammento del top edge, se la piastra è “spanned”) da analizzare. Quindi si controlla che il puntatore alla testa dell’albero SVBSP sia associato; se non lo è, non è stata ancora esaminata nessuna piastra, per cui quella sotto test è sicuramente visibile: il campo ‘visible’ (impostato di default su .FALSE.) dell’elemento di PIAS2D relativo alla piastra viene posto TRUE. Vieni quindi lanciata la subroutine CREA_SVBSP che crea e inizializza l’albero SVBSP elementare che descrive la zona d’ombra di TEST. La pseudo-codifica è riportata di seguito:

SUBROUTINE CREA_SVBSP (root: radice dell’albero; indice; test) DO j=1, 2

ALLOCATE(nuovo_nodo)

CALL coefficienti_retta(p_obs , test, nuovo_nodo) CALL punto(test, nuovo_nodo)

! inserisce il nuovo nodo nell'albero SVBSP elementare IF (j=1) THEN

root=>nuovo_nodo ELSE

CALL orienta_nodi(root, nuvo_nodo) root%pos=>nuovo_nodo

! inserisce un nuovo nodo nella lista degli ostacoli associata a nuovo_nodo ALLOCATE(ostacolo) ostacolo%indice_piastra=indice%indice_piastra nuovo_nodo%lista_ostacoli=>ostacolo END IF END DO END SUBROUTINE

ELSE IF ((n=1).AND.(pias2d(a)%sp = 0)) THEN ALLOCATE(nuovo_nodo)

var=controlla_spanned(nodo%vertici) IF (var) THEN

CALL reinizializza(nuovo_nodo) ELSE

CALL inizializza(nuovo_nodo, nodo_albero) ENDIF

END IF

CREA_SVBSP lancia un ciclo di due loop; per ognuno di essi, alloca un nodo dell’albero SBSVP e lo inizializza con i coefficienti dell’equazione esplicita della retta che delimita la zona d’ombra e con le coordinate dell’estremo di TEST sotto esame (primo loop primo vertice, secondo loop secondo vertice). A questo punto, controllando l’indice del ciclo, può o associare la radice dell’albero SVBSP al nodo o chiamare la routine ORIENTA_NODI. Tale routine assegna il segno ai coefficienti delle rette registrate nei due nodi in modo che il punto della prima cada nel semispazio positivo indotto della seconda e viceversa: in questo modo otteniamo un albero SVBSP elementare come quello associato alla piastra 1 in fig. 2.2. Viene quindi allocato un elemento della lista degli ostacoli, relativo alla cella interna dell’albero, che viene fatto puntare dal secondo nodo.

RECURSIVE SUBROUTINE merge_svbsp (n: nodo corrente; indice,;s: segmento sotto test) ! s_in è il puntatore alla parte del segmento che giace nella zona d’ombra

! s_ext è il puntatore alla parte del segmento che giace fuori dalla zona d’ombra CALL partiziona(n, s, s_in, s_ext)

IF (ASSOCIATED(s_ext)) THEN s=s_ext

IF (ASSOCIATED(n%neg)) THEN

CALL merge_svbsp(node_o%neg, indice, s) ELSE

! aggiorno l’albero SVBSP

CALL crea_svbsp(nuovo_nodo, indice, s) n%neg=>nuovo_nodo) indice%splitted=.TRUE. ENDIF ENDIF IF (ASSOCIATED(s_in)) THEN s=s_in IF (ASSOCIATED(n%pos)) THEN

CALL merge_svbsp (n%pos, indice, s) ELSE

! visible è la variabile locale che classifica la visibilità del segmento nella cella visible=.FALSE.

CALL cfr_altezza(n%lista_ostacoli, indice, visible) IF (visible) THEN

! aggiunge un nuovo nodo alla lista degli ostacoli

CALL aggiungi_nodo(n%lista_ostacoli, indice) indice%visible=.TRUE.

ENDIF ENDIF ENDIF

Nel caso in cui invece la radice di SVBSP sia già associata, TEST viene passato alla routine MERGE_SVBSP che opera l’analisi di visibilità 2D (cfr. Tabella 5) e aggiorna l’albero. La pseudo-codifica è riportata poco sopra.

MERGE_SVBSP è una routine ricorsiva; innanzitutto verifica se il segmento è diviso dal partizionatore del nodo, nel qual caso lo suddivide in altri due segmenti che passerà ai rispettivi sottoalberi. Se invece il segmento giace completamente in uno dei due semipiani, lo passerà al solo sottoalbero interessato. Le condizioni di uscita dalle ricorsioni si hanno quando il segmento (o un suo frammento) raggiunge una cella: se è una cella esterna, il campo ‘visible’ dell’elemento di PIAS2D corrispondente alla piastra sotto esame viene posto TRUE, e l’albero viene aggiornato; se la cella è interna, viene chiamata la routine CFR_ALTEZZA che compie l’analisi sull’altezza della piastra. Se la piastra è visibile all’interno della cella, la lista degli ostacoli viene aggiornata e il campo ‘visible’ dell’elemento di PIAS2D corrispondente alla piastra sotto test viene posto TRUE.

Usciti da MERGE_SVBSP, si passa alla piastra successiva in lista e si ripete la procedura; la scansione della lista va avanti fino a che non ci sono più piastre da analizzare; a questo punto viene cancellato sia l’albero SVBSP che la lista delle piastre, e si passa al secondo ciclo. Concluso anche questo, inizia la fase di riscrittura del vettore relativo alla visibilità del punto di vista, concordemente con le condizioni di visibilità e invisibilità (cfr. Tabella 5): viene fatto un ultimo ciclo sull’array PIAS2D per verificare come è impostato il campo ‘visible’ di ognuno dei suoi elementi. Se è FALSE, l’elemento del vettore MULTI_PRIMO o MULTI_ULTIMO relativo alla piastra in questione viene posto a 0. Nello stesso ciclo viene anche reimpostato su 2 il campo ‘sp’ e su FALSE quello ‘visible’ di tutti gli elementi di PIAS2D: in questo modo si evitano errori nella successiva chiamata della routine PREDIZIONE. Il suo funzionamento completo è riportato nei Diagrammi di flusso 3, 4, 5.