Post on 12-Jan-2016
description
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
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
• basati su BSP tree
• basati su BV gerarchici
• basati su OBB tree
• basati su k-DOP tree
Metodo approssimato con raggi
• 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 raggi-
superficie, se la distanza intersezione-origine_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
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
a
e
c
d
b
ab c
d e
ff pp
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 è insieme 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
p0
r
z y
xp0
p0
t
p0e
e
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
• possono esserci inaccuratezze€
tx =rnxnx2 + ny
2+ px
ty =rny
nx2 + ny
2+ py
basato su BSP tree - 7HitCheckBSP(N,v0,v1)return(RUE,FALSE)if(not isSolidCell(N)) return FALSEesle if(isSolideCell(N))
pimpact=v0return TRUE
hit=FALSEif(clipLineInside(N shift out v0,v1,w0, w1)
hit = HitCheckBSP(N.negativechild,w0,w1)
if (hit) v1=pimpact
endif(clipLineOutside(N shift in v0,v1,w0, w1)
hit = HitCheckBSP(N.positivechild,w0,w1)endreturn hit
basato su BV gerarchici
• indipendente dal tipo di volumi
• si costruisce la gerarchia di volumi
• si determina se c’e’ una coppia di triangoli che collide, termina appena se ne trova una (collision detection)
• la gerarchia è organizzata ad albero k-ario
basato su BV gerarchici - 2FindFirstHit(A,B)returns(TRUE,FALSE)if(isLeaf(A) and isLeaf(B))
for each triangle pair TA in A and TB in B
if(overlap(TA,TB) return TRUEelse if(isNotLeaf(A) and isNotLeaf(B))
if(Volume(A)>Volume(B))
for each child CA in A
FindFirstHit(CA,B)else
for each child CB in A
FindFirstHit(A,CB)else if(isleaf(A) and isNotLeaf(B))
for each child CB in B
FindFirstHit(CB,A)else
for each child CA in A
FindFirstHit(CA,B)return(FALSE)
basato su BV gerarchici - 3
complessità: t=nvcv+npcp+nucu
dove:• nv numero di test di overlap BV/BV• costo test di overlap BV/BV• np numero di test di overlap di primitive• cp costo test di overlap di primitive• nu numero di BV aggiornati per movimento oggetti• cu costo aggiornamento BVridurre costo di test overlap BV comporta BV più
grossolani e maggior costo cp
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 traforma 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