Esame di “Elementi di Grafica Digitale”
Prof. Matjaz Hmeljak
Marco Bacer
12 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 intersection
http://www.realtimerendering.com/intersections.html
Collision detection – NeHe tutorial
http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30
Collision detection & Response – Peroxide tutorial
http://www.peroxide.dk/download/tutorials/tut10/pxdtut10.html
Collision detection – Videotutorialsrock tutorial
http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/t
ext.php
Simple Sphere-Sphere Collision Detection and Collision Response
http://wp.freya.no/simple-sphere-sphere-collision-detection-andcollision-response/comment-page-1#comment-6713
Collision detection – Wikipedia
http://en.wikipedia.org/wiki/Collision_detection
Bounding volume – Wikipedia
http://en.wikipedia.org/wiki/Bounding_volume
Octree – Wikipedia
http://en.wikipedia.org/wiki/Octree
How can I perform collision detection with OpenGL? – OpenGL FAQ
http://www.opengl.org/resources/faq/technical/miscellaneous.htm