Методы обнаружения столкновений в двигателе непрерывной физики

Question

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

Широкая фаза Единственный непрерывный метод широкой фазы, который я могу придумать, - это заключить каждое тело в круг и проверить, будет ли каждый круг перекрывать другой. Это кажется ужасно неэффективным и лишено какой-либо отбраковки.

Я понятия не имею, какие непрерывные аналоги могут существовать для современных методов дискретного отбора столкновений, таких как квадр-деревья. Как мне предотвратить недопустимые и бессмысленные широкие тесты, такие как дискретный двигатель?

Узкая фаза
Мне удалось адаптировать узкий SAT к непрерывной проверке, а не к дискретным, но я уверен, что есть другие лучшие алгоритмы в документах или на сайтах, которые вы, ребята, могли встретить.
Какие различные быстрые или точные алгоритмы вы предлагаете использовать, и каковы преимущества / недостатки каждого из них?

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

Answer 1

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

Например, еслиу вас есть круг в (x, y), движущийся вправо (+ x) с постоянной скоростью, затем, когда вы расширяете его с измерением времени, у вас есть диагональный цилиндр в (x, y, t).Делая пересечения между этими трехмерными объектами (просто рассматривайте время как z), вы можете видеть, будут ли когда-либо пересекаться два объекта.Если точка P является точкой пересечения, то вы знаете время этого пересечения, просто взглянув на Pt

. Это также обобщает на более высокие измерения, хотя математика становится трудной (для меня, во всяком случае).

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

Answer 2

Я собираюсь предположить, что вам нужны такие вещи, как гравитация или другие консервативные силы в вашей симуляции. Если это так, то траектории ваших объектов, скорее всего, не будут линиями, и в этом случае, как указал Адриан, математика будет несколько сложнее. Я не могу придумать способ избежать проверки всех возможных комбинаций кривых на наличие столкновений, но вы можете довольно легко рассчитать минимальное расстояние между двумя кривыми, если обе они являются решениями для линейных систем (или, в общем, если у вас есть замкнутое решение для кривых). Если вы знаете, что x1(t) = f(t) и x2(t) = g(t), то что вы хотите сделать это рассчитать расстояние ||x1(t) - x2(t)|| и установить его производную на ноль. Это должно быть выражение, которое зависит от f(t), g(t) и их производных и даст вам время tmin (или, возможно, несколько возможных), после которого вы затем оцените расстояние и проверите, чтобы оно больше или меньше r1+r2 --- сумма радиусов двух ограничивающих кругов. Если оно меньше, то у вас есть потенциальное столкновение в это время, поэтому вы запускаете алгоритм узкой фазы.