Обнаружение столкновения между двумя телами, подвергающимися множественным преобразованиям

Question

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

Как вы можете видеть, иногда t0 и t1 нет столкновений, номежду ними происходит несколько столкновений.

Один из способов решения этой проблемы, который я задумал, заключался в уменьшении размера временных интервалов.Таким образом, между t0 и t1 должно быть в общей сложности n обновлений для проверки на наличие коллизий.Это работает, но единственным способом, который я обнаружил, что я не могу гарантировать ложных негативов, то есть не обнаружив столкновения, было объединение в чрезвычайно малых временных шагах.Как вы можете себе представить, это очень дорого, потому что это приводит к десяткам или сотням временных шагов на тело на цикл обновления.Я не говорю, что эта идея не имеет смысла, но мне нужно найти способ рассчитать минимальное количество временных шагов, а не равномерно перемещать каждое тело вперед на одну единицу расстояния / поворота, пока они не достигнут желаемого положения и ориентации.

Итак, мой вопрос состоит из двух частей:

1. Есть ли лучший способ определить, произошло ли столкновение и когда?
2. Если нет, можно ли рассчитатьминимальное количество временных шагов?

Answer 1

Я сомневаюсь, что эту проблему можно решить вообще.Если мы рассматриваем время как третью пространственную ось, проблема эквивалентна нахождению любого пересечения между телами, очерченного контуром двух фигур между временами t_1 и t_2 .Лучшее (наиболее точное) решение, вероятно, состоит в использовании небольших временных шагов и рассмотрении пересечений между любыми двумя 3d-срезами, охватывающими время t_m и t_ (m + 1) ,Но это будет не намного лучше, чем рассмотрение только двухмерных цифр.

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

Если вы это сделаете, я бы предложил шаг по времени, dt , что-то вроде

dt = Min (f * d / Max (-v, v_min), DT), где

DT - максимальный временной шаг, который вы допустите,

d - расстояниемежду ближайшими точками на рисунках

v - это скорость, с которой это расстояние изменяется (отрицательно, если они сближаются),

v_min - это минимальная (положительная) скорость, которую вы считаете реалистичнойдля моделирования,

f - это некоторый коэффициент меньше единицы, чтобы минимизировать количество ложных срабатываний, вызванных внезапными «скачками» скорости между двумя объектами.

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

Надеюсь, что это поможет.