Posizione e ora dell'impatto per un punto in movimento e un segmento di linea in movimento (Continuous Collision Detection)

Aug 19 2020

Sto lavorando su un sistema di collisione 2D che scompone le forme in una possibile primitiva: segmenti impenetrabili definiti da due punti. Per fornire il rilevamento delle collisioni per questo sistema, sto utilizzando un approccio di rilevamento delle collisioni statico che calcola la distanza tra il bordo di un segmento e il segmento attualmente gestito (distanza punto/linea) una volta ogni fotogramma. Se la distanza è troppo piccola, durante quel fotogramma viene attivata una collisione. Funziona bene ma presenta il noto problema del tunneling se uno o più corpi mostrano velocità elevate. Quindi sto armeggiando con le alternative.

Ora voglio introdurre il rilevamento continuo delle collisioni (CCD) che opera su punti dinamici/segmenti dinamici. Il mio problema è: non so esattamente come. So come eseguire una collisione continua tra due punti in movimento, un punto in movimento e un segmento statico, ma non come eseguire il CCD tra un punto in movimento (definito dal punto P) e un segmento in movimento (definito dai punti U e V, entrambi possono muoversi completamente liberamente).

illustrazione del problema

Ho visto domande simili poste su SO e altre piattaforme, ma non con questi requisiti esatti:

  • sia il punto che il segmento si muovono
  • il segmento può ruotare e allungarsi (poiché U e V si muovono liberamente)
  • il tempo di collisione e il punto di collisione devono essere trovati con precisione tra due fotogrammi (CCD, nessun test di collisione statico)
  • Preferisco una soluzione matematicamente perfetta, se possibile (nessun algoritmo di approssimazione iterativo, volumi spostati)
  • nota: la forma della linea spazzata non sarà sempre un poligono convesso, a causa della libertà dei punti U,V ( vedi immagine )
  • nota: il test per una collisione con il test del volume spostato è impreciso perché un punto di collisione con il poligono non significa un punto di collisione nel movimento effettivo ( vedi immagine , il punto avrà lasciato il poligono una volta che il segmento effettivo ha attraversato la traiettoria di il punto)

Finora ho trovato il seguente approccio, dato :

  • sP (P all'inizio del fotogramma),
  • eP (P alla fine del fotogramma),
  • sU (U all'inizio del frame),
  • eU (U alla fine del frame),
  • sV (V all'inizio del fotogramma),
  • eV (V alla fine del fotogramma)

Domanda : si scontreranno? Se sì, quando e dove?

Per rispondere alla domanda "se", ho trovato utile questo documento:https://www.cs.ubc.ca/~rbridson/docs/brochu-siggraph2012-ccd.pdf(sezione 3.1) ma non sono riuscito a ricavare le risposte a "quando" e "dove". Ho anche trovato una spiegazione alternativa del problema qui:http://15462.courses.cs.cmu.edu/fall2018/article/13(terza domanda)

Soluzione :

Modella la traiettoria temporale di ciascun punto durante un fotogramma come movimento lineare (traiettoria della linea per 0 <= t <= 1 )

  • P(t) = sP * (1 - t) + eP * t
  • U(t) = sU * (1 - t) + eU * t
  • V(t) = sV * (1 - t) + eV * t

( 0 <= a <= 1 rappresenta una posizione sul segmento definito da U e V):

  • UV(a, t) = U(t) * (1 - a) + V(t) * a

Modella la collisione equiparando le equazioni dei punti e dei segmenti:

  • P(t) = UV(a, t)
  • P(t) = U(t) * (1 - a) + V(t) * a

Derivare una funzione per il vettore dal punto P a un punto sul segmento ( vedi figura di F ):

  • F(a, t) = P(t) - (1 - a) * U(t) - a * V(t)

Per trovare ora una collisione, è necessario trovare a e t , in modo che F(a, t) = (0, 0) e a,t in [0, 1] . Questo può essere modellato come un problema di ricerca della radice con 2 variabili.

Inserisci le equazioni della traiettoria temporale in F(a, t) :

  • F(a, t) = (sP * (1 - t) + eP * t) - (1 - a) * (sU * (1 - t) + eU * t) - a * (sV * (1 - t ) + eV * t)

Separare le equazioni della traiettoria temporale per dimensione (x e y):

  • Fx(a, t) = (sP.x * (1 - t) + eP.x * t) - (1 - a) * (sU.x * (1 - t) + eU.x * t) - a * (sV.x * (1 - t) + eV.x * t)

  • Fy(a, t) = (sP.y * (1 - t) + eP.y * t) - (1 - a) * (sU.y * (1 - t) + eU.y * t) - a * (sV.y * (1 - t) + eV.y * t)

Ora abbiamo due equazioni e due variabili per le quali vogliamo risolvere ( rispettivamente Fx, Fy e a , t ), quindi dovremmo essere in grado di utilizzare un risolutore per ottenere solo a e t per controllare se si trovano all'interno di [0, 1].. giusto?

Quando lo inserisco in Python Sympy per risolvere:

from sympy import symbols, Eq, solve, nsolve

def main():

    sxP = symbols("sxP")
    syP = symbols("syP")
    exP = symbols("exP")
    eyP = symbols("eyP")

    sxU = symbols("sxU")
    syU = symbols("syU")
    exU = symbols("exU")
    eyU = symbols("eyU")

    sxV = symbols("sxV")
    syV = symbols("syV")
    exV = symbols("exV")
    eyV = symbols("eyV")

    a = symbols("a")
    t = symbols("t")

    eq1 = Eq((sxP * (1 - t) + exP * t) - (1 - a) * (sxU * (1 - t) + exU * t) - a * (sxV * (1 - t) + exV * t))
    eq2 = Eq((syP * (1 - t) + eyP * t) - (1 - a) * (syU * (1 - t) + eyU * t) - a * (syV * (1 - t) + eyV * t))

    sol = solve((eq1, eq2), (a, t), dict=True)

    print(sol)

if __name__ == "__main__":
    main()

Ottengo una soluzione di dimensioni ENORMI e ci vogliono 5 minuti per valutarla. Non posso usare un'espressione così grande nel mio vero codice motore e questa soluzione non mi sembra giusta.

Quello che voglio sapere è : mi sto perdendo qualcosa qui? Penso che questo problema sembri piuttosto facile da capire, ma non riesco a trovare un modo matematicamente accurato per trovare una soluzione di tempo ( t ) e punto ( a ) di impatto per punti dinamici / segmenti dinamici. Qualsiasi aiuto è molto apprezzato, anche se qualcuno mi dice che non è possibile fare così.

Risposte

1 Blindman67 Aug 20 2020 at 02:52

TLDR

Ho letto "... tipo 5 minuti per valutare..."

Non troppo a lungo, questa è una soluzione in tempo reale per molte linee e punti.

Scusa questa non è una risposta completa (non ho razionalizzato e semplificato l'equazione) che troverà il punto di intercettazione, che lascio a te.

Inoltre posso vedere diversi approcci alla soluzione poiché ruota attorno a un triangolo (vedi immagine) che quando è piatto è la soluzione. Il muggito di avvicinamento trova il punto nel tempo in cui il lato lungo del triangolo è uguale alla somma dei due più corti.

Risolvere per te (tempo)

Questo può essere fatto come un semplice quadratico con i coefficienti derivati ​​dai 3 punti di partenza, il vettore sull'unità di tempo di ogni punto. Risolvere per te

L'immagine sottostante fornisce maggiori dettagli.

  • Il punto P è la posizione iniziale del punto
  • I punti L1 , L2 sono i punti iniziali delle estremità della linea.
  • Il vettore V1 è per il punto, nell'unità di tempo (lungo la linea verde).
  • I vettori V2 , V3 sono per le estremità della linea nell'unità di tempo.
  • u è l'unità di tempo
  • A è il punto (blu) e B e C sono i punti finali della linea (rosso)

C'è (può) un punto nel tempo u dove A è sulla linea B , C . A questo punto la lunghezza delle linee AB (as a ) e AC (as c ) si somma per eguagliare la lunghezza della linea BC (as b ) (linea arancione).

Ciò significa che quando b - (a + c) == 0 il punto è sulla retta. Nell'immagine i punti sono quadrati perché questo lo semplifica un po'. b 2 - (a 2 + c 2 ) == 0

Nella parte inferiore dell'immagine è l'equazione (quadratica) in termini di u, P, L1, L2, V1, V2, V3 .

L'equazione deve essere riorganizzata in modo tale da ottenere (???)u 2 + (???)u + (???) = 0

Mi dispiace farlo manualmente è molto noioso e molto soggetto a errori. Non ho gli strumenti a portata di mano per farlo né uso Python, quindi la libreria matematica che stai usando mi è sconosciuta. Tuttavia dovrebbe essere in grado di aiutarti a trovare come calcolare i coefficienti per (???)u 2 + (???)u + (???) = 0

Aggiornare

Ignora la maggior parte di quanto sopra perché ho commesso un errore. b - (a + c) == 0 non è uguale a b 2 - (a 2 + c 2 ) == 0 . Il primo è quello necessario e questo è un problema quando si ha a che fare con i radicali (si noti che potrebbe esserci ancora una soluzione usando a + bi == sqrt(a^2 + b^2)where iè il numero immaginario).

Un'altra soluzione

Così ho esplorato le altre opzioni.

Il più semplice ha un leggero difetto. Restituirà l'ora dell'intercettazione. Tuttavia, ciò deve essere convalidato in quanto restituirà anche il tempo per le intercettazioni quando intercetta la linea, anziché il segmento di linea BC

Pertanto, quando viene trovato un risultato, lo si verifica dividendo il prodotto scalare del punto trovato e del segmento di linea per il quadrato della lunghezza del segmento di linea. Vedere la funzione isPointOnLinenello snippet di test.

Per risolvere utilizzo il fatto che il prodotto incrociato della retta BC e il vettore da B ad A sarà 0 quando il punto si trova sulla retta.

Qualche ridenominazione

Usando l'immagine sopra ho rinominato le variabili in modo che sia più facile per me fare tutte le parti complicate.

/*
point P is  {a,b}
point L1 is  {c,d}
point L2 is  {e,f}
vector V1 is {g,h}
vector V2 is {i,j}
vector V3 is {k,l}

Thus for points A,B,C over time u    */
Ax = (a+g*u)
Ay = (b+h*u)
Bx = (c+i*u)
By = (d+j*u)
Cx = (e+k*u)
Cy = (f+l*u)

/* Vectors BA and BC at u */
Vbax = ((a+g*u)-(c+i*u))
Vbay = ((b+h*u)-(d+j*u))
Vbcx = ((e+k*u)-(c+i*u))
Vbcy = ((f+l*u)-(d+j*u))

/*
   thus Vbax * Vbcy - Vbay * Vbcx == 0 at intercept 
*/

Questo dà il quadratico

0 = ((a+g*u)-(c+i*u)) * ((f+l*u)-(d+j*u)) - ((b+h*u)-(d+j*u)) * ((e+k*u)-(c+i*u))

Riorganizzando otteniamo

0 = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)*u* u -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))*u +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

I coefficienti sono così

 A = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)
 B = -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))
 C = (c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

Possiamo risolvere usando la formula quadratica (vedi immagine in alto a destra).

Si noti che potrebbero esserci due soluzioni. Nell'esempio ho ignorato la seconda soluzione. Tuttavia, poiché la prima potrebbe non essere sul segmento di linea, è necessario mantenere la seconda soluzione se all'interno dell'intervallo 0 <= u <= 1 nel caso in cui la prima fallisca. È inoltre necessario convalidare tale risultato.

Test

Per evitare errori ho dovuto testare la soluzione

Di seguito è riportato uno snippet che genera una coppia di righe casuali casuali e quindi genera righe casuali fino a quando non viene trovata un'intercettazione.

Le funzioni di interesse sono

  • movingLineVPointche restituiscono l'unità di tempo della prima intercettazione, se presente.
  • isPointOnLineper convalidare il risultato.

const ctx = canvas.getContext("2d");
canvas.addEventListener("click",test);
const W = 256, H = W, D = (W ** 2 * 2) ** 0.5;
canvas.width  = W; canvas.height = H;
const rand = (m, M) => Math.random() * (M - m) + m;
const Tests = 300;
var line1, line2, path, count = 0; 
setTimeout(test, 0);

// creating P point L line
const P = (x,y) => ({x,y,get arr() {return [this.x, this.y]}}); 
const L = (l1, l2) => ({l1,l2,vec: P(l2.x - l1.x, l2.y - l1.y), get arr() {return [this.l1, this.l2]}}); 
const randLine = () => L(P(rand(0, W), rand(0, H)), P(rand(0, W), rand(0, H)));
const isPointOnLine = (p, l) =>  {
    const x = p.x - l.l1.x;
    const y = p.y - l.l1.y;
    const u = (l.vec.x * x + l.vec.y * y) / (l.vec.x * l.vec.x + l.vec.y * l.vec.y);
    return u >= 0 && u <= 1;
}
// See answer illustration for names
// arguments in order Px,Py,L1x,l1y,l2x,l2y,V1x,V1y,V2x,V2y,V3x,V3y
function movingLineVPoint(a,b, c,d, e,f, g,h, i,j, k,l) {
    var A = -(i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j;
    var B = -d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j)
    var C = +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b

    // Find roots if any. Could be up to 2
    // Using the smallest root >= 0 and <= 1
    var u, D, u1, u2;
    // if A is tiny we can ignore
    if (Math.abs(A) < 1e-6) { 
        if (B !== 0) {
            u = -C / B;
            if (u < 0 || u > 1) { return }  // !!!!  no solution  !!!!
        } else { return }                   // !!!!  no solution  !!!!
    } else {
        B /= A;
        D = B * B - 4 * (C / A);
        if (D > 0) {
            D **= 0.5;
            u1 = 0.5 * (-B + D);
            u2 = 0.5 * (-B - D);
            if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1))  { return }  // !!!!  no solution  !!!!
            if (u1 < 0 || u1 > 1) { u = u2 }        // is first out of range
            else if (u2 < 0 || u2 > 1) { u = u1 }   // is second out of range
            else if (u1 < u2) { u = u1 }            // first is smallest
            else { u = u2 }
        } else if (D === 0) {
            u = 0.5 * -B;
            if (u < 0 || u > 1)  { return }  // !!!!  no solution  !!!!            
        } else { return }                    // !!!!  no solution  !!!! 
    }    
    return u;
}

function test() {
   if (count> 0) { return }
   line1 = randLine();
   line2 = randLine();
   count = Tests
   subTest();
}
function subTest() {
   path = randLine()
   ctx.clearRect(0,0,W,H);
   drawLines();
   const u = movingLineVPoint(
       path.l1.x, path.l1.y,
       line1.l1.x, line1.l1.y,
       line2.l1.x, line2.l1.y,
       path.vec.x, path.vec.y,
       line1.vec.x, line1.vec.y,
       line2.vec.x, line2.vec.y
   );
   
   if (u !== undefined) { // intercept found maybe
      pointAt = P(path.l1.x + path.vec.x * u, path.l1.y + path.vec.y * u);
      lineAt = L(
          P(line1.l1.x + line1.vec.x * u, line1.l1.y + line1.vec.y * u),
          P(line2.l1.x + line2.vec.x * u, line2.l1.y + line2.vec.y * u)
      );
      const isOn = isPointOnLine(pointAt, lineAt);
      if (isOn) {
          drawResult(pointAt, lineAt);
          count = 0;
          info.textContent = "Found at: u= " + u.toFixed(4) + ". Click for another";
          return;
      }
   }
   setTimeout((--count < 0 ? test : subTest), 18);
}   








function drawLine(line, col = "#000", lw = 1) {
    ctx.lineWidth = lw;
    ctx.strokeStyle = col;
    ctx.beginPath();
    ctx.lineTo(...line.l1.arr);
    ctx.lineTo(...line.l2.arr);
    ctx.stroke();
}
function markPoint(p, size = 3, col = "#000", lw = 1) {
    ctx.lineWidth = lw;
    ctx.strokeStyle = col;
    ctx.beginPath();
    ctx.arc(...p.arr, size, 0, Math.PI * 2);
    ctx.stroke();
}
function drawLines() {
   drawLine(line1);
   drawLine(line2);
   markPoint(line1.l1);
   markPoint(line2.l1);
   drawLine(path, "#0B0", 1);
   markPoint(path.l1, 2, "#0B0", 2);
}
function drawResult(pointAt, lineAt) {
   ctx.clearRect(0,0,W,H);
   drawLines();
   markPoint(lineAt.l1, 2, "red", 1.5);
   markPoint(lineAt.l2, 2, "red", 1.5);
   markPoint(pointAt, 2, "blue", 3);
   drawLine(lineAt, "#BA0", 2);
}
div {position: absolute; top: 10px; left: 12px}
canvas {border: 2px solid black}
<canvas id="canvas" width="1024" height="1024"></canvas>
    <div><span id="info">Click to start</span></div>