Come si verifica la collisione di due scatole di delimitazione orientate 2D orientate?

Question

Gli OBB hanno una posizione (x, y), una velocità (x, y) e un orientamento (Matrix). Con aggiornamenti periodici, gli OBB devono scontrarsi tra loro, restituendo la frazione della mossa ritenuta valida.

Ho esaminato il test Polygon su GPWiki - http://gpwiki.org/index.php/Polygon_Collision - ma non tiene conto degli oggetti in movimento o di un oggetto completamente all'interno di un OBB.

Il libro Real Time Collision Detection copre OBB 3D nel Capitolo 4: Volumi limite, ma il metodo per il test in 3 dimensioni è notevolmente più complesso rispetto al 2D.

Answer 1

Si dice 2d, ma si parla anche di 3d come più complesso. Per il rilevamento delle collisioni, in pratica si vuole verificare se due forme si intersecano tra loro. In 2D, con i bounding box, questi sono rectangles. Dovrai utilizzare un algoritmo per vedere se i rettangoli si intersecano e anche controllare se uno è completamente contenuto in un altro (3 test per l'algoritmo semplice). Per 3d, questi sono cubi. Stessa cosa. Guarda questo matrix di intersezioni oggetto-oggetto e trova quelle che vuoi. Controlla l'intersezione degli oggetti stessi e anche l'avvizzire è completamente contenuto nell'altro.

Questa procedura può estendersi non solo a scatole di delimitazione, ma anche a sfere di delimitazione o a oggetti reali stessi in scafi di confine convessi, poligoni o oggetti 3D completi. Il risultato finale è, mentre gli oggetti avanzano attraverso lo spazio e il tempo, se le loro superfici si scontrano o se si trovano l'una dentro l'altra. Nel caso in cui la tua granularità sia troppo grossolana e, nella situazione che stai modellando, dovrebbero collidere, ma finiscono per muoversi l'una dopo l'altra, dovresti eseguire un test di intersezione del raggio aggiuntivo per vedere se qualche punto centrale, ponderato in un l'oggetto interseca i limiti dell'altro.

Answer 2

Se si dispone di due riquadri di delimitazione (cioè rettangoli) con alcune orientazione arbitraria (che presumo significa qualche "rotazione"), allora farei il seguente:

• partire da una posizione iniziale (dove supponiamo che le caselle di delimitazione non si intersechino), traduci ciascuna casella in avanti in base alla sua velocità (tuttavia stai applicando movimenti nel tempo).
• Trova le coordinate degli angoli di ogni riquadro di delimitazione convertito. Queste 4 coordinate definiscono i punti finali dei 4 segmenti di linea che costituiscono i bordi del riquadro di delimitazione.
• Per il riquadro di delimitazione n. 1, testare un'intersezione tra ciascuno dei suoi segmenti di linea e i 4 segmenti di linea del riquadro di delimitazione n. È possibile farlo utilizzando equazioni standard per calcolare il punto di intersezione di due linee, come illustrato, ad esempio, here.
• Se è presente un'intersezione, calcolare la frazione di una mossa che ha avuto successo utilizzando le coordinate dei punti di intersezione e la traduzione nota applicata.
• Ripetere i passaggi precedenti per ciascun aggiornamento.

EDIT: A pseudocode approssimativa (che incorpora quello che è stato discusso nei commenti) apparirebbe come segue:

...test for intersections between the OBB edges... 
if any intersections are found{ 
    ...run code for when OBBs are partially overlapping... 
}else{ 
    P = line segment whose endpoints are the OBB centers; 
    ...test for intersections between P and OBB edges... 
    if P intersects edges of both OBBs{ 
     ...run code for when OBBs are not touching... 
    }else{ 
     ...run code for when one OBB is completely inside the other... 
    } 
} 

Answer 3

Per testare i rilevamenti di collisione tra 2 scatole di delimitazione orientati, userei la separazione assi teorema (SAT). Infatti SAT può essere utilizzato per il rilevamento di collisioni tra 2 forme convesse. Questa tecnica non è eccessivamente complessa da comprendere e ha una prestazione ragionevole. Il teorema può essere facilmente esteso a 3D.

EDIT:

L'algoritmo tenta di determinare è che è possibile montare un piano tra due oggetti. Se un tale piano esiste, allora l'oggetto è separato e non può intersecarsi.

Per determinare se gli oggetti sono separati, si tratta semplicemente di proiettare gli oggetti sul normal del piano e confrontare gli intervalli e verificare se si sovrappongono.

Quindi, c'è ovviamente un numero infinito di piani che possono stare tra due oggetti separati. Ma è stato dimostrato che devi solo testare una manciata di aerei.

Si può dimostrare che, per scatole, i piani di separazione da testare sono i piani con normale uguali agli assi delle due scatole. Quindi per 2 caselle, è necessario testare solo 4 piani di separazione in totale. Dei 4 piani, una volta trovato un piano di separazione che separa le caselle, allora sai che la scatola non può intersecare e tu non restituisci un flag di collisione.

Se i 4 aerei non possono separare le scatole, quindi la casella deve essere incrocio, e ci avete una collisione.

Answer 4

Un altro suggerimento (che copre il contenimento, e penso che è più conveniente):

Verificare se uno qualsiasi dei 4 vertici di 1 # sono all'interno # 2, quindi verificare se uno qualsiasi dei 4 vertici di 2 # sono dentro # 1. Ecco come suggerirei di fare questo:

Assumere che il vertice di # 1 che si sta verificando è v, ei 4 vertici di # 2 sono v1 ... v4. Rotazione inversa tutti e 5 i vertici in base all'orientamento del n. (per ruotare inverso un vettore u per una matrice di orientamento M, moltiplicare u per M-trasposto: M^T u, supponendo che nell'orientamento della convenzione funzioni per moltiplicazione a sinistra.) La seconda casella risultante, chiamala # 2 ' , ora è allineato sull'asse: è possibile verificare immediatamente se v 'è contenuto in esso.

Se hai trovato un vertice n. 1 all'interno di # 2 - stop, hai l'intersezione. Altrimenti, continua.

Vengono subito in mente alcune ottimizzazioni (forse è possibile archiviare le copie non ruotate dei vertici in ciascuna casella? Se le dimensioni sono corrette, è possibile confrontarle per eliminare immediatamente uno dei possibili contenimenti e salvare 3 potenziali test ?) ma a meno che non lo stiate applicando su migliaia di miliardi di coppie di scatole, questo test dovrebbe essere abbastanza economico.

Per quanto riguarda il movimento, è possibile ottenere in profondità come si vuole lì - guardate un po 'di collisione continuo', e vedere di persona. (Ricordo in particolare alcuni bei lavori di Stephane Redon). Credo con tutto il cuore che nessun gioco faccia parte di questa roba di fantasia: se ti stai davvero muovendo molto velocemente, puoi suddividere il tuo passo temporale ed eseguire controlli di collisione su ciascuna sub-iterazione di posizione/orientamento.

(modifica :) Ci fu un'altra discussione right here a tale proposito, con belle riferimenti.

Answer 5

Probabilmente è opportuno implementare una quadtree (vedi wikipedia) per tenere traccia di tutti gli oggetti sul piano. Sfortunatamente non ne ho mai implementato uno per il rilevamento delle collisioni, ma sembra che altri people siano stati in grado di creare scenari simili ai vostri utilizzando quad alberi.