Esame di “Elementi di Grafica Digitale”

Prof. Matjaz Hmeljak

Marco Bacer12 gennaio 2009

Nelle simulazioni fisiche e nei videogiochi si parla di collision detection riferendosi a quegli algoritmi utilizzati per verificare le collisioni (come ad esempio l’intersezione tra due solidi)

La simulazione di ciò che avviene una volta rilevata la collisione si dice collision response

È indipendente dalla libreria grafica utilizzata

È un problema abbastanza complicato

Non c’è un unico approccio Dipende dal tipo di programma che si

vuole realizzare

Un fattore importante per la progettazione della collision detection è la determinazione di quanto spesso avvengono le collisioni e quali sono le collisioni che hanno più importanza

Nel caso di un videogame: sono rilevanti solo le collisioni con il protagonista o anche quelle tra ogni coppia di oggetti presente nel gioco?

Ci sono molte tecniche Solitamente tutte ruotano attorno al

“trucco” di raggruppare assieme oggetti vicini

È possibile ottenere esattamente ogni collisione basandosi sui poligoni che compongono il solido, ma solitamente si preferisce approssimare la forma degli oggetti con qualcosa di più semplice

Un’altra tecnica comune è quella di fare un check rapido di quali oggetti potrebbero collidere, prima di perdere tempo per fare un controllo più complicato

Ad esempio si può verificare se le sfere che contengono gli oggetti collidono, e solo se l’esito è positivo si procede a controlli più approfonditi

Una scatola con pareti trasparenti Ad ogni pressione della spacebar

vengono inserite nella scatola 10 palline

La forza di gravità fa cadere e rimbalzare le palline tra di loro e contro le pareti

Per trovare tutte le collisioni è possibile controllare per ogni paio di palline se la distanza è minore della somma dei raggi

Tuttavia una volta raggiunte le 300 palline ci ritroveremmo a dover controllare circa 50000 paia di palline per potenziali collisioni

Un approccio più efficace e quello di dividere il cubo a metà lungo ogni dimensione

A questo punto basta trovare in quale sottocubo(o cubi) si trova una pallina e controllare ogni paia di palline presenti in quel cubo

Se nella figura avremmo dovuto controllare ogni coppia di palline, ci saremmo trovati con 105 paia di palline su cui effettuare il controllo

Controllando invece le collisioni in ognuno dei quadrati più piccoli, troviamo soltanto 3 + 3 + 15 + 10 = 31 paia di palline

Nella versione 3D, il procedimento è analogo

Il cubo viene diviso in 8 cubi più piccoli Ogni cubo a sua volta può essere

ulteriormente diviso in 8 cubi più piccoli È possibile iterare questo procedimento

indefinitamente ma è necessario porre un limite per evitare coppie duplicate

La suddivisione dello spazio nella maniera descritta può essere rappresentata con una struttura ad albero chiamata octree (ogni cubo è un nodo, che, se viene diviso, avrà otto figli)

L’equivalente 2D dell’octree si chiama quadtree(quattro figli)

Utilizzando il quadtree per individuare le potenziali collisioni, vediamo che queste sono scese da 31 a 15

Suddividere troppo lo spazio porta le palline ad apparire in più cubi

Per evitare questo fenomeno è necessario porre un limite alla profondità dell’albero

Una volta trovate le coppie di palline che potrebbero collidere si controlla se effettivamente hanno colliso

Se collidono, le palline rimbalzano l’una contro l’altra

La fisica dell’urto è stata realizzate per essere il più reale possibile

Trovo il vettore che servirà come base x e lo normalizzo

Calcolo le componenti rispetto al vettore x (appena trovato) e y (perpendicolare a x) della velocità

Si esegue la stessa procedimento anche sull’altra sfera.

Applicando le leggi di Newton ottengo:

Segue il codice corrispondente a quanto appena illustrato

L’urto tra pallina e muro è di realizzazione molto più semplice

d è la velocità prima dell’urto d-2s è la velocità dopo l’urto Per trovare s, trovo la “direzione”

muro e poi calcolo il prodotto scalare tra velocità iniziale e direzione

Object-Object intersectionhttp://www.realtimerendering.com/intersections.html

Collision detection – NeHe tutorialhttp://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30

Collision detection & Response – Peroxide tutorialhttp://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html

Collision detection – Videotutorialsrock tutorialhttp://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php

Simple Sphere-Sphere Collision Detection and Collision Responsehttp://wp.freya.no/simple-sphere-sphere-collision-detection-and-collision-response/comment-page-1#comment-6713

Collision detection – Wikipediahttp://en.wikipedia.org/wiki/Collision_detection

Bounding volume – Wikipediahttp://en.wikipedia.org/wiki/Bounding_volume

Octree – Wikipediahttp://en.wikipedia.org/wiki/Octree

How can I perform collision detection with OpenGL? – OpenGL FAQhttp://www.opengl.org/resources/faq/technical/miscellaneous.htm