Местоположение и время удара для движущейся точки и движущегося отрезка линии (постоянное обнаружение столкновений)

Question

Я работаю над системой 2D-коллайдера, которая разбивает формы на один возможный примитив: непроницаемые сегменты, определяемые двумя точками. Чтобы обеспечить обнаружение столкновений для этой системы, я использую подход статического обнаружения столкновений, который вычисляет расстояние между краем одного сегмента и текущим обрабатываемым сегментом (расстояние точки / линии) один раз в каждом кадре. Если расстояние слишком мало, во время этого кадра происходит столкновение. Это прекрасно работает, но имеет известную проблему туннелирования, если одно или несколько тел демонстрируют высокие скорости. Так что я пытаюсь найти альтернативы.

Теперь я хочу представить непрерывное обнаружение столкновений (CCD), которое работает с динамическими точками / динамическими сегментами. Моя проблема: я точно не знаю, как это сделать. Я знаю, как сделать непрерывное столкновение между двумя движущимися точками, движущейся точкой и статическим сегментом, но не как сделать CCD между движущейся точкой (определяемой точкой P) и движущимся сегментом (определенным точками U и V, оба могут двигаться совершенно свободно).

иллюстрация проблемы

Я видел похожие вопросы на SO и других платформах, но не с этими точными требованиями:

• и точка, и сегмент движутся
• сегмент может вращаться и растягиваться (потому что U и V перемещаются свободно)
• время столкновения и точка столкновения должны быть точно найдены между двумя кадрами (CCD, без статического теста столкновения)
• Я предпочитаю математически идеальное решение, если возможно (без алгоритмов итеративного приближения, развернутых объемов)
• Примечание: форма скользящей линии не всегда будет выпуклым многоугольником из-за свободы точек U, V ( см. изображение )
• примечание: проверка столкновения с тестом развернутого объема неточна, потому что точка столкновения с многоугольником не означает точку столкновения при фактическом движении ( см. изображение , точка покинет многоугольник, как только фактический сегмент пересечет траекторию движения). точка)

Пока что я придумал следующий подход, учитывая :

• sP (P в начале кадра),
• eP (P в конце кадра),
• sU (U в начале кадра),
• eU (U в конце кадра),
• sV (V в начале кадра),
• эВ (В в конце кадра)

Вопрос : они столкнутся? Если да, то когда и где?

Чтобы ответить на вопрос «если», я нашел эту статью полезной: https://www.cs.ubc.ca/~rbridson/docs/brochu-siggraph2012-ccd.pdf(раздел 3.1), но я не мог получить ответы на вопросы «когда» и «где». Я также нашел здесь альтернативное объяснение проблемы:http://15462.courses.cs.cmu.edu/fall2018/article/13 (3-й вопрос)

Решение :

Моделируйте временную траекторию каждой точки во время кадра как линейное движение (линейная траектория для 0 <= t <= 1 )

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

( 0 <= a <= 1 представляет местоположение на сегменте, определяемом U и V):

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

Модель столкновения путем приравнивания точечных и сегментных уравнений:

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

Выведите функцию для вектора из точки P в точку на отрезке ( см. Рисунок F ):

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

Теперь, чтобы найти столкновение, нужно найти a и t , так что F (a, t) = (0, 0) и a, t в [0, 1] . Это можно смоделировать как проблему поиска корня с двумя переменными.

Подставим уравнения временной траектории в F (a, t) :

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

Разделите уравнения временной траектории по размерности (x и 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)

Теперь у нас есть два уравнения и две переменные, которые мы хотим решить для ( Fx, Fy и a , t соответственно), поэтому мы должны иметь возможность использовать решатель, чтобы получить a и t только затем, чтобы проверить, лежат ли они в пределах [0, 1] .. верно?

Когда я подключаю это к Python sympy, чтобы решить:

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

Я получаю ОГРОМНОЕ по размеру решение, на оценку которого у sympy уходит около 5 минут. Я не могу использовать такое большое выражение в моем реальном коде движка, и эти решения мне просто не подходят.

Что я хочу знать : я что-то упустил? Я думаю, что эта проблема кажется довольно простой для понимания, но я не могу найти математически точный способ найти решение для времени ( t ) и точки ( a ) удара для динамических точек / динамических сегментов. Любая помощь приветствуется, даже если кто-то скажет мне, что это невозможно.

Answer 1

TL; DR

Я прочитал «... около 5 минут на оценку ...»

Не слишком долго, это решение в реальном времени для многих линий и точек.

Извините, это не полный ответ (я не рационализировал и не упрощал уравнение), который найдет точку пересечения, которую я оставляю вам.

Также я вижу несколько подходов к решению, так как оно вращается вокруг треугольника (см. Изображение), когда плоское решение является решением. Приведенный ниже подход находит момент времени, когда длинная сторона треугольника равна сумме двух более коротких.

Решение для u (время)

Это можно сделать как простую квадратичную с коэффициентами, полученными из 3 начальных точек, вектора за единицу времени для каждой точки. Решение для тебя

Изображение ниже дает более подробную информацию.

• Точка P - это начальная позиция точки
• Точки L1 , L2 - начальные точки концов линии.
• Вектор V1 соответствует точке в единицу времени (по зеленой линии).
• Векторы V2 , V3 соответствуют концам линии за единицу времени.
• u - единица времени
• A - точка (синяя), а B и C - конечные точки линии (красные)

Существует (может) точка во времени ¯u , где находится на линии B , C . В этот момент сумма длин линий AB (как a ) и AC (как c ) равна длине линии BC (как b ) (оранжевая линия).

Это означает, что когда b - (a + c) == 0, точка находится на линии. На изображении точки возведены в квадрат, что немного упрощает его. б ² - (а ² + с ² ) == 0

Внизу изображения находится уравнение (квадратичное) относительно u, P, L1, L2, V1, V2, V3 .

Это уравнение необходимо перестроить так, чтобы получилось (???) u ² + (???) u + (???) = 0

Извините, делать это вручную очень утомительно и очень подвержено ошибкам. У меня нет инструментов для этого, и я не использую python, поэтому математическая библиотека, которую вы используете, мне неизвестна. Однако он должен помочь вам найти, как вычислить коэффициенты для (???) u ² + (???) u + (???) = 0

Обновлять

Игнорируйте большую часть вышеперечисленного, так как я допустил ошибку. b - (a + c) == 0 не то же самое, что b ² - (a ² + c ² ) == 0 . Первый - тот, который нужен, и это проблема при работе с радикалами (обратите внимание, что все еще может быть решение, использующее a + bi == sqrt(a^2 + b^2)где i- мнимое число).

Другое решение

Поэтому я изучил другие варианты.

У самого простого есть небольшой недостаток. Вернет время перехвата. Однако это должно быть подтверждено, так как оно также будет возвращать время для перехвата, когда оно перехватывает линию, а не отрезок линии BC.

Таким образом, когда результат найден, вы затем проверяете его, разделив скалярное произведение найденной точки и отрезка линии на квадрат длины отрезка линии. См. Функцию isPointOnLineв тестовом фрагменте.

Для решения я использую тот факт, что перекрестное произведение прямой BC и вектора от B до A будет равно 0, когда точка находится на прямой.

Некоторое переименование

Используя изображение выше, я переименовал переменные, чтобы мне было легче выполнять все неудобные биты.

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

Это дает квадратичную

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

Переставляя, получаем

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

Таким образом, коэффициенты равны

 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

Мы можем решить, используя формулу корней квадратного уравнения (см. Изображение вверху справа).

Обратите внимание, что может быть два решения. В этом примере я проигнорировал второе решение. Однако, поскольку первое решение может не находиться на отрезке линии, вам необходимо сохранить второе решение, если оно находится в диапазоне 0 <= u <= 1, на случай, если первое выйдет из строя. Вам также необходимо подтвердить этот результат.

Тестирование

Чтобы избежать ошибок, пришлось протестировать решение

Ниже приведен фрагмент, который генерирует случайную случайную пару строк, а затем генерирует случайные строки, пока не будет найден перехват.

Интересующие функции:

• movingLineVPoint которые возвращают единицу времени первого перехвата, если таковая имеется.
• isPointOnLine для подтверждения результата.

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>