Какой самый быстрый способ проверить, пересекаются ли две движущиеся AABB?

12

У меня есть две AABB, которые движутся, какой самый быстрый способ проверить, будут ли они пересекаться под рамкой?

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

Я думаю просто сделать это так:

Эта

Но этот шестиугольник довольно сложен, и я не знаю, как рассчитать пересечение AABB - Polygon, есть ли более простой способ?

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

Благодарю.

супер
источник
3
Я не совсем понимаю. Вы специально упомянули «развернутый тест», пробовали ли вы типичный анализ AABB? Это именно то, что вы хотите.
SomeWritesReserved
1
Я согласен с комментарием выше - что не так с «классическим» тестом? Более того, большинство предлагаемых здесь решений явно медленнее ... плюс некоторые из них могут давать неправильные результаты (не надежные).
Wondra
Вы можете попробовать Тест Разделяющей
Pharap

Ответы:

8

Используйте сумму Минковского

Хороший способ решить эту проблему , чтобы рассмотреть пересечение между линией движения ( v ) переведены в начало координат ( V « ) и сумма Минковского от А поворачивается на 180 градусов в начале координат ( А» ) и его препятствия (только B в данном случае): А»B .

На следующем рисунке я помещаю A smack-dab в начало произвольной системы координат. Это упрощает понимание, поскольку вращение A на 180 градусов приводит к A ' , а v, переведенная в начало координат, равна v' .

Сумма Минковского - это зеленый прямоугольник, и точки пересечения движущегося A и неподвижного B можно найти, выполнив пересечение линии-AABB . Эти точки отмечены синими кругами.

Сумма Минковского - вырожденный случай

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

Сумма Минковского - более общий случай

Несколько движущихся AABB

Чтобы это работало для двух AABB, которые движутся линейно в течение определенного периода времени, вы должны вычесть вектор скорости B из вектора скорости A и использовать его в качестве отрезка для пересечения линии-AABB.

Псевдокод

def normalize(aabb):
    return {x1: min(aabb.x1, aabb.x2), x2: max(aabb.x1, aabb.x2),
            y1: min(aabb.y1, aabb.y2), y2: max(aabb.y1, aabb.y2),

def rotate_about_origin(aabb):
    return normalize({x1: -aabb.x1, x2: -aabb.x2
                      y1: -aabb.y1, y2: -aabb.y2})

# given normalized aabb's
def minkowski_sum(aabb1, aabb2):
    return {x1: aabb1.x1+aabb2.x1, x2: aabb1.x2+aabb2.x2,
            y1: aabb1.y1+aabb2.y1, y2: aabb1.y2+aabb2.y2}

def get_line_segment_from_origin(v):
    return {x1: 0, y1: 0, x2: v.x, y2: v.y}

def moving_objects_with_aabb_intersection(object1, object2):
    A = object1.get_aabb()
    B = object2.get_aabb()

    # get A'⊕B
    rotated_A = rotate_about_origin(A)
    sum_aabb = minkowski_sum(rotated_A, B)

    # get v'
    total_relative_velocity = vector_subtract(object1.get_relative_velocity(), object2.get_relative_velocity())
    line_segment = get_line_segment_from_origin(total_relative_velocity)

    # call your favorite line clipping algorithm
    return line_aabb_intersection(line_segment, sum_aabb)

Столкновение ответ

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

При столкновении алгоритм пересечения линии-AABB возвращает 1 или 2 точки пересечения в зависимости от того, заканчивает ли A свое движение внутри B или проходит через него соответственно. (Это не относится к вырожденным случаям, когда A пасет B вдоль своих сторон или вдоль одного из их соответствующих углов.)

В любом случае, первая точка пересечения вдоль отрезка линии - это точка столкновения, вы бы перевели ее обратно в правильную позицию в мировой системе координат (первый голубой круг на втором рисунке вдоль исходного v , назовите его p ) и затем решите (например, для упругих столкновений, отражая v вдоль нормали столкновения в точке p ), какой будет фактическая позиция для A в конце кадра ( At + 1 ).

Столкновение ответ

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

Эрик
источник
Спасибо, самое интересное. Не могли бы вы объяснить, как вы справляетесь со случаем, когда А и В пересекаются во время перемещения, но заканчивают движение без пересечения?
GameAlchemist
@GameAlchemist Это будет реакция на столкновение, а не обнаружение столкновений (предмет вопроса). Но мне нравится Paint, так что проверьте редактирование. :-)
Эрик
Спасибо за обновление (и ура за схемы :-)), это не был мой вопрос, но помог мне понять, что ваш алгоритм уже обрабатывает случай, когда А полностью проходит через B.
GameAlchemist
5

OBB - ориентированная ограничительная коробка. Вот учебник

По сути, ограничивающий прямоугольник выравнивается с вектором скорости объекта A в качестве оси Y (вверх). Его ширина и высота могут быть рассчитаны по начальной и конечной точкам объекта А. Затем вы сравниваете это с AABB объекта B (рассматривая его как OOBB) и вашим золотым.

Если вы просто ищете быстрый тест на пересечение, чтобы увидеть, ЕСЛИ они МОГУТ пересекаться, вы можете создать AABB, который окружает AABB объекта A как в начальной, так и в конечной позиции. Если AABB не пересекается со всем этим AABB, то пересечения нет; Однако это может привести к ложным срабатываниям, поэтому его следует использовать только в качестве предварительного теста.

Вольфганг Скайлер
источник
4

Вам не нужны OOB, и вам не нужно использовать обнаружение столкновений с изменяющимся временем. Просто используйте обычный тест AABB, смотрите эту ссылку . По сути, он делает именно то, что есть на вашей диаграмме: движущаяся AABB «перемещается» из начальной точки в конечную точку, а затем используется для обнаружения столкновений с другими статическими AABB.

Если вы обеспокоены тем, что этот быстрый тест дороже, поскольку он возвращает «время воздействия», я думаю, вы преждевременно оптимизируете.

Более подробную информацию о комплексных тестах можно найти в превосходной книге Кристера Эриксона « Обнаружение столкновений в реальном времени ».

SomeWritesReserved
источник
3

AABB-аппроксимация

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

Оценка наличия или отсутствия столкновения путем проверки AABB (или OOBB) с использованием только начальных и конечных положений может пропустить столкновения, если один из объектов вращается быстро и длиннее в одном измерении, чем в другом.

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

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

Constablebrew
источник
2
или предварительно вычислите максимальную ширину, которую BB может использовать для любого вращения, и используйте это
ratchet freak
2

Вы должны будете разложить движение на более мелкие шаги. Например:

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

Это может показаться слишком дорогим, но имейте в виду, что объект, движущийся быстрее, чем его собственная ширина, в каждом цикле будет ЧРЕЗВЫЧАЙНО быстрым, поэтому этот сценарий не так распространен, как вы могли подумать.

Лео
источник
2
Этот метод плох, потому что он не будет ловить некоторые случаи (например, поле рядом с первым и вторым, которое вы нарисовали), и увеличение выборки будет излишним. Простой тест Polygon с использованием SAT должен быть достаточно быстрым и надежным.
Sopel
1
Да, это хорошее решение, но не слишком хорошее. Точность быстро уменьшается, когда столкновение приближается к углам объектов, производительность снижается с увеличением скорости (или точности, в зависимости от реализации), и это просто излишне хакерство.
BWG
2

Вы также должны использовать относительные скорости для проверки столкновения, чтобы одна AABB была «статичной», а другая двигалась со скоростью своей собственной скорости минус скорость «статической».

Самый быстрый способ увидеть, могут ли они пересекаться, - это просто увеличить скорость движущейся AABB.

например, AABB движется вправо с шагом 0,1 x / кадр, затем вы расширяете его, чтобы левый край остался прежним, а правый край был на 0,1 дальше. Тогда вы можете проверить с новым AABB. Если false, то столкновения нет. (ранний возврат и точность для малых скоростей).

Затем вы можете проверить, пересекается ли конец и начало AABB движущегося объекта. если true, тогда верните true.

В противном случае вам нужно проверить, пересекает ли диагональ статический ABB.

Это включает в себя получение координат диагонали, где x = левый край статики, а правый край, чтобы увидеть, находится ли y внутри дна и верха. (повторите наоборот)

чокнутый урод
источник