Широкая фаза: btDbvtBroadphase, btAxisSweep3

В архитектуре физического движка вычисление столкновений разделяется на два этапа:

  1. Широкая фаза (Broadphase) — быстрый поиск потенциально пересекающихся пар.
  2. Узкая фаза (Narrowphase) — точное вычисление контактов между найденными парами.

Широкая фаза не определяет фактическое столкновение. Её задача — эффективно сократить число проверок, отфильтровав объекты, которые гарантированно не могут пересекаться.

В основе работы лежат ограничивающие объёмы (AABB — Axis-Aligned Bounding Box). Для каждого физического тела рассчитывается прямоугольный параллелепипед, выровненный по мировым осям координат. Пересечение AABB служит критерием для передачи пары в узкую фазу.

В библиотеке Ammo.js, являющейся портом Bullet Physics, реализованы разные алгоритмы широкой фазы. Наиболее часто применяются:

  • btDbvtBroadphase
  • btAxisSweep3

btDbvtBroadphase

Общая характеристика

btDbvtBroadphase основан на динамическом иерархическом дереве ограничивающих объёмов (Dynamic Bounding Volume Tree, DBVT). Это адаптивная структура данных, которая перестраивается по мере движения объектов.

Алгоритм оптимизирован для:

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

Принцип работы

Структура DBVT представляет собой бинарное дерево:

  • Листовые узлы содержат AABB конкретных объектов.
  • Внутренние узлы хранят объединённые AABB дочерних элементов.

При обновлении положения тела:

  1. Пересчитывается его AABB.
  2. Узел может быть удалён и повторно вставлен в дерево.
  3. Выполняется локальная оптимизация структуры.

Поиск потенциальных пересечений происходит путём обхода дерева и проверки пересечения AABB узлов.

Преимущества

  • Хорошо масштабируется при большом числе динамических тел.
  • Не требует заранее заданных границ сцены.
  • Эффективен при хаотичном распределении объектов.

Недостатки

  • Небольшие накладные расходы на обслуживание дерева.
  • Чуть более высокая сложность по сравнению с алгоритмами sweep-and-prune.

Создание в Ammo.js

const broadphase = new Ammo.btDbvtBroadphase();

Использование в составе физического мира:

const collisionConfiguration = new Ammo.btDefaultCollisionConfiguration();
const dispatcher = new Ammo.btCollisionDispatcher(collisionConfiguration);
const solver = new Ammo.btSequentialImpulseConstraintSolver();

const dynamicsWorld = new Ammo.btDiscreteDynamicsWorld(
    dispatcher,
    broadphase,
    solver,
    collisionConfiguration
);

Особенности применения

btDbvtBroadphase является дефолтным выбором для большинства проектов, включая:

  • игровые сцены с большим числом динамических тел;
  • процедурно генерируемые миры;
  • сцены без жёстко ограниченных границ.

btAxisSweep3

Алгоритм Sweep and Prune

btAxisSweep3 реализует классический алгоритм Sweep and Prune (SAP).

Основная идея:

  1. Проецировать AABB объектов на одну или несколько осей.
  2. Отсортировать интервалы.
  3. Искать перекрывающиеся диапазоны.

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

Особенности реализации

btAxisSweep3:

  • Работает в фиксированных границах мира.
  • Использует квантование координат.
  • Требует задания минимальной и максимальной точки пространства.

Создание:

const worldMin = new Ammo.btVector3(-1000, -1000, -1000);
const worldMax = new Ammo.btVector3(1000, 1000, 1000);

const broadphase = new Ammo.btAxisSweep3(worldMin, worldMax);

Важность границ мира

В отличие от btDbvtBroadphase, алгоритм SAP требует заранее определить рабочий объём. Все объекты должны находиться внутри него.

Если объект выходит за границы:

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

Поэтому границы должны быть выбраны:

  • достаточно большими,
  • но не чрезмерно, чтобы не ухудшать точность.

Преимущества

  • Очень высокая производительность при умеренном числе объектов.
  • Отличная эффективность в сценах с преимущественно статическими телами.
  • Минимальные накладные расходы при малом движении.

Недостатки

  • Плохо подходит для бесконечных или динамически расширяемых миров.
  • Требует ручной настройки границ.
  • Менее эффективен при хаотичном движении большого числа тел.

Сравнение btDbvtBroadphase и btAxisSweep3

Характеристика btDbvtBroadphase btAxisSweep3
Тип структуры Динамическое дерево Sweep-and-Prune
Границы мира Не требуются Обязательны
Подходит для Динамических сцен Ограниченных сцен
Масштабируемость Высокая Средняя
Стабильность при большом числе движущихся тел Высокая Снижается

Выбор алгоритма в реальных проектах

Сценарии для btDbvtBroadphase

  • Песочницы и open-world сцены.
  • Физические симуляции с постоянным добавлением и удалением объектов.
  • Игры с разрушениями и процедурной генерацией.

Сценарии для btAxisSweep3

  • Закрытые уровни с фиксированными размерами.
  • Небольшие сцены с предсказуемым движением.
  • Инженерные или архитектурные симуляции.

Внутренние аспекты работы широкой фазы

AABB обновление

При каждом шаге симуляции:

  1. Обновляется трансформация тела.
  2. Пересчитывается AABB.
  3. Широкая фаза обновляет структуру данных.

В динамических сценах именно этот этап становится критичным для производительности.

Фильтрация столкновений

Широкая фаза учитывает:

  • collision groups,
  • collision masks.

Пример добавления тела с группами:

dynamicsWorld.addRigidBody(body, group, mask);

Если маска не включает группу другого тела, пара не попадёт даже в широкую фазу.

Оптимизация производительности

1. Минимизация лишних тел

Статические объекты лучше объединять в compound shape или использовать один большой меш, чтобы сократить число AABB.

2. Разделение статических и динамических объектов

Bullet оптимизирует статические тела отдельно, что уменьшает количество проверок.

3. Контроль границ при btAxisSweep3

Границы мира должны:

  • охватывать максимальный возможный диапазон движения,
  • но не быть избыточными.

Память и управление ресурсами

Ammo.js требует ручного освобождения памяти:

Ammo.destroy(broadphase);

Аналогично необходимо освобождать:

  • btVector3,
  • btCollisionConfiguration,
  • btDispatcher,
  • btSolver.

Игнорирование освобождения приводит к утечкам памяти в WebAssembly.

Взаимодействие с узкой фазой

После того как широкая фаза определяет потенциальные пары:

  1. Они передаются в btCollisionDispatcher.
  2. Узкая фаза вычисляет точки контакта.
  3. Результаты поступают в solver.

Эффективность широкой фазы напрямую влияет на:

  • нагрузку узкой фазы,
  • стабильность симуляции,
  • общий FPS приложения.

Поведение в больших сценах

При числе тел > 10 000:

  • btDbvtBroadphase демонстрирует более устойчивое время шага.
  • btAxisSweep3 может испытывать рост времени сортировки.

В высоконагруженных симуляциях предпочтение обычно отдаётся DBVT.

Расширенные варианты

В Bullet существуют и другие реализации:

  • bt32BitAxisSweep3
  • btMultiSapBroadphase

Однако в Ammo.js чаще всего используются именно btDbvtBroadphase и btAxisSweep3, так как они полностью совместимы с типичным WebAssembly-пайплайном.

Архитектурное значение широкой фазы

Широкая фаза определяет:

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

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

Оглавление