Разрешение столкновений круглых кругов

Question

Я пишу программное обеспечение, которое расширяет Circle-Rectangle collision detection (intersection), чтобы включить ответы на столкновение. Круг и край прямоугольника довольно прямолинейны. Но круговой круг меня озадачил.

Например, пусть два круга сталкиваются, один красный и один зеленый, в моделировании дискретных событий. Мы могли бы иметь следующую ситуацию:

Сразу после того, как они сталкиваются, мы могли бы иметь:

Здесь RIP и GIP были места окружностей на предыдущем такте. При текущем такте отслеживания столкновение обнаруживается при RDP и ВВП. Тем не менее, столкновение произошло между часами, когда два круга были на RCP и GCP. При тактировании часов красный круг перемещается в направлении RVy вниз и RVx вправо; зеленый круг движется GVy вниз и GVx влево. RVy не равно GVy; и RVx не равняется GVx.

столкновение происходит тогда, когда расстояние между круговыми центрами меньше или равно сумме радиусов окружностей, то есть, на предыдущем рисунке, д < = (Rr + Гр). При столкновении, где d < (Rr + Gr), мы должны поместить DP обратно в CP, прежде чем настраивать компоненты скорости кругов. В случае d == (Rr + Gr) перепозиционирование не требуется, поскольку DP находятся в CP.

В этом и заключается проблема: как мне сделать переход обратно к CP. Некоторые авторы предположили, что необходимо использовать половину проникновения, заданного p на следующем рисунке.

Для меня это просто неправильно. Он предполагает, что векторы скорости двух окружностей равны, что в этом примере не так. Я думаю, что проникновение имеет какое-то отношение к вычислению, но как ускользает от меня. Я знаю, что проблема может быть переделана как проблема правильных похожих треугольников, в которых мы хотим решить для Gcdy и GCdx.

Само столкновение будет смоделирована как упругое и математике для обмена инертности уже на месте. Единственная проблема заключается в том, где позиционировать круги при столкновении.

Answer 1

Если вы ищете базовую ссылку на неупругие столкновения для круглых объектов, то можно легко следить за Pool Hall Lessons: Fast, Accurate Collision Detection Between Circles or Spheres Джо ван ден Хевелем и Майлзом Джексоном.

От менее формального до наиболее формального, вот некоторые последующие ссылки на ремесло реализации программирования, которое лежит в основе решения вашего вопроса (ответы на столкновение).

• Брайан Бекман & Чарльз Torre The Physics in Games - Real-Time Simulation Explained
• Chris Hecker, Physics, Part 3: Collision Response, Разработчик игры 1997
• Дэвид Baraff, Physically Based Modeling: Principles and Practice, Интернет SIGGRAPH '97 примечания курса, особое значение имеют Слайды для жестких моделирования тела.

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

Answer 2

«В этом и заключается проблема: как мне сделать ход».

Скорее всего, вы хотите знать, как «позиционировать DP обратно в CP, прежде чем настраивать компоненты скорости кругов».

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

Столкновение будет смоделировано как эластичное. Математика для обмена инерцией уже установлена. Проблема заключается в том, где размещать круги.

Учитывая, что я собираюсь обратиться к первому вопросу, разрешая точное местоположение, где происходит столкновение. Предполагая равномерное движение обоих окружностей, достаточно знать точное время столкновения, т. Е. Когда расстояние между центрами окружностей равно сумме их радиусов.

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

Теперь точное время столкновения найдено путем решения квадратного уравнения. Пусть V = (GVx-RVx, GVy-RVy) - относительное движение окружностей, а P = (GIPx-RIPx, GIPy-RIPy) - их относительные положения в «момент» до столкновения. Мы «живой» линейный путь для относительного положения P путем определения:

Р (Т) = Р + Т * У

и спросить, когда эта прямая пересекает окружность вокруг начала координат радиуса Rr + Gr , или когда делает:

(Рх + T * Vx)^2 + (Py + T * Vy)^2 = (Rr + Gr)^2

Это квадратное уравнение в неизвестном времени Т, все другие количества, которые были известны. Обстоятельства таковы, что (при столкновении, имеющем место или до позиции CP) будет существовать положительное реальное решение (обычно два решения: один до СР и один после, но, возможно, пастбищный контакт, дающий «двойной корень»). Решение (root) t, которое вы хотите, - это более раннее, где t (которое равно нулю в «мгновенных» RIP, положениях GIP) меньше.

Answer 3

Фактически вы можете получить выражение для времени, необходимого для достижения столкновения, с учетом начальных положений и векторов скорости.

Вызов ваши объекты А и В, и говорят, что они имеют положение векторов в и б и векторы скорости у и v соответственно.Давайте предположим, что А движется со скоростью у единиц временного шага (так, в момент времени = т, А на ; в момент времени = T + 1, А на + у).

Я не уверен, хотите ли вы видеть вывод; это было бы не так здорово ... мои знания о LaTeX довольно ограничены. (Если вы этого захотите, я могу изменить его позже). На данный момент, вот что я получил, используя общий синтаксис C# -i, с типом Vector2, который объявлен Vector2 (X, Y) и имеет функции для сложения векторов, скалярного умножения, точечного произведения и длины.

double timeToCollision(Vector2 a, Vector2 b, Vector2 u, Vector2 v) 
{ 
    // w is the vector connecting their centers; 
    // z is normal to w and equal in length. 
    Vector2 w = b - a; 
    Vector2 z = new Vector2(-1 * w.Y, w.X); 
    Vector2 s = u - v; 
    // Dot() represents the dot product. 
    double m = Dot(z, s)/Dot(w, s); 

    double t = w.Length()/Dot(w, s) * 
       (w.Length() - sqrt(((2 * r)^2) * (1 + m^2) - (m * w.Length())^2))/
       (1 + m * m) 

    return t; 
} 

Что касается реагирования на столкновения: если вы можете быстро вперед до точки удара, вам не придется беспокоиться о работе с пересекающимися кругами.

Если вам интересно, это выражение дает отличные результаты, когда не будет быть столкновением. Если два объекта отходят друг от друга, но столкнулись бы, если бы их скорости были отменены, вы получите отрицательное значение для t. Если объекты находятся на путях, которые не параллельны, но никогда не будут встречаться (проходя мимо друг друга), вы получите отрицательное значение внутри квадратного корня. Отбрасывая квадратный корень, вы получите время, когда они будут ближе друг к другу. И если они движутся параллельно с одинаковой скоростью, вы получите нуль в знаменателе и неопределенное значение для t.

Ну, надеюсь, это было полезно! У меня была такая же проблема, как у вас, и я решил посмотреть, смогу ли я ее обработать на бумаге.

Редактировать: Я должен был прочитать предыдущие ответы более тщательно, прежде чем публиковать это ... беспорядок формулы выше действительно является решением квадратного уравнения, описанного в hardmath. Извинения за избыточную почту.

Answer 4

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

Прежде всего, вместо двух перемещаемых кругов мы рассмотрим один круг с объединенным радиусом и относительным положением и скоростью. Пусть входные круги имеют позиции P1 и P2, скорости V1 и V2 и радиусы r1 и r2. Пусть объединенный круг имеет положение P = P2 - P1, скорость V = V2 - V1 и радиус r = r1 + r2.

Мы должны найти время, при котором круг пересекает происхождение, другими словами, найти значение t, для которого r = |P + tV|. Должно быть 0, 1 или 2 значения в зависимости от того, не проходит ли круг по происхождению, летит к нему касательно или пролетает через него.

r^2 = ||P + tV|| путем возведения в квадрат с обеих сторон.

r^2 = (P + tV)*(P + tV) = t^2 V*V + 2tP*V + P*P, используя тот факт, что L2-норма эквивалентна точечному произведению вектора с самим собой, а затем распределяет точечный продукт.

t^2 V*V + 2tP*V + P*P - r^2 = 0 превращение его в квадратное уравнение.

Если решений нет, то дискриминатор b^2 - 4ac будет отрицательным. Если он равен нулю или положителен, то нас интересует первое решение, поэтому мы вычтем дискриминант.

a = V*V 
b = 2 P*V 
c = P*P - r^2 
t = (-b - sqrt(b^2 - 4ac))/(2a) 

So t - время столкновения.