Il problema delle collisioni nel campo della simulazione fisica e suoi derivati è sempre stato un problema sia di difficile soluzione sia di enorme interesse.

La sua difficolta stà nella sua appartenenza all dominio di esplorazione esponenziale delle soluzioni:per ogni faccia si deve fare un confronto con tutte le altre faccie presenti nella scena portando a tempi computazionali troppo alti per applicazioni real time; questo ha portato a sviluppo di metodi di approssimazione per applicazioni con necessità real time nella simulazione di collisioni,per esempio videogiochi o robotica.

I primi metodi per la collision detection si sono basati sulla tecnica bounding box: il metodo disegna un parallelepipedo attorno al corpo e basa la sua decisione per la collisione in base all'intersezione o meno di queste costruzioni.La velocità è guadagnata a discapito della precisione,ma in molti campi questa caratteristica è meno importante rispetto alla generazione di frame.

Per corpi molto complessi e facilmente suddivisibili in zone distinte la tecnica bounding box viene applicata ad ogni sottocorpo in modo indipendente l'una dall'altra, quindi di avrà un accrescimento della precisione a scapito solo di un fattore costante sui tempi di computazione.

Man mano che nuovi metodi maggiormente precisi venivano sviluppati metodi precedenti, solitamente piu veloci, venivano chiamati per ordine di precisione maggiore fin quando uno di questi non dava un esito negativo.Questo metodo di procede può velocizarre la computazione applicando metodi sempre piu precisi solo quando ce ne sarà bisogno.

Altra caratteristica sfruttata in alcuni campi e l'indeformabilità dei corpi, questo comporta la possibilità di computare caratteristiche degli oggetti presenti nello spazio a priori,non gravando alla computazione della scena.Un esempio in questo senso e la tecnica del bsp(binary space partition) tree,che spezza la scena in regioni di spazio e la computazione di collisioni(ma non solo) viene effettuata solo se due oggetti appartengono alla stesso spazio.

Una tecnica analoga può essere applicata anche al singolo oggetto non solo all'intero spazio: ogni corpo viene strutturato come un albero in modo che la ricerca di una qualsiasi entità geometrica utile per la collision detection sia in una struttura ottimizzata per la ricerca rispetto alla posizione della stessa all'interno del corpo.

Esistono altre tecniche per la collision detection che non si basano sull intersezione di corpi ma sul calcolo delle distanze minime tra corpi.Queste tecniche sono usate soprattutto se si necessità di una precisione maggiore.

Il progetto e stato sviluppato basandosi sulla struttura di un singolo corpo.Questa e stato pensato come un grafo, quindi un insieme di vertici e un insieme di relazioni tra di essi,ovvero la loro connessione,questo permette una creazione incrementale dell'oggetto e la possibilità di inserimento di funzioni solitimante usate sui grafi.I corpi possono essere inoltre creati in base a certi parametri di input per la propria geometria locale, per esempio è possibile specificare la lunghezza del lato al cubo oppure il numero di meridiani e paralleli della sfera poligonale.A questa struttura sono state aggiunte informazioni riguardanti il corpo come il suo vettore di rotazione,il suo colore e via dicendo.

Ogni oggetto ha un suo sistema di coordinate, solitamente centrato nel baricentro del corpo per operazioni locali, mentre per operazioni tra corpi esite un sistema di coordinate mondo e la transformazione avviene tramite i vettori di rotazione traslazione e scalatura del corpo.

Questa serie di transformazioni vengono racchiuse in una matrice di transformazione per portare ogni vertice dell'oggetto espresso inizialmente in coordinate oggetto in coordinate mondo concatenando le matrici di scalatura, rotazione e traslazione in questo ordine.

Esiste una seconda matrice che viene applicata ad ogni singolo vertice per la sua proiezione, parallela o prospettica, per ottenere la visualizzazzione dell'oggetto nelle aree di visualizzazione opportune.

Le due matrici risultanti vengono moltiplicate per ottenere la matrice finale di visualizzazione completa dell'oggetto,che avrà vita fin quando tutti i vertici del suddetto verranno processati,alchè si ricomputera la prima matrice e la si moltiplicherà per la seconda matrice rimasta invariata fin quando non si dovra rendere la scena su un altra finestra.

Tutti gli oggetti presenti nel mondo vengono mantenuti tramite un vettore e processati,tramite la matrice detta sopra, uno per uno dalla classe engine che restituira un oggetto draw bidimensionale su cui si faranno le operazioni di selezione,che avviene calcolando il perimetro esterno dell'oggetto e stabilendo se il punto di click sia o meno all interno di questo perimetro.

L'interfaccia invece si occupa di catturare gli eventi del mouse click e drag e quelli della tastiera alt e shift e li organizza in base alla sorgente dell'evento e al tool selezionato,una volta catturata l'azione viene chiamata una funzione dell'engine atta a soddisfare la richiesta,non esiste nessuna intersezione logica della parte engine (kernel o core dell'applicazione) e la sua interfaccia grafica tranne per la particolare classe drawcanvas che si occupa anche di fare alcune operazioni sulle immagini a video in bidimensionale come trovare il perimetro.

Esiste una seconda classe che mette a disposizione delle funzioni alla gui ed è la classe collisionengine che si occupa di trovare le collisioni all'interno della geometria mondo e creare nuovi oggetti temporanei atti alla visualizzazzione della collisione.

Esiste quindi la tipica separazione gui da core/kernel in cui le classi che si interfacciano l'una verso l'altra sono rispettivamente i vari gestori degli eventi e le 4 canvas(input e output rispettivamente), e le classi engine e collisionengine.

Purtroppo per una mancanza sia di tempo non e stata un altra classe che poteva essere una classe del tipo rasterengine atta a operare sulle immagini bidimensionali a video,con possibilità di implementazione di zbuffer antialias o alcuni modelli di illuminazione per il rendering.

Tutti gli oggetti istanziabili sono sottoclassi della classe Draw che mette a disposizione una serie di chiamate standard, per esempio per l'aggiunta di un vertice o di un collegamento tra vertici e via dicendo, ed ognuna di queste sottoclassi effettua la costruzione del corpo in un proprio sistema di riferimento: tutti i vertici sono costruiti attorno ad un punto fisso,di solito il baricentro.

Alcune sottoclassi mettono a disposizione alcune informazioni addizzionali per rendere consistente l'informazione del corpo,per esempio la classe DrawBerzie aggiunge le informazioni sul grado in u e v della superficie di Bezier che si andrà a creare e la classe DrawRationalBerzie aggiunge la matrice dei pesi per ogni superficie razionale di Bezier.

La pipeline di transformazione mondo-visualizzazione funziona in questo modo: viene prima creata la matrice di transformazione per la visualizzazzione sull'area che fa questa richiesta: di solito un prodotto di 2 matrici,una per la transformazione dei vertici in base alla prospettiva ed una per il ridimensionamento all'interno della finestra di visualizzazzione,successivamente per ogni oggetto viene creata una matrice che serve a posizionare correttamente il corpo nello spazio secondo i suoi valori rotazione scalatura e traslatura,attraverso il prodotto di queste tre matrici in questo ordine, scalatura, rotazione e traslazione.

La martice ottenuta viene infine moltiplicata per la matrice propria della finestra di visualizzazione calcolata precedentemente ed applicata ad ogni vertice del corpo.Ogni punto viene reso omogeneo prima di essere effetivamente disegnato.

La matrice di rotazione viene composta in questo modo: si calcola prima la matrice di rotazione attorno all'asse x,se questo valore e diverso da 0,poi quella attorno ad y,poi quella attorno a z,ed infine moltiplicate nel ordine di creazione.

Le superficii di Bezier vengono costruite in fase di visualizzazione basandosi sul poliedro di controllo trasformato in base al procedimento sopra esposto.

Per la parte delle collisioni vieni invece usato un altro motore implementato nella classe CollisionEngine e mette a disposizione 3 metodi per il confronto dei corpi:by Sphere,by bounding box, by analisys.Questi metodi vengono chiamati su ogni coppia di oggetti presenti nella scena.

Il primo metodo semplicemente controlla che sfere,una per ogni corpo centrata nel baricento del corpo e aventei come raggio la massima distanza tra il baricentro e vertici del corpo,abbiano o meno intersezioni a 2 a 2.Una volta controllata la possibile intersezione di 2 sfere si procede, in caso che il test abbia dato esito positivo, a costruire il corpo per rendere a video la zona d'intersezione come unione di due calotte.

Il secondo metodo costruisce parallelogrammi attorno ai vari corpi e calcola l'intersezione tra questi, costruendo anche in questo caso l'opportuna intersezione.

L'ultimo metodo non e stato completamento sviluppato, ed non è completamente corretto. Il metodo esegue prima un confornto basato sulle sfere,in caso di test positivo costruisce per entrambi i corpi il loro involucro convesso tramite l'algoritmo quickhull,una volta costruito controlla che esistano vertici dell'involucro che siano interni all'altro, se non esistono non riporta nessuna intersezione,nel caso invece ce ne siano,inzia a costruire due insiemi di punti per ogni involucro,un insieme di vertici interni e un insieme di vertici esterni con un vicino interno rispettivamente al secondo involucro,e cerca le intersezioni tra piani del primo involucro e segmenti generati da vertici interni ed esternidel secondo e viceversa.Una volta trovati i punti costruisce il corpo convesso di questi.

Purtroppo questo metodo ha 2 problemi: uno di approssimazioni numerica in qualche caso di vicinanza allo zero,e un secondo problema proprio concettuale:se un corpo non ha nessun vertice all'interno dell'altro la costruzione è incompleta in quanto manca l'apporto del secondo corpo,inoltre il fatto che non abbia vertici inclusi nella possibile intersezione non vuole dire che questa non esista:potrebbero intersecarsi solo le superficii delle faccie.

Purtoppo per mancanza di tempo, non ho potuto completare questo punto in modo adeguato.

la zona dei menu mette a disposizione la lista di comandi di creazioni di oggetti in modo parametrico,la lista per la modifica delle propietà di un singolo oggetto come la sua rotazione, la sua scalatura o il suo colore, una lista per modificare il metodo di selezione dell'oggetto, una lista di opzioni generali.

la zona di visualizzazione e divisa in 4 finestre che,partendo dall'alto a sinistra sono vista in pianta,vista prospettica,vista laterare,vista frontale. Nella vista prospettica le azioni possibili sono quelle di selezione tramite click, sia dell'oggetto sia di un suo vertice/peso, e quelle di modifica della telecamera per quanto riguarda zoom (drag del mouse con shift premuto) e rotazione attorno all'origine mondo(drag del mouse con alt premuto).

Nelle restanti tre finestre,oltre alla modifica dello zoom(sempre col drag del mouse con shift premuto) ed alla selezione,si può modificare anche le propietà dell'oggetto selezionato tramite il drag del mouse e a seconda del tool scelto(rotazione translazione o scalatura) nella parte dei tools(vedere seguito).

La zona dei tools si divede maggiormente in 2 zone: la zona alta permette di selezionare il tool da usare (traslazione,rotazione o scalatura) che modificherà il comportamento del drag del mouse nelle zone dell'area di visualizzazione che supportano tale possibilità (tutte tranne la prospettica).

La seconda parte invece influeza il comportamento del click del mouse nell'area di visualizzazione rendendo disponibili selezioni per oggetto,per vertice o per peso.

Questa zona permette di creare oggetti che verranno piazzati nell'origine del mondo e senza possibilità di parametrizzarli(se si desidera farlo si usi il comando corripondente presente nel menù),di cancellare l'oggetto selezionato,o di testare le collisioni coi metodi descritti nella sezione “descrizione geometrica”.

Lo sviluppo del progetto è stato molto pesante sia per la dimensione e difficoltà del'argomento, sia per un non chiara fase iniziale di concept,sia per la mancanza di una serie di chiamate grafiche usabili (java3D).

Il problema affrontato e molto complesso per le sue richieste di real time nella grafica odierna, e questo e solo una principio di approccio utilizzato soprattutto nei videogiochi, mentre un altra tecnica sarà esplorata da me nella tesi basata sul computo delle distanze tra le faccie.

Per chi approccia per la prima volta lo sviluppo di programmi per la grafica consiglio lo sviluppo di una propria libreria geometrica per le normali operazioni nel piano e eventualmente nello spazio,la scrittura a livello semantico (interfaccie delle classi e prototipi) dei vari moduli che opereranno nella versione finale dell'applicativo.In alcuni casi possono sorgere problemi di underflow per calcoli vicini allo zero la cui propagazione può essere molto nociva.