ПрограммированиеТерминыФизика

Широкая фаза (Broad Phase)

Широкая фаза - одна из стадий определения столкновений.
Изначально из всех объектов (например, физических тел) находят пары потенциально пересекающихся. “Потенциально пересекающихся” - означает не точную проверку на пересечение, а проверку упрощенной геометрии, в роли которой обычно выступает Axis-Aligned Bounding Boxes, реже Bounding Spheres(ограничивающие сферы).
Надобность широкой фазы можно объяснить следующим:
Узкая фаза, требуемая для точного определения точек контактов(нормалей, глубины проникновения), обычно намного дороже, чем проверка на пересечение AABB, в то же время - из всех возможных пересечений n*(n-1) / 2 для n объектов, обычно реально пересекается очень малое количество, следовательно мы можем отбросить огромное количество относительно дорогих проверок узкой фазой, сначала проведя простые проверки на потенциальное пересечение, что и делает широкая фаза.

От выбора широкой фазы во многом может зависеть производительность приложения при большом количестве тел.
Основные алгоритмы широкой фазы:

  • Brute-force (так же встречаются названия Exhaustive, All-Pairs test) - простая проверка на пересечения AABB или же BS каждого-с-каждым объектом. Сложность алгоритма O(n2), то есть при увеличении количества объектов время занимаемое широкой фазой будет изменяться пропорционально квадрату числа объектов.
  • Spatial Hashing - разбиение пространства для более эффективного поиска. Иерархическая реализация с многочисленными оптимизациями может занимать O(n) времени, что очень хорошо. Хотя есть минусы, в том числе большой объем занимаемой памяти и, вероятно, трудность оптимальной реализации.
  • Sweep-and-prune - метод сортировки AABB по координатам. То есть для каждой из осей(для 3D - x,y,z, для 2D - x,y), есть массив интервалов занимаемых AABB объектов. Эти интервалы хранятся отсортированными и сортируются каждый раз, заодно проверяя на пересечения по координатам AABB. Сложность алгоритма, в зависимости от когерентности, как правило, составляет от O(n) до O(n2)(в худшем случае, когда интервалы на момент сортировки находятся в обратном порядке).
  • Наиболее часто в физических движках для физики твердых тел применяются различные варианты sweep-and-prune широкой фазы, в то время как spatial hashing алгоритмы применяются для широкой фазы в физике деформируемых\мягких тел, симуляции жидкостей.

    Что такое Широкая фаза (Broad Phase)?

    #broad phase, #collision detection

    27 февраля 2007 (Обновление: 12 мар 2013)