Lokasi dan waktu tumbukan untuk titik bergerak dan segmen garis bergerak (Deteksi Tabrakan Berkelanjutan)

Question

Saya sedang mengerjakan sistem collider 2D yang memecah bentuk menjadi satu kemungkinan primitif: segmen yang tidak dapat ditembus yang ditentukan oleh dua titik. Untuk memberikan deteksi tabrakan untuk sistem ini, saya menggunakan pendekatan deteksi tabrakan statis yang menghitung jarak antara tepi satu segmen dan segmen yang saat ini ditangani (jarak titik / garis) sekali setiap bingkai. Jika jaraknya terlalu kecil, tabrakan dipicu selama frame tersebut. Ini berfungsi dengan baik tetapi memiliki masalah terowongan jika satu atau lebih benda menunjukkan kecepatan tinggi. Jadi saya mengutak-atik alternatif.

Sekarang saya ingin memperkenalkan deteksi tabrakan berkelanjutan (CCD) yang beroperasi pada titik dinamis / segmen dinamis. Masalah saya adalah: Saya tidak tahu persis bagaimana caranya. Saya tahu bagaimana melakukan tabrakan terus menerus antara dua titik bergerak, titik bergerak dan segmen statis tetapi tidak tahu bagaimana melakukan CCD antara titik bergerak (ditentukan oleh titik P) dan segmen bergerak (ditentukan oleh titik U dan V, keduanya dapat bergerak bebas sepenuhnya).

ilustrasi masalah

Saya telah melihat pertanyaan serupa diajukan di SO dan platform lain, tetapi tidak dengan persyaratan yang tepat berikut:

• baik titik maupun segmen sedang bergerak
• segmen dapat berputar dan meregang (karena U dan V bergerak bebas)
• waktu tabrakan dan titik tabrakan harus ditemukan secara akurat antara dua bingkai (CCD, tidak ada uji tabrakan statis)
• I prefer a mathematically perfect solutiuon, if possible (no iterative approximation algorithms, swept volumes)
• note: the swept line shape will not always be a convex polygon, because of the freedom of the U,V points (see image)
• note: testing for a collision with the swept volume test is inaccurate because a collision point with the polygon does not mean a collision point in the actual movement (see image, the point will have left the polygon once the actual segment has crossed the trajectory of the point)

So far I came up with the following approach, given:

• sP (P at start of frame),
• eP (P at end of frame),
• sU (U at start of frame),
• eU (U at end of frame),
• sV (V at start of frame),
• eV (V at end of frame)

Question: Will they collide? If yes, when and where?

To answer the question of "if", I found this paper to be useful: https://www.cs.ubc.ca/~rbridson/docs/brochu-siggraph2012-ccd.pdf (section 3.1) but I could not derive the answers to "when" and "where". I also found an alternative explanation of the problem here: http://15462.courses.cs.cmu.edu/fall2018/article/13 (3rd Question)

Solution:

Model temporal trajectory of each point during a frame as linear movement (line trajectory for 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 represents a location on the segment defined by U and V):

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

Model collision by equating point and segment equations:

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

Derive a function for the vector from point P to a point on the segment (see picture of F):

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

To now find a collision, one needs to find a and t, so that F(a, t) = (0, 0) and a,t in [0, 1]. This can be modeled as a root finding problem with 2 variables.

Insert the temporal trajectory equations into F(a, t):

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

Separate the temporal trajectory equations by dimension (x and 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)

Now we have two equations and two variables that we want to solve for (Fx, Fy and a, t respectively), so we should be able to use a solver to get a and t to only then check if they lie within [0, 1].. right?

When I plug this into Python sympy to solve:

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()

I get a solution that is HUGE in size and it takes sympy like 5 minutes to evaluate. I cannot be using such a big expression in my actual engine code and this solutions just does not seem right to me.

What I want to know is: Am I missing something here? I think this problem seems rather easy to understand but I cannot figure out a mathematically accurate way to find a time (t) and point (a) of impact solution for dynamic points / dynamic segments. Any help is greatly appreciated, even if someone tells me that this is not possible to do like that.

Answer 1

TLDR

I did read "...like 5 minutes to evaluate..."

No way too long, this is a real-time solution for many lines and points.

Sorry this is not a complete answer (I did not rationalize and simplify the equation) that will find the point of intercept, that I leave to you.

Also I can see several approaches to the solution as it revolves around a triangle (see image) that when flat is the solution. The approach bellow finds the point in time when the long side of the triangle is equal to the sum of the shorter two.

Solving for u (time)

This can be done as a simple quadratic with the coefficients derived from the 3 starting points, the vector over unit time of each point. Solving for u

The image below give more details.

• The point P is the start pos of point
• The points L1, L2 are the start points of line ends.
• The vector V1 is for the point, over unit time (along green line).
• The vectors V2,V3 are for the line ends over unit time.
• u is the unit time
• A is the point (blue), and B and C are the line end points (red)

There is (may) a point in time u where A is on the line B,C. At this point in time the length of the lines AB (as a) and AC (as c) sum to equal the length of line BC (as b) (orange line).

That means that when b - (a + c) == 0 the point is on the line. In the image the points are squared as this simplifies it a little. b² - (a² + c²) == 0

At the bottom of image is the equation (quadratic) in terms of u, P, L1, L2, V1, V2, V3.

That equation needs to be rearranged such that you get (???)u² + (???)u + (???) = 0

Sorry doing that manually is very tedious and very prone to mistakes. I don`t have the tools at hand to do that nor do I use python so the math lib you are using is unknown to me. However it should be able to help you find how to calculate the coefficients for (???)u² + (???)u + (???) = 0

Update

Ignore most of the above as I made a mistake. b - (a + c) == 0 is not the same as b² - (a² + c²) == 0. The first one is the one needed and that is a problem when dealing with radicals (Note that there could still be a solution using a + bi == sqrt(a^2 + b^2) where i is the imaginary number).

Another solution

So I explored the other options.

The simplest has a slight flaw. It will return the time of intercept. However that must be validated as it will also return the time for intercepts when it intercepts the line, rather than the line segment BC

Thus when a result is found you then test it by dividing the dot product of the found point and line segment with the square of the line segments length. See function isPointOnLine in test snippet.

To solve I use the fact that the cross product of the line BC and the vector from B to A will be 0 when the point is on the line.

Some renaming

Using the image above I renamed the variables so that it is easier for me to do all the fiddly bits.

/*
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 
*/

This gives the quadratic

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))

Rearranging we get

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

The coefficients are thus

 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

We can solve using the quadratic formula (see image top right).

Note that there could be two solutions. In the example I ignored the second solution. However as the first may not be on the line segment you need to keep the second solution if within the range 0 <= u <= 1 just in case the first fails. You also need to validate that result.

Testing

To avoid errors I had to test the solution

Below is a snippet that generates a random random pair of lines and then generate random lines until an intercept is found.

The functions of interest are

• movingLineVPoint which return the unit time of first intercept if any.
• isPointOnLine to validate the result.

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>