Collisioni
Corso di
Programmazione Grafica e Laboratorio
Daniele Marini
Campi applicazione
• praticamente tutto: giochi, CAD, realtà
virtuale
• complessità elevata dipendente dalla
complessità degli oggetti
• soluzioni approssimate e soluzioni esatte
• esigenze di real time
• Accresce il realismo di una simulazione
grafica
Fasi
• determinare se c’e’ collisione collision
detection - test sì/no
• determinare dove c’è collisione collision
determination
• decidere cosa fare quando c’è collisione
collision handling
Metodi principali
•
•
•
•
•
metodi approssimati e veloci (ray tracing)
basati su BSP tree
basati su BV gerarchici
basati su OBB tree
basati su k-DOP tree
Metodo approssimato (ray
tracing)
• es. un automobile che viaggia su una
superficie: determinare collisione ruote
– si dovrebbero analizzare tutte le ruote rispetto
alla superficie
– semplificare: rappresentiamo l’auto con un
insieme di raggi - un raggio per ogni ruota, si
testa l’intersezione dei raggi con la superficie
Metodo appross. con raggi - 2
• all’inizio il raggio è posto sul punto di contatto
ruota-superficie
• il raggio è diretto verticalmente
• a ogni passo si fa un test di intersezione raggiosuperficie, se la distanza intersezioneorigine_raggio è positiva non c’è contatto, se =0
contatto, se <0 penetrazione
• l’esito del test guida la risposta alla collisione
Metodo appross. con raggi - 3
• la superficie può essere composta da molti
triangoli
• per accelerare il calcolo dell’intersezione
con la superficie, essa può essere
organizzata gerarchicamente
• il calcolo della intersezione dipende dalle
primitive usate nel rappresentare la
superficie
Un’altra semplificazione
• A volte si può ridurre un problema 3D a un problema 2D
• Esempio: il labirinto



Un oggetto (giocatore) che si muove in
un labirinto può essere approssimato
da una circonferenza
Si testa la circonferenza rispetto alle
linee del labirinto
Meglio: si spostano le linee di un offset
pari al raggio della criconferenza

Il test ora è tra il centro della circonferenza e
le linee spostate
Rilevazione collisioni accurata
per molti oggetti
• Per ”simulazione” intendiamo la modellazione del
movimento degli oggetti
Collisione accurata tra oggetti
complessi
• Se è richiesto un risultato accurato si
ricorre alla gerarchia di BV
• Usa gerarchia di BV (BVH) separata per
ciascun oggetto
• Testare un BVH rispetto all’altro BVH per
cercare sovrapposizioni
• Se ci sono sovrapposizioni di triangoli si
calcola l’intersezione esatta (se
necessario)
Esempio di costruzione di una
gerarchia di volumi (BVH)
Suddividere
il piano
Ordina i
piani
rispetto ai
centroidi
Dei triangoli
=
+
Trova box
minimo
…and so on.
Pseudocodice per testare un
BVH rispetto a un altro BVH
Considera 4 casi:
1) Test tra due nodi foglia
2) Test tra due nodi interni
(non foglia)
3) Nodo interno vs.
nodo foglia
4) Nodo foglia vs.
nodo interno
Commenti
• Teermiona quando trova la prima coppia di
triangoli che collidono
• Si può modificare per cercare tutte le
coppie che collidono e metterle in una lista
Quali BV?
• Scelte possibili:
– AABB, OBB, k-DOP, sfere
• In generale BV più ”stretti” comportano ricerche più lente


BV più laschi alla fine comportano
più test tra coppie di traingoli
Funzione di costo:
Collisione tra molti oggetti semplificare!
• Immaginate centinaia di pietre che rotolano da un
monte ….
• La semplificazione viene spesso chiamata”First-Level
Collision Detection (CD)”
• Si preferisce fare una CD di primo livello per farne una
di secondo livello meno frequentemente
• Supponiamo ci sia elevata coerenza tra frame
successivi
– Ovvero gli oggetti sono vicini alla posizione precedente
– È una ipotesi ragionevole
Sweep-and-prune
[Ming Lin]
• Gli oggetti possono traslare e ruotare
• Si determina un cubo minimale che
contiene un oggetto sotto tutte le possibili
rotazioni
• Eseguire il testi di collisione tre volte
rispetto ai tre assi
• Consideriamo un solo asse per volta
• Ciascun cubo sull’asse è un intervallo da si
a ei, dove i è il numero del cubo
Sweep-and-prune
• Ordina tutti gli si e ei in una lista
• Attraversa la lista da start a end
• Quando incontri un s, marca il correspondiente
intervallo come attivo in una
active_interval_list
• Quando incontri un e cancella l’intervallo dalla
active_interval_list
• Tutti gli interrvalli nella active_interval_
list hanno sovrapposizioni
Sweep-and-prune
• L’ordinamento costa: O(n*log n)
• Ma sfruttiamo la coerenza tra frame!
• La lista quindi non dovrebbe cambiare
molto
• Si può perciò usare un ordinamento che
”riordina” un insieme già quasi in ordine,
come bubble-sort, o insertion-sort
• Compelssità attesa: O(n)
Sweep-and-prune algorithm
• Mantieni una variabile booleana per ciascuna coppia di
intervalli
• Scambia elementi quando cambia l’ordinamento
• Se tutte le variabile booleane per i tre assi sono true, 
sovrapposizione
basato su BSP tree
• la scena è organizzata in BSPtree
• l’oggetto può essere: sfera, cilindro o
poliedro convesso che contiene l’oggetto
(guscio convesso convex hull)
• è dinamico, se l’oggetto si sposta da p0 a
p1 determina dove avviene la collisione
lungo il segmento p0 - p1
• nei giochi l’oggetto è approssimato da
sfere o cilindri
basato su BSP tree - 2
• il test dovrebbe venire valutato rispetto ai piani
di separazione dei sottospazi
• si preferisce spostare il piano lungo la direzione
ortogonale (si allarga o stringe sottospazio):
piano=n.x + d ---> n.x + d +-r
c
a
c
b
e
d
d
p
f
f
a
b
e
p
basato su BSP tree - 3
• una delle regioni del sottospazio è
considerata piena (l’oggetto non può
entrare), è il sottospazio negativo
• se l’oggetto è nel sottospazio positivo
n.x + d ≥0 si sottrae r: n.x + d -r
• si valuta la distanza di p dal piano
basato su BSP tree - 4
• la sfera è una grossolana approssimazione, si
può usare guscio convesso
• lo spostamento del piano d si sceglie nella
direzione più ortogonale al piano:
-maxvi in S(n.(vi-p0))
• dove S è l’insieme dei vertici del guscio, il segno
meno indica che il punto deve stare all’esterno
• il punto p0 può essere nel piede o l’ombelico di
un personaggio, la posizione del punto viene
aggiornata secondo la direzione di spostamento:
p1=p0+w
basato su BSP tree - 5
• si puà usare un cilindro, è più veloce
r
z
y
x
p0
p0
t
e
e
p0
p0
basato su BSP tree - 5
•
•
•
•
si sposta il piano al punto t
si calcola e
si sposta il piano di e = |n.(t-p0)|
occorre calcolare t , se nz >0 la
componente z è quella di p0
• se nx=ny=0 il piano è parallelo ai cerchi del
cilindro se si puo’ prendere t=p0 altrimenti
si trova un punto sul bordo
basato su BSP tree - 6
tx 
ty 
rn x
n n
2
x
2
y
rn y
n n
2
x
2
y
 px
 py
• possono esserci inaccuratezze

basato su BSP tree - 7
HitCheckBSP(N,v0,v1)
return(RUE,FALSE)
if(not isSolidCell(N)) return FALSE
esle if(isSolideCell(N))
pimpact=v0
return TRUE
hit=FALSE
if(clipLineInside(N shift out v0,v1,w0, w1)
hit = HitCheckBSP(N.negativechild,w0,w1)
if (hit) v1=pimpact
end
if(clipLineOutside(N shift in v0,v1,w0, w1)
hit = HitCheckBSP(N.positivechild,w0,w1)
end
return hit
basato su OBB tree
• si riduce nv numero test overlap volumi e np numero
testo overlap primitive
• il costo cv per OBB è maggiore che per AABB
• durante il test si può orientare OBB agli assi riducendo il
costo
• nv e np sono minori per OBB rispetto AABB
• la creazione di un OBB richiede il calcolo del guscio
convesso O(nlogn), la profondità dell’albero costa
O(logn), il costo totale è O(nlog2n)
basato su OBB tree - 2
• due OBB A e B sono archiviati con le
matrici di rototraslazione MA ,M B rispetto al
genitore
• test di overlap di A e B nel sistema di
riferimento di A, A è un AABB, si trasforma
B nel riferimento di A:
TAB=M-1AMB
• se i volumi si intersecano occorre
discendere la gerarchia
basato su OBB tree - 3
• facciamo il test rispetto al sottovolume C nel suo
riferimento
• si trasforma B nel sistema di A con TAB poi si
trasforma B nel riferimento di C con MC-1
TCB= MC-1 TAB
• si procede ricorsivamente usando lo
pseudocodice già visto
• esiste un software free che lo implementa:
RAPID (robust accurate polygon interference
detection)
http://www.cs.unc.edu/~geom/OBB/OBBT.html
basato su k-DOP
• test di overlap dei volumi più veloce
• BV più accurato (minor numero di np)
• tutto ciò se k è piccolo, altrimenti degenera in
guscio convesso
• c’è un costo di aggiornamento dei volumi in
movimento cu e pu
• si è mostrato che k=18 dà un ottimo risultato
• la costruzione di 18-DOP può partire da un
AABB aggiungendo 12 piani con somme delle 6
normali iniziali
altri problemi
• dipendenza dal tempo: la collisione va
rilevata in relazione ai fps della
animazione
– occorre controllare il frame rate, es. 50 fps
richiedono 20 ms ciascuno, se 15 ms servono
al rendering ne restano 5ms per la collisione
– una tecnica è di attraversare l’albero non per
profondità ma per ampiezza
altri problemi - 2
• gestione della collisione: cosa fare
– es. rimbalzo di una pallina:
– si determina la collisione
– se viene rilevata:
• si calcola la nuova traiettoria e velocità secondo le
leggi della riflessione
• In generale è oggetto del modello fisico
scelto