Как я тестирую на коллизию двух движущихся 2-х ориентированных ограничительных рамок?

Чтобы проверить обнаружение столкновений между 2 ориентированными ограничивающими прямоугольниками, я бы использовал теорему о разделении осей ( SAT ). Фактически SAT может использоваться для обнаружения столкновений между любыми двумя выпуклыми формами. Этот метод не слишком сложен для понимания и имеет разумную производительность. Теорема может быть легко расширена до 3D.

РЕДАКТИРОВАТЬ:

Алгоритм пытается определить, можно ли подогнать плоскость между двумя объектами. Если такая плоскость существует, то объект отделен и не может пересекаться.

Чтобы определить, отделены ли объекты, достаточно просто спроецировать объекты на нормаль плоскости, и сравнивая интервалы и посмотрим, перекрываются ли они.

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

Можно показать, что для боксов тестируемыми плоскостями разделения являются плоскости, нормали которых равны осям обоих боксов. Таким образом, для 2 коробок вам нужно всего лишь протестировать 4 плоскости разделения. Из 4 самолетов,

Еще одно предложение (которое охватывает сдерживание, и я думаю, что оно дешевле):

Проверьте, есть ли какая-либо из 4 вершин # 1 находятся внутри # 2, затем проверьте, есть ли какая-либо из 4 вершин # 2 внутри # 1. Вот как я бы предложил это сделать:

Предположим, что вершина # 1, которую вы проверяете, v, а 4 вершины # 2 v1 ... v4. Повернуть в обратном направлении все 5 вершин по ориентации # 2. (Чтобы повернуть вектор u в обратном направлении на матрицу ориентации M, умножьте u на M-транспонированный: M ^ T u, предполагая, что в вашем соглашении ориентация работает путем умножения влево.) Получившийся второй блок, называемый # 2 ', теперь выровнен по оси - вы можете сразу проверить, содержится ли в нем v'.

Если вы нашли какую-либо вершину # 1 внутри # 2 - стоп, у вас есть пересечение. В противном случае - продолжить.

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

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

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

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

Если у вас есть две ограничивающие рамки (то есть прямоугольники) с произвольной ориентацией (что, как я предполагаю, означает некоторое «вращение»), то я бы сделал следующее:

• Начиная с начальной позиции (где я предполагаю, что ограничивающие рамки не пересекаются), переместите каждый прямоугольник вперед в зависимости от его скорости (однако вы применяете движения с течением времени).
• Найдите координаты углов каждого переведенного ограничивающего прямоугольника. Эти 4 координаты определяют конечные точки 4-х линейных сегментов, составляющих края ограничивающей рамки.
• Для ограничивающего прямоугольника №1 проверьте наличие пересечения между каждым из его линейных сегментов и четырьмя линейными сегментами ограничивающего прямоугольника №2. Вы можете сделать это, используя стандартные уравнения для вычисления точки пересечения двух прямых, как, например, обсуждается здесь .
• Если было пересечение, вычислите долю движения, которое было успешным, используя координаты точек пересечения и известный перенос, который вы применили.
• Повторяйте вышеуказанные шаги для каждого обновления.

РЕДАКТИРОВАТЬ: Приблизительный псевдокод (включающий то, что обсуждалось в комментариях) будет выглядеть следующим образом:

...test for intersections between the OBB edges...
if any intersections are found{
    ...run code for when OBBs are partially overlapping...
}else{
    P = line segment whose endpoints are the OBB centers;
    ...test for intersections between P and OBB edges...
    if P intersects edges of both OBBs{
        ...run code for when OBBs are not touching...
    }else{
        ...run code for when one OBB is completely inside the other...
    }
}

Вам, вероятно, следует реализовать дерево квадрантов (см. wikipedia ), чтобы отслеживать все объекты на плоскости. К сожалению, я никогда не реализовывал ни один сценарий для обнаружения столкновений, но кажется, что другие люди смогли создать сценарии, аналогичные вашему, с использованием четырехугольных деревьев.