Прямоугольное столкновение призмы

Question

Я хочу создать игру, в которой персонаж представляет собой прямоугольную призму, которую можно вращать, а остальная часть карты - это прямоугольные призмы, ориентированные по оси. Все, кроме персонажа, будет статичным, поэтому мне было интересно, какой будет лучший алгоритм для определения, сталкивается ли персонаж с какими-либо частями на карте. Любые учебники / код / ​​совет будет высоко ценится:)

Кроме того, персонаж будет поворачиваться только по оси Y, если это поможет.

Answer 1

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

1. Проверьте, неY-интервал персонажа пересекает Y-интервал другой призмы.

2. Проверьте, пересекаются ли соответствующие XZ-сечения двух призм, что составляет проблему обнаружения столкновения между двумя повернутымипрямоугольники.

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

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

Пересекающиеся интервалы

Два закрытых интервала [a, b] и [c, d] пересекаются, если и только c ≤ b и a≤ д.Здесь мы также предполагаем, что обозначения интервалов согласованы, то есть a ≤ b и c ≤ d (в противном случае поменяйте местами конечные точки, если это необходимо).

Пересекающиеся повернутые прямоугольники

Высокий рейтинг SO на этот конкретный вопрос здесь .Реализация Lua, которую я написал для чуть более общей проблемы, Наименьшее расстояние между двумя прямоугольниками , включает в себя оптимизацию "раннего выхода" (ограничивающий круг и вершину в прямоугольнике), о которой я упоминал в этом потоке ,Мой код Lua возвращает «ложь», если повернутые прямоугольники пересекаются, в противном случае расстояние между ними.Для целей Java возвращаемое значение ноль в случаях коллизии будет служить.

Answer 2

Я считаю, что один из способов проверить это - проверить 16 случаев пересечения линий:

http://www.math.niu.edu/~rusin/known-math/95/line_segs

Если вы хотите оптимизировать, вы также можете проверить, не имеют ли прямоугольники шансов перекрытия, т. Е. Если все углы находятся справа / слева / выше / ниже другого прямоугольника.

Edit:

Комментарий ниже.