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

Question

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

Я посмотрел тест Polygon на GPWiki - http://gpwiki.org/index.php/Polygon_Collision - но он не учитывает движущиеся объекты или объект, который полностью находится в OBB.

Книга «Обнаружение столкновений в реальном времени» охватывает 3D OBB в Главе 4: Ограничивающие объемы, но метод тестирования в 3 измерениях значительно сложнее, чем в 2D.

Answer 1

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

EDIT:

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

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

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

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

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

• Начиная с начальной позиции (где я предполагаю, что ограничивающие рамки не пересекаются), переведите каждый прямоугольник вперед на основе его скорости (однако вы применяете движения во времени).
• Найдите координаты углов каждого переведенного ограничивающего прямоугольника. Эти 4 координаты определяют конечные точки 4 отрезков, которые составляют края ограничительной рамки.
• Для ограничительной рамки № 1 проверьте наличие пересечения между каждым из ее линейных сегментов и 4 сегментами линии ограничительной рамки № 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...
    }
}

Answer 4

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

Answer 5

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

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