Rilevazione collisione continua tra due tetraedri mobili

Question

La mia domanda è abbastanza semplice. Ho due tetraedri, ognuno con una posizione corrente, una velocità lineare nello spazio, una velocità angolare e un centro di massa (centro di rotazione, in realtà).

Avendo questi dati, sto cercando di trovare un algoritmo (veloce) che determini precisamente (1) se si colliderebbero ad un certo punto nel tempo, e se è il caso, (2) dopo quanto tempo essi colliso e (3) il punto di collisione.

La maggior parte delle persone risolverebbe questo facendo il rilevamento di collisioni triangolo-triangolo, ma ciò sprecherebbe alcuni cicli CPU su operazioni ridondanti come controllare lo stesso bordo di un tetraedro contro lo stesso bordo dell'altro tetraedro al controllo di triangoli diversi . Questo significa solo che ottimizzerò un po 'le cose. Nulla di cui preoccuparsi.

Il problema è che non sono a conoscenza di alcun algoritmo triangolo-triangolo CCD (rilevamento collisione continua) che tenga conto dell'autorotazione.

Pertanto, mi devo algoritmo che verrebbe immesso i seguenti dati:

• dati di vertice per tre triangoli
• posizione e centro di rotazione/massa
• velocità lineare e la velocità angolare

E restituirebbe quanto segue:

• Se c'è una collisione
• Dopo quanto tempo la collisione si è verificata
• In quale punto dello spazio collisione avvenuta

Grazie in anticipo per il vostro aiuto.

Answer 1

Il rilevamento di collisione discreta comunemente utilizzato controlla i triangoli di ciascuna forma per la collisione, su punti discreti successivi nel tempo. Mentre è semplice da calcolare, potrebbe perdere un oggetto in rapido movimento che ne colpisce un altro, a causa della collisione tra i punti discreti nel tempo testato.

Il rilevamento continuo delle collisioni calcolerebbe innanzitutto i volumi tracciati da ciascun triangolo su un infinito di tempo. Per un triangolo che si muove a velocità costante e senza rotazione, questo volume potrebbe sembrare un prisma triangolare. Il CCD controllerebbe quindi la collisione tra i volumi e infine riconsegnerebbe se ea che ora i triangoli effettivamente condividessero lo stesso spazio.

Quando viene introdotta la velocità angolare, il volume tracciato da ciascun triangolo non sembra più un prisma. Potrebbe sembrare più simile alla forma di una vite, come una ciocca di DNA, o qualche altra forma non banale che potresti ottenere ruotando un triangolo attorno ad un asse arbitrario mentre lo trascini linearmente. Calcolare la forma di tale volume non è un'impresa facile.

Un approccio potrebbe prima calcolare la sfera che contiene un intero tetraedro quando ruota sul vettore di velocità angolare dato, se non si muoveva linearmente. Puoi calcolare un cerchio di rotazione per ogni vertice e ricavare la sfera da quello. Data una sfera, ora possiamo approssimare il volume del CCD estruso come un cilindro con il raggio della sfera e progredire lungo il vettore di velocità lineare. Trovare le collisioni di tali cilindri ci fornisce una prima approssimazione per un'area in cui cercare collisioni.

Un secondo approccio complementare potrebbe tentare di approssimare il volume effettivo tracciato da ciascun triangolo suddividendolo in piccoli sottogruppi quasi prismatici. Prenderebbe le posizioni del triangolo a due incrementi di tempo e aggiungerà superfici generate tracciando i vertici triangolari in quei momenti. È un'approssimazione perché collega una linea retta piuttosto che una curva reale. Per approssimazione, per evitare errori grossolani, la durata tra ciascun momento successivo deve essere sufficientemente breve in modo che il triangolo completi solo una piccola frazione di una rotazione. La durata può essere derivata dalla velocità angolare.

Il secondo approccio crea molti più poligoni! È possibile utilizzare il primo approccio per limitare il volume di ricerca e quindi utilizzare il secondo per ottenere una maggiore precisione.

Se stai risolvendo questo problema con un motore di gioco, potresti trovare la precisione di sopra sufficiente (vorrei ancora rabbrividire al costo computazionale). Se, invece, stai scrivendo un programma CAD o lavori alla tua tesi, potresti trovarla meno che soddisfacente. In quest'ultimo caso, potresti voler perfezionare il secondo approccio, forse con una migliore descrizione geometrica del volume occupato da un triangolo in movimento, quando limitato a un piccolo angolo di virata.

Answer 2

Ho passato molto tempo a pensare a problemi di geometria come questo, e sembra che soluzioni accurate, nonostante le loro semplici affermazioni, siano troppo complicate per essere pratiche, anche per casi 2D analoghi.

Ma intuitivamente vedo che tali soluzioni esistono quando si considerano velocità di traslazione lineare e velocità angolari lineari. Non pensare che troverai la risposta sul web o in qualsiasi libro perché ciò di cui stiamo parlando qui sono casi speciali, ma complessi. Una soluzione iterativa è probabilmente ciò che vuoi comunque - il resto del mondo è soddisfatto di questi, quindi perché non dovresti essere?

Answer 3

Se si stava tentando di entrare in collisione tetraedri non rotante, io suggerirei un prendendo la somma Minkowski e l'esecuzione di un controllo a raggi, ma che non funziona con rotazione.

Il meglio che riesco a ottenere è di eseguire una collisione con la sfera circolare usando le loro sfere di delimitazione per darvi una serie di tempi per verificare usando la bisezione o che cosa avete.

Answer 4

Scusa se non sono un esperto di matematica e non ho idea di quale sia la terminologia corretta. Spero che le mie pessime condizioni non nascondano troppo il mio significato.

Selezionare un punto temporale arbitrario.

Calcolare i limiti di ciascuna forma in due dimensioni perpendicolari all'asse su cui si sta muovendo per il timestep.

Per un passo temporale:. Se l'albero di questi limiti per due oggetti si intersecano, metà timestep e iniziare recurse in

Un tipo di ricerca binaria sempre soddisfacente precisione per scoprire il punto in cui un'intersezione finita si verifica.

Answer 5

Ecco uno schema di un approccio matematico a forma chiusa. Ogni elemento di questo sarà facile da esprimere individualmente, e la combinazione finale di questi sarebbe un'espressione di forma chiusa se si potrebbe mai scrivere:

1) L'equazione di movimento per ogni punto del tetraedro è abbastanza semplice nel proprio sistema di coordinate.Il movimento del centro di massa (CM) si muoverà semplicemente lungo una linea retta ei punti d'angolo ruoteranno attorno a un asse attraverso il CM, assumendo che sia l'asse z qui, quindi l'equazione per ogni punto d'angolo (parametrizzato da tempo, t) è p = v t + x + r (sin (wt + s) i + cos (wt + s) j), dove v è il vettore velocità di il centro di massa; r è il raggio della proiezione sul piano x-y; i, j e k sono i vettori di unità x, ye z; e x e s account per la posizione di partenza e la fase di rotazione at = 0.

2) Si noti che ogni oggetto ha il proprio sistema di coordinate per rappresentare facilmente il movimento, ma per confrontarli è necessario ruotare ciascuno in un sistema di coordinate comune, che può anche essere il sistema di coordinate dello schermo. (Si noti però che i diversi sistemi di coordinate sono fissi nello spazio e non viaggiano con il tetraedro.) Determinare quindi le matrici di rotazione e applicarle a ciascuna traiettoria (e cioè i punti e CM di ciascuno dei tetraedri).

3) Ora si dispone di un'equazione per ogni traiettoria all'interno dello stesso sistema di coordinate e occorre trovare i tempi delle intersezioni. Questo può essere trovato testando se uno qualsiasi dei segmenti di linea dai punti al CM di un tetraedro interseca uno qualsiasi dei triangoli di un altro. Questo ha anche un'espressione in forma chiusa, come si può trovare here.

La stratificazione di questi passaggi renderà le equazioni terribilmente brutte, ma non sarebbe difficile risolverle a livello computazionale (anche se con la rotazione del tetraedro è necessario essere certi di non rimanere bloccati al minimo locale). Un'altra opzione potrebbe essere quella di collegarlo a qualcosa come Mathematica per fare il cranking per te. (Non tutti i problemi hanno risposte facili).

Answer 6

Il problema può essere risolto in un problema di programmazione lineare e risolto esattamente.

Primo, supporti (p0, p1, p2, p3) sono i vertici al tempo t0, e (q0, q1, q2, q3) sono i vertici al tempo t1 per la prima tetraedro, poi a 4d spazio-tempo , riempiono il seguente 4d del volume

V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) } 

Qui la a0 ... a3 e b0 chiuso ... parametri b3 sono nell'intervallo [0,1] e somma 1:

a0+a1+a2+a3+b0+b1+b2+b3=1 

la seconda il tetraedro è similmente un poligono convesso (aggiungi un 'tutto per sopra per definire V' il volume 4d per quel tetraedro in movimento

Ora l'intersezione di due poligoni convessi è un poligono convesso. La prima volta che succede soddisfi il seguente problema di programmazione lineare:

Se (p0, p1, p2, p3) si sposta (q0, q1, q2, q3) e (p0' , p1' , p2' , p3 ') si sposta (q0', q1' , q2' , q3') poi la prima volta di intersezione avviene in punti/volte (r, t):

Minimizzare t0 * (a0 + a1 + a2 + a3) + t1 * (b0 + b1 + b2 + b3) soggetto a

0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4 
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1) 
    = a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1) 

L'ultimo è in realtà 4 equazioni, una per ogni dimensione di (r, t). Questo è un totale di 20 vincoli lineari dei 16 valori ak, bk, ak 'e bk'. Se c'è una soluzione, poi

(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1) 

è un punto di primo incrocio. Altrimenti non si intersecano.

Answer 7

Pensato in passato ma ha perso interesse ... Il modo migliore per risolverlo sarebbe quello di astrarre un oggetto. Crea un sistema di coordinate in cui il primo tetraedro è il centro (corde baricentriche o un sistema inclinato con un punto come origine) e astragga la rotazione facendo ruotare l'altro tetraedro attorno al centro. Questo dovrebbe darti equazioni parametriche se fai i tempi di rotazione. Aggiungi il movimento del centro di massa verso il primo e il suo giro e hai un insieme di equazioni per il movimento relativo al primo (distanza). Risolvere per t dove la distanza è uguale a zero.

Ovviamente con questo metodo più effetti aggiungete (come la resistenza al vento) il più disordinato che le equazioni ottengono è probabilmente ancora il più semplice (quasi ogni altra tecnica di collisione utilizza questo metodo di astrazione). Il problema più grande è che se si aggiungono effetti con feedback senza soluzione analitica, l'intera equazione diventa irrisolvibile.

Nota: se si segue il percorso di un sistema inclinato, fare attenzione alle eventuali trappole con distanza. Devi essere nell'ottante giusto! Questo metodo favorisce però vettori e quaternioni, mentre le corde baricentriche favoriscono le matrici. Quindi scegli quale sia il tuo sistema più efficace.