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