Collisioni
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
2
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
3
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
4
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
5
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
6
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
7
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 circonferenza

Il test ora è tra il centro della circonferenza e
le linee spostate
8
Rilevazione collisioni accurata
per molti oggetti
• Per ”simulazione” intendiamo la modellazione del
movimento degli oggetti
9
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
10
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.
11
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.
12
nodo interno
Commenti
• Termina quando trova la prima coppia di
triangoli che collidono
• Si può modificare per cercare tutte le
coppie che collidono e metterle in una lista
13
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 triangoli
n v : numero di test di sovrapposizione tra BV
Funzione di costo:
c v : costo del test di sovrapposizione tra BV
n p : numero di coppie di primitive testa per la sovrapposizione
c p : costo del test di sovrapposizione tra due primitive
n u : numero di BV aggiornati per ilmovimento del modello
14
c u : costo dell' aggiornamento di un BV
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
15
Sweep-and-prune
• Gli oggetti possono traslare e ruotare
• Si determina un cubo minimale AABB che
contiene un oggetto sotto tutte le possibili
rotazioni
• Si esegue il test di collisione tre volte
rispetto ai tre assi considerando un solo
asse per volta
• Ciascun cubo sull’asse è un intervallo da si
a ei, dove i è il numero del cubo
16
Sweep-and-prune
• Si ordinano tutti gli si e ei in una lista
• Si attraversa la lista da start a end
• Quando si incontra 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
17
Sweep-and-prune
• L’ordinamento costa: O(n*log n)
• Ma si sfruttia 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
• Complessità attesa: O(n)
18
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, 19
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
20
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 il sottospazio):
piano=n.x + d ---> n.x + d ±r
c
a
c
b
e
d
d
p
e
f
p
f
a
b
21
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
“stringe” l’espansione del volume)
• si valuta la distanza di p dal piano
22
basato su BSP tree - 4
• la sfera è una grossolana approssimazione, si
può usare un guscio convesso
• lo spostamento del piano d si sceglie nella
direzione 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 nel centro di
un modello, la posizione del punto viene
aggiornata secondo la direzione di spostamento:
p1=p0+w
23
basato su BSP tree - 5
• si può usare un cilindro per approssimare
l’ingombro di un personaggio, è più veloce
r
z
y
x
p0
p0
t
e
e
p0
p0
24
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 (soffitto o pavimento)
• si puo’ scegliere t=p0 altrimenti occorre
trovare un punto sul bordo del cerchio
25
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

26
basato su BSP tree - 7
HitCheckBSP(N,v0,v1)
#N radice del BSPtree, v0 v1
estremi segmento di spostamento
return(TRUE,FALSE)
if(not isSolidCell(N)) return FALSE
esle if(isSolideCell(N))
#è una foglia e siamo all’interno
pimpact=v0
return TRUE
hit=FALSE
if(clipLineInside(N shift out v0,v1,w0,w1)#parte del segmento di
spostamento è all’interno del volume dilatato e restituisce il
nuovo segmento w0,w1
hit = HitCheckBSP(N.right-child,w0,w1)
if (hit) v1=pimpact
end
if(clipLineOutside(N shift in v0,v1,w0, w1)
hit = HitCheckBSP(N.left-child,w0,w1)
end
return hit
27
basato su OBB tree
• si riduce nv numero test overlap dii volumi e np numero
testo overlap di 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)
28
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 si fa 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 per testare rispetto a C
29
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 per BVH
• esiste un software free che lo implementa:
RAPID (robust accurate polygon interference
detection)
http://www.cs.unc.edu/~geom/OBB/OBBT.html
30
K-DOP
• Politopi discreti orientati di ordine k
• Definito da k/2 normali unitarie (normalizzate) ni
cui sono associati due scalari dimin < dimax
• Ogni tripletta (ni, dimin,dimax) identifica una “lastra”
compresa tra i due piani identificati da:
ni .x  dimin  0
ni .x  dimax  0
• L’intersezione di tutte le lastre identifica il k-DOP

31
32
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 combinando le 6
normali iniziali
33
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
34
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
35