Методы обнаружения столкновений с широкой фазой?

Question

Я создаю физический 2D-движок и хочу добавить широкофазное обнаружение столкновений, хотя я знаю только 2 или 3 типа:

• Проверить все на все остальное (сложность O (n ^ 2))
• Sweep and Prune (сортировка и развертка)
• кое-что о бинарном пространстве (не знаю, как это сделать)

Но наверняка есть еще варианты, верно? кто они такие? И может ли быть предоставлено базовое описание каждого или ссылки на описания?

Я видел это , но я прошу список доступных алгоритмов, не самый лучший для моих нужд.

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

Answer 1

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

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

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

Если вы говорите о перемещении тел внутри ограниченных пространств вместо открытых пространств, то вы можете рассмотреть BSP дерево ;дерево разделяет мир на «пространство, в котором вы можете ходить» и «стены», и отсечение тела в дереве определяет, находится ли оно в законном положении.В зависимости от геометрии мира, вы также можете использовать BSP для широкофазного обнаружения столкновений между телами в мире.

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

Answer 2

Альтернативой QuadTrees или BSPTrees являются SphereTrees (CircleTrees в 2D, реализация будет более или менее одинаковой). Преимущество SphereTrees заключается в том, что они очень хорошо справляются с большими нагрузками динамических объектов. Если ваши объекты постоянно движутся, BSPTrees и QuadTree обновляются медленнее, чем Sphere / Circle Tree.

Если у вас есть хорошее сочетание статических и динамических объектов, разумно хорошим решением будет использование QuadTree / BSPTree для статики и Sphere / Cicle Tree для динамических объектов. Просто помните, что для любого данного объекта вам нужно будет проверить его по обоим деревьям.

Answer 3

Я рекомендую quadtree разбиение. Это довольно просто и работает очень хорошо. Вот Flash demo обнаружения столкновений методом грубой силы против обнаружения столкновений с деревом. (Вы можете указать это, чтобы показать структуру дерева квадрантов.) Вы заметили, что обнаружение столкновений деревьев в этом демо составляет только 3% от грубой силы?

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

Answer 4

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

1. Пространственное разбиение. Вырежьте пространство и дешево исключите кандидатов, которые находятся в разных регионах. Например, BSP, сетки, октреи и т. Д.

2. Разделение объекта. Аналогично # 1, но кластеризация сосредоточена на самих объектах больше, чем на пространстве, в котором они находятся. Например, ограничивающие иерархии томов.

3. Методы сортировки и развертки. Расположите объекты в порядке и исключите столкновения между соседними объектами.

1 и 2 часто являются иерархическими, повторяющимися в каждом разделе по мере необходимости. С помощью 3 вы можете при желании выполнять итерации по разным измерениям.

Компромиссы во многом зависят от геометрии сцены. Кластеры объектов или они распределены равномерно или редко? Они все примерно одинакового размера или есть огромные различия в размере? Сцена динамична? Можете ли вы позволить себе много времени для предварительной обработки?

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

Answer 5

Возможно, вы захотите проверить, что Скотт сделал в Бурундук с пространственным хешированием. Источник в свободном доступе. Я думаю, что он использовал технику, аналогичную Box-2D , если бы не столкновение, определенно для сохранения контакта.

Answer 6

Я только что нашел решение, которое не зависит от размера сетки и, вероятно, O (nlogn) (это оптимально, когда нет столкновений), хотя худшее при O (n n logn ) (когда все сталкивается).

Я также реализовал и протестировал его, вот ссылка на источник . Но я не сравнивал это с решением грубой силы.

Описание того, как это работает: (Я ищу столкновения прямоугольников)

• по оси x Я сортирую прямоугольники по их правому краю (O (nlogn))

• для каждого прямоугольника в отсортированном списке я беру левый край и выполняю двоичный поиск до тех пор, пока не найду крайний правый край слева от левого края и вставлю эти прямоугольники между этими индексами в набор возможных__Коллекций_О__Акс n прямоугольников, logn для двоичного поиска, n вставляет int в набор по O (log n) для каждой вставки)

• по оси Y я делаю то же самое

• в каждом из наборов у меня теперь есть возможные столкновения по x (в одном наборе) и по y (внутри другого), я пересекаю эти наборы, и теперь у меня есть столкновения как по оси x, так и по оси y (это означает, что я беру общие элементы) (O (n))

извините за плохое описание, надеюсь, вы лучше понимаете из источника, также пример, показанный здесь: image

Answer 7

Альтернативой являются простые сетки, скажем, 20x20 или 100x100 (зависит от вашего мира и объема памяти). Реализация проще, чем рекурсивная структура, такая как quad / bsp-деревья (или сферические деревья в этом отношении).

Объекты, пересекающие границы ячеек, в этом случае немного проще и не вырождаются настолько, насколько могла бы наивная реализация bsp / quad / oct-tree.

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

Answer 8

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

Основная идея заключается в том, что вы создаете рекурсивную древовидную структуру, в которой хранятся 4 (для четырехугольника) или 8 (октавные) дочерние объекты того же типа, что и корень дерева. Каждый узел в дереве представляет часть декартового пространства, например, -100 -> +100 на каждой применимой оси. каждый дочерний элемент представляет то же пространство, но подразделяется на половину (непосредственный дочерний элемент примера будет представлять, например, -100-> 0 по оси X и -100-> 0 по оси Y).

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

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

Итак, прежде чем идти вперед и попытаться реализовать такой алгоритм, как вы:

Сколько объектов в моей игре? Если их много, мне, вероятно, нужна широкая фаза. Если нет, то Nnarrowphase должно быть достаточно. Кроме того, я имею дело со многими движущимися объектами?

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

Если это так, вам лучше использовать Sweep и Prune, которые поддерживают минимальные / максимальные кучи экстентов форм в вашем мире. Объекты не нужно повторно вставлять, но кучи нужно восстанавливать в каждом кадре, хотя обычно это происходит быстрее, чем по всему дереву, обход с удалением и повторной вставкой.

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

Answer 9

Я бы хотел порекомендовать вступительную ссылку на физику игры от Иана Миллингтона, Разработка движка игровой физики . У этого есть большой раздел по широкому обнаружению столкновения фазы с образцом кода.

Answer 10

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

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

Преимущество этого подхода перед более адаптивным алгоритмом (т. Е. BSP, Quadtree, Circletree) заключается в том, что доступ к ячейкам можно получить за O (1) время (т. Е. Постоянное время), а не O (log N), т. Е. Логарифмическое ). Однако эти последние алгоритмы могут адаптироваться к большой изменчивости плотности объектов. Сеточный подход работает лучше всего, когда плотность объекта довольно постоянна в пространстве.