Обнаружение столкновений между ускоряющимися сферами

Question

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

Итерационный моделирование движения, которое я использую в основном следующим образом:

(Примечание:. 3D Векторы ВСЕ CAPS)

For each obj 

    obj.ACC = Sum(all acceleration influences) 

    obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2  (*EQ.2*) 

    obj.VEL = obj.VEL + (obj.ACC * dT) 

Next 

Где:

obj.ACC is the acceleration vector of the object 
obj.POS is the position or location vector of the object 
obj.VEL is the velocity vector of the object 

obj.Radius is the radius (scalar) of the object 

dT is the time delta or increment 

Я в основном необходимо найти эффективную формулу, полученную из (EQ.2) выше для двух объектов (obj1, obj2) и указать, если они когда-либо были сталкиваются, и если да, то в какое время. Мне нужно точное время и для того, чтобы я мог определить, будет ли он в это конкретное время увеличиваться (поскольку accelleratons будут отличаться при разных временных шагах), а также для того, чтобы я мог найти точное положение (которое я знаю, как это сделать, учитывая время)

для этого двигателя, я моделирование всех объектов как сферы, вся эта формула/algortithim нужно сделать, это выяснить, в каких точках:

(obj1.POS - obj2.POS).Distance = (obj1.Radius + obj2.Radius) 

где .distance положительное скалярное значение. (Вы можете также сгруппировать обе стороны, если это проще, чтобы избежать функции квадратного корня, неявной в вычислении .Distance).

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

---

Некоторые Разъяснения:.

1) это не достаточно для меня, чтобы проверить * пересечения * из двух сфер до и после времени. Во многих случаях их скорости и изменения положения значительно превышают их радиусы.

2) RE: Эффективность, мне не нужна помощь (на данный момент так или иначе) в отношении определения вероятных кандидатов для столкновений, я думаю, что у меня это покрыто.

---

Еще одно уточнение, который, кажется, придумать много:

3) Мое уравнение (EQ.2) пошагового движения является квадратным уравнением, которое применяется как Velocity и ускорение:

obj.POS = obj.POS + (obj.VEL * dT) + (obj.ACC * dT^2)/2 

физике двигателей, которые я видел, (и, конечно, каждый игровой движок, что я когда-либо слышал) только линейный уравнения движения дополнительного, которые применяются только Скорость:

obj.POS = obj.POS + (obj.VEL * dT) 

Вот почему я не могу использовать широко опубликованные решения для обнаружения столкновений, найденных на Stac kOverflow, в Википедии и по всему Интернету, например, найти пересечение/ближайший подход двух сегментов линии. Мое моделирование связано с переменными ускорениями, которые имеют фундаментальное значение для результатов, поэтому мне нужен пересечение/ближайший подход двух сегментов параболических.

Answer 1

На веб-странице, на которую ссылается AShelley, разработан метод «Ближайшая точка подхода» для случая двух объектов, движущихся с постоянной скоростью. Однако я считаю, что один и тот же метод векторных вычислений может быть использован для получения результата в случае двух объектов, движущихся с постоянным ненулевым ускорением (квадратичная зависимость от времени).

В этом случае производная по времени от функции квадрата равна 3-му порядку (кубическому) вместо 1-го порядка. Поэтому будет 3 решения для времени ближайшего подхода, что неудивительно, так как путь обоих объектов изогнут, поэтому возможны множественные пересечения. Для этого приложения вы, вероятно, захотите использовать самое раннее значение t, которое находится в пределах интервала, определенного текущим этапом моделирования (если такое время существует).

Я разработал производное уравнение, которое должно дать времена наибольшего сближения:

0 = |D_ACC|^2 * t^3 + 3 * dot(D_ACC, D_VEL) * t^2 + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ] * t + 2 * dot(D_POS, D_VEL)

где:

D_ACC = ob1.ACC-obj2.ACC

D_VEL = ob1.VEL-obj2.VEL (до обновления)

D_POS = ob1.POS-obj2.POS (также перед обновлением)

и dot(A, B) = A.x*B.x + A.y*B.y + A.z*B.z

(Обратите внимание, что квадрат величины |A|^2 можно вычислить с помощью dot(A, A))

Чтобы решить эту проблему для т, вам, вероятно, нужно использовать формулы, как те found on Wikipedia.

Конечно, это только даст вам момент ближайший подход. В этот момент вам нужно будет проверить расстояние (используя что-то вроде уравнения 2). Если он больше (obj1.Radius + obj2.Radius), его можно пренебречь (т. Е. Никакого столкновения). Однако, если расстояние меньше, это означает, что сферы сталкиваются до этого момента. Затем вы можете использовать итеративный поиск для проверки расстояния в более ранние времена. Возможно, также будет возможно придумать другой (еще более сложный) вывод, который учитывает размер или можно найти какое-либо другое аналитическое решение, не прибегая к итеративному решению.

Edit: из-за более высокого порядка, некоторые из решений уравнения фактически моменты дальнему разделения. Я считаю, что во всех случаях один из 3-х решений или 2 из 3-х решений будет временем более полного разделения. Вы можете проверить аналитически ли вы на мин или макс путем оценки второй производной по времени (при значениях т, которые вы нашли, установив первую производную нулю):

D''(t) = 3 * |D_ACC|^2 * t^2 + 6 * dot(D_ACC, D_VEL) * t + 2 * [ |D_VEL|^2 + dot(D_POS, D_ACC) ]

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

Answer 2

Похоже, вы хотите Closest Point of Approach (CPA). Если он меньше суммы радиусов, у вас есть столкновение. В ссылке есть пример кода. Вы можете рассчитать каждый кадр с текущей скоростью и проверить, меньше ли время CPA, чем размер вашего галочки. Вы даже можете кэшировать время cpa и обновляться только тогда, когда ускорение было применено к любому элементу.

Answer 3

Нарисуйте линию между местом начала и конечным местоположением каждой сферы. Если результирующие отрезки линии пересекаются с шарами, определенно сталкивающимися в какой-то точке, и какая-то умная математика может найти, в какое время произошло столкновение. Также убедитесь, что минимальное расстояние между сегментами (если они не пересекаются) всегда меньше радиуса 2 *. Это также укажет на столкновение.

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

Рассматривали ли вы использование библиотеки физики, которая уже выполняет эту работу? Многие библиотеки используют гораздо более совершенные и более стабильные (лучшие интеграторы) системы для решения систем уравнений, с которыми вы работаете. Bullet Physics Приходит на ум.