TEORIA APPLICATA

 

Questa sezione prenderà in esame la parte teorica utilizzata per la creazione di questo applet.

 

SCOPO DEL PROGRAMMA

Lo scopo prefissato a questo programma è quello di visualizzare due cubi in wireframe tenendo conto del problema della sovrapposizione dei segmenti che formano gli spigoli dei cubi (che chiameremo edges) rispetto ad un punto di vista (chiamato eye). L'algoritmo per gestire questa sovrapposizione tra due edges calcola quale dei due copre l'altro rispetto ad eye e disegna spezzato nel punto d'intersezione l'edge coperto.

In pratica dati quattro punti a,b,c,d nello spazio 3D che formano i due edge ab e cd (come si vede in Fig1. (A) ) supponendo che rispetto all'osservatore l'edge ab copra cd, il programma deve restituire un risultato simile a quello mostrato in Fig.1 (B).

Per rendere più chiaro all'utente la teoria applicata per la creazione di questo programma verrà suddivisa questa sezione in due parti principali: nella prima parte verranno illustrate le parti di geometria alla base del programma, mentre nella seconda parte verrà mostrato il funzionamento dell'algoritmo tramite i suoi vari passaggi logici, ed il link al listato del programma.

 

PRIMA PARTE

I principali punti necessari per comprendere come, poi, l'algoritmo raggiunga il risultato visto nella Fig.1 (a) sono:

PUNTO 1 - il capire quando due edge nello spazio 3D si incrociano rispetto un punto di vista (eye);

PUNTO 2 - il capire quale dei due edge copre l'altro rispetto al punto eye;

PUNTO 3 - il passaggio dallo spazio 3D allo spazio 2D e quindi come avviene la conversione delle coordinate dei punti che formano la figura tridimensionale nei loro corrispettivi bidimensionali;

PUNTO 4 - il trovare nella rappresentazione 2D il punto di intersezione tra i due edges in esame, per poter eseguire una corretta rappresentazione grafica.

 

PUNTO 1- VERIFICA INCROCIO DI DUE EDGES

In questo punto viene spiegato come si capisce se due edges in uno spazio di coordinate tridimensionale si intersecano rispetto ad un punto di vista chiamato eye.

Prendiamo come esempio la situazione di Fig.2.

Abbiamo 4 punti a,b,c,d (identificati dalle loro coordinate X,Y,Z per i tre assi) che formano due edges ab e cd.

Quindi avremo a=(xa,ya,za) b=(xb,yb,zb) c=(xc,yc,zc) d=(xd,yd,zd).

Per prima cosa si calcola l'equazione del piano ( Ax+By+Cz+D=0 ) formato dai punti c,d,eye.

L'equazione di un piano Ax+By+Cz+D=0 passante per tre punti generici a=(xa,ya,za), b=(xb,yb,zb), c=(xc,yc,zc) viene calcolato dall'algoritmo con le seguenti 4 equazioni che restituiscono come risultato rispettivamente A,B,C e D.

A=-((-1*(zb-za)*(yc-ya)*(zb-za))+((zb-za)*(zc-za)*(yb-ya)))

B=-(((zb-za)*(xc-xa)*(zb-za))-((zb-za)*(xb-xa)*(zc-za)))

C=-(((xb-xa)*(yc-ya)*(zb-za))-((xb-xa)*(zc-za)*(yb-ya))-((yb-ya)*(xc-xa)*(zb-za))+((yb-ya)*(xb-xa)*(zc-za)))

D=-(xa*((zb-za)*(zb-za)*(yc-ya))-xa*((zb-za)*(zc-za)*(yb-ya))-za*((xb-xa)*(yc-ya)*(zb-za))+za*((xb-xa)*(zc-za)*(yb-ya))+za*((yb-ya)*(xc-xa)*(zb-za))-ya*((zb-za)*(xc-xa)*(zb-za))+ya*((zb-za)*(xb-xa)*(zc-za))-za*((yb-ya)*(xb-xa)*(zc-za)))

Queste quattro formule vengono calcolate nel seguente modo:

1° - si calcola il vettore spostamento b dal punto a al punto b che non è altro che b=(xb-xa,yb-ya,zb-za);

2° - si calcola il vettore spostamento c dal punto a al punto c che non è altro che c=(xc-xa,yc-ya,zc-za);

3° - si risolve il sistema tra le seguenti 3 equazioni:

[1] x = xa+F*(xc-xa)+G*(xb-xa)

[2] y = ya+F*(yc-ya)+G*(yb-ya)

[3] z = za+F*(zc-za)+G*(zb-za)

Una volta ottenuta l'equazione del piano, si sostituiscono in questa le coordinate dei due punti a e b. Se i risultati delle due sostituzioni hanno stesso segno allora non vi è più nulla da fare in quanto i due edge non si intersecano rispetto al punto di vista eye (vedi Fig.2 (A) ). Altrimenti se i segni NON sono concordi, si rieffettua lo stesso procedimento di prima, ma con l'altro edge; cioè si calcola il piano ( A'x+B'y+C'z+D'=0 ) formato dai punti a,b,eye ed una volta ottenuto si sostituiscono i valori delle coordinate dei punti c e d nell'equazione del piano e se i risultati delle due sostituzioni hanno stesso segno allora non vi è più nulla da fare in quanto i due edges non si intersecano rispetto al punto di vista eye (vedi Fig.2 (B) ). Al contrario se i due segni NON sono concordi vuole dire che i due edges si intersecano rispetto al punto di vista eye (vedi Fig.2 (C) ).

 

PUNTO 2 - PRIORITA' VISIVA

In questo punto viene spiegato come viene gestita la sovrapposizione di due edges rispetto ad un punto di vista eye; cioè quale tra i due edges che si intersecano rispetto ad eye copre l'altro.

Prendiamo come esempio la situazione di Fig.3.

Abbiamo 4 punti a,b,c,d (identificati dalle loro coordinate X,Y,Z per i tre assi) che formano due edges ab e cd.

Quindi avremo a=(xa,ya,za) b=(xb,yb,zb) c=(xc,yc,zc) d=(xd,yd,zd).

Per prima cosa si calcola l'equazione del piano formato dai punti a,c,d. Una volta ottenuto il piano ( A''x+B''y+C''z+D''=0 ) si sostituiscono le coordinate dei due punti b ed eye nel piano e se i risultati delle due sostituzioni hanno stesso segno allora vuole dire che l'edge ab nasconde l'edge cd rispetto al punto eye (vedi Fig.3); mentre se i risultati NON sono concordi allora sarà l'edge cd a nascondere l'edge ab rispetto al punto eye.

 

PUNTO 3 - CONVERSIONE DELLE COORDINATE

La rappresentazione bidimensionale di un oggetto solido, come si può vedere dalla Fig.4, si realizza proiettando i punti dello spazio 3D su un piano P (detto piano di proiezione) rispetto ad un punto di vista chiamato eye.

Nel nostro programma ognuna delle tre viste selezionabili (FRONTALE, SOPRA e LATERALE) utilizza un piano di proiezione ed un punto di vista. Avremo per la vista FRONTALE il piano di proiezione perpendicolare all'asse Z; per la vista SOPRA il piano sarà perpendicolare all'asse Y ed infine per la vista LATERALE sarà perpendicolare all'asse X.

Per esempio, per ottenere la conversione delle coordinate del punto a=(xa,ya,za) dello spazio 3D in a'=(x'a,y'b) dello spazio 2D per la vista FRONTALE vengono utilizzate le seguenti formule:

x'a=(xa/za)*F+xc

y'a=(ya/za)*F+yc

dove xc e yc sono le coordinate 2D del centro dello schermo ed F il fattore di prospettiva, il quale non è altro che la distanza del piano P dal centro degli assi. Dalla Fig.4 si nota, quindi, che questa distanza è data dalla lunghezza del segmento che unisce i punti O e Q; dove O rappresenta l'origine del sistema di riferimento e Q il punto di intersezione tra l'asse perpendicolare al piano di proiezione ed il piano stesso.

 

PUNTO 4 - PUNTO D'INTERSEZIONE TRA DUE EDGES

 

In questa parte della teoria viene spiegato come l'algoritmo calcola il punto di intersezione tra i due edge incrociati per, poi, disegnare l'edge coperto spezzato nel punto di intersezione.

Per prima cosa è da chiarire il fatto che si lavorerà solo ed esclusivamente in 2D; cioè sulla rappresentazione bidimensionale ottenuta tramite le conversioni delle coordinate viste nel PUNTO4 precedentemente descritto.

Si prenda, ad esempio, la situazione della Fig.5 (A) dove si ha 4 punti a=(x'a,y'a) b=(x'b,y'b) c=(x'c,y'c) e d=(x'd,y'd) che formano i due edges ab e cd. Inoltre si conosce già che l'edge ab copre cd rispetto al punto di vista (in quanto determinato in precedenza).

L'algoritmo calcola le equazioni delle due rette (y=m1x+q1 e y=m2x+q2) passanti rispettivamente per i punti a,b e c,d (vedi Fig.5 (B) ) sfruttando le seguenti formule:

m1=-((y'b-y'a)/(x'a-x'b))

m2=-((y'd-y'c)/(x'c-x'd))

q1=-(((x'b*y'a)-(x'a*y'b))/(x'a-x'b))

q2=-(((x'd*y'c)-(x'c*y'd))/(x'c-x'd))

Una volta calcolate le due equazioni si svolge il sistema delle due rette per trovare il punto d'intersezione i=(x'i,y'i) (vedi Fig.6 (A) ).

x'i=((q2-q1)/(m1-m2))

y'i=(m2*xi+q2)

Trovato il punto d'intersezione e sapendo quale dei due edge deve essere spezzato, l'algoritmo che disegna le linee sullo schermo saprà ottenere il risultato di Fig.6 (B).

 

SECONDA PARTE

In questa sezione, come accennato all'inizio, verranno spiegati brevemente i passaggi che l'algoritmo compie per raggiungere il proprio scopo.

Per prima cosa l'algoritmo posiziona i cubi nello spazio aggiornando le loro posizioni.

II°

Controlla ogni edge con tutti gli altri che formano i due cubi per verificare la loro intersezione rispetto al punto di vista usando il metodo spiegato nel PUNTO1 della PRIMA PARTE. In questo modo l'algoritmo conosce tutti gli edges che si intersecano.

III°

Per ogni coppia di edge che si intersecano calcolati nel punto II° verifica quale dei due copre l'altro rispetto al punto di vista utilizzando il metodo spiegato nel PUNTO2 della PRIMA PARTE. Fatto questo l'algoritmo apprende le "priorità" tra gli edges che si intersecano.

IV°

Converte le coordinate 3D in 2D per ottenere una rappresentazione bidimensionale dei due cubi rispetto il punto di vista. La conversione avviene tramite i passaggi descritti nel PUNTO3 della PRIMA PARTE.

Otenuta la rappresentazione 2D dei due cubi, l'algoritmo riprende le coppie di edges che si intersecano trovate prima e cerca il punto d'intesezione tra i due come viene spiegato nel PUNTO4 della PRIMA PARTE. Una volta trovato il punto di intersezione disegna con un segmento spezzato (nel punto d'intersezione) gli edges coperti e da un segmento intero tutti gli altri.

 

Ma vediamo ora più in dettaglio le varie parti del programma:

La classe Ccubi contiene, come dice il nome stesso, al suo interno la descrizione dei due cubi visualizzati al centro dell'applet. Questa descrizione comprende l'insieme delle coordinate in 3D dei vertici separate in tre vettori x[],y[],z[]. Ogniuno dei vettori contiene 16 elementi: i primi 8 (da 0 a 7) sono per il primo cubo, mentre i restanti (da 8 a 15) vengono utilizzati per il secondo cubo. Oltre alle coordinate dei vertici si affianca anche la descrizione di come sono connessi tra loro per formare i vari edges. Queste informazioni sono contenute nella classe topologia definita all'interno di Ccubi. Infine negli array xx[] e yy[] vengono memorizzate le coordinate dei vertici dei 2 cubi nello spazio bidimensionale.

All'interno di Ccubi sono definiti alcuni metodi che consentono di gestire in maniera indipentdente i due oggetti:

ruota() e trasla() => permettono di applicare le omonime trasformazioni nello spazio indicando, tramite un apposito parametro, a quale dei due oggetti ci stiamo riferendo.

update() => aggiorna le trasformazioni e converte le coordinate dei vertici dal sistema tridimensionale a quello bidimensionale in relazione alla vista scelta (tramite la chiamata del metodo calc_vista()), in modo da preparare la scena per essere rappresentata sul monitor.

cambia vista () => si impostano le variabili d'ambiente che verranno utilizzate da calc_vista() in modo da rappresentare la composizione dei cubi da uno dei possibili punti di vista.

scambio(), preundo() e undo() => gestiscono la funzione UNDO che registra lo "stato" dei due cubi precedente all'ultima modifica fatta dall'utente in modo tale da annullare l'ultima manipolazione effettuata ai due cubi.

Passiamo ora alla descrizione della classe Cintersezione, la quale si occupa di risolvere il problema fondamentale del progetto d'esame.

Il metodo calc_int() confronterà gli uni con gli altri tutti i vari edges che compongono i due cubi (senza preoccuparsi se appartengono o meno allo stesso solido), utilizzando il sistema spiegato al PUNTO1 della PRIMA PARTE. In questo modo si isolano tutte le coppie che danno origine ad una intersezione e tramite il metodo add() si aggiorna la struttura dati, presente in Cintersezione, che ne deve tener traccia. Dopo di che invocando il metodo l_update() si passerà a determinare quale dei due edges che generano l'intersezione si sovrappone all'altro (applicando il metodo spiegato al PUNTO2 della PRIMA PARTE). Durante questa operazione si aggiorneranno le informazioni relative alla struttura della linea (contenute anch'esse nella classe topologia), indicando se il segmento sarà rappresentato intero o spezzato (in questo caso verranno inserite anche le coordinate del punto di intersezione ricavate dal sistema bidimensionale). Il metodo myLine(), della classe generale, si occuperà di rappresentare a video i vari edges utilizzando le informazioni ricavate, dal processo descritto qui sopra, per rappresentare a meno di qualche approssimazione le linee spezzate e quelle continue. All'inizio di ogni ciclo di disegno le informazioni riguardanti la rappresentazione delle linee vengono azzerate tramite l'uso del metodo clear() contenuto nella classe intersezione.

Per comprendere meglio la parte appena descritta si consiglia la visione del listato del programma.