Широкофазовые алгоритмы: NaiveBroadphase, SAPBroadphase, GridBroadphase

В физическом движке Cannon.js широкофазовые алгоритмы (broadphase) используются для эффективного определения потенциальных столкновений между телами в симуляции. Их основная задача — сократить количество проверок столкновений, передаваемых в узкофазный алгоритм (narrowphase), который выполняет точные вычисления пересечений. Без широкофазной фильтрации проверка всех возможных пар тел растёт квадратично (O(n^2)), что делает симуляцию неэффективной при большом количестве объектов.

Cannon.js предоставляет три основных широкофазовых алгоритма: NaiveBroadphase, SAPBroadphase и GridBroadphase. Каждый из них имеет свои особенности и применимость.

NaiveBroadphase

NaiveBroadphase — самый простой и прямолинейный алгоритм широкофазы. Он проверяет все возможные пары тел на потенциальные столкновения без какой-либо оптимизации.

Особенности:

  • Прямой перебор всех пар: Для n объектов выполняется проверка (n (n-1) / 2) пар.
  • Простота реализации: Не требует дополнительной структуры данных.
  • Используется для небольших сцен: Хорошо подходит для обучения или тестов с десятками объектов.

Пример создания:

const world = new CANNON.World();
world.broadphase = new CANNON.NaiveBroadphase();

Ограничения:

  • С увеличением числа тел производительность падает квадратично.
  • Невозможность масштабирования для больших симуляций.

SAPBroadphase

SAPBroadphase (Sweep and Prune) — алгоритм широкофазы, основанный на сортировке проекций тел на выбранной оси. Основная идея: объекты далеко друг от друга по координате не могут пересекаться, поэтому можно быстро отбрасывать большинство пар.

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

  1. Выбирается основная ось (например, X).
  2. Все тела сортируются по минимальной координате на этой оси.
  3. Пары проверяются только среди объектов с пересекающимися проекциями.

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

  • Снижает количество проверок до (O(n n + k)), где k — число потенциальных столкновений.
  • Эффективен для длинных сцен с ограниченной плотностью тел.
  • Простая реализация в Cannon.js и низкая память для хранения структуры.

Пример использования:

const world = new CANNON.World();
world.broadphase = new CANNON.SAPBroadphase(world);
world.broadphase.axisIndex = 0; // выбор оси X

Особенности настройки:

  • axisIndex — определяет, по какой оси происходит сортировка (0 — X, 1 — Y, 2 — Z).
  • Эффективность сильно зависит от распределения объектов: для равномерно распределённых объектов по всем осям SAP может быть не столь эффективен.

GridBroadphase

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

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

  1. Задаются границы пространства и размер ячеек (aabbMin, aabbMax, nx, ny, nz).
  2. Каждое тело помещается в соответствующую ячейку на основе координат.
  3. Проверяются пары тел только внутри ячеек и соседних ячеек.

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

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

Пример использования:

const world = new CANNON.World();
world.broadphase = new CANNON.GridBroadphase(
    new CANNON.Vec3(-100, -100, -100),
    new CANNON.Vec3(100, 100, 100),
    10, 10, 10
);

Особенности настройки:

  • Размер сетки критически влияет на производительность: слишком маленькие ячейки увеличивают количество соседних проверок, слишком большие — увеличивают количество объектов внутри одной ячейки.
  • Рекомендуется подбирать сетку исходя из среднего размера объектов и плотности сцены.

Сравнение алгоритмов

Алгоритм Сложность Применение Плюсы Минусы
NaiveBroadphase O(n²) Малые сцены Простота, точность Плохо масштабируется
SAPBroadphase O(n log n + k) Линейные или вытянутые сцены Быстро для умеренных сцен Зависит от оси сортировки
GridBroadphase O(n + k’) Частицы, равномерные сцены Отлично для больших чисел тел Требует настройки сетки

Выбор алгоритма зависит от размеров сцены, распределения объектов и требуемой производительности. Для небольших учебных примеров подходит NaiveBroadphase, для длинных сцен с небольшим числом объектов — SAPBroadphase, для массивов мелких частиц — GridBroadphase.

Рекомендации по оптимизации

  • Использовать SAP или Grid вместо Naive для больших сцен.
  • Настраивать параметры сетки или оси сортировки исходя из размеров объектов.
  • Ограничивать количество активных тел и использовать sleep для неподвижных объектов.
  • Периодически пересматривать настройки broadphase при динамическом изменении сцены.

Эффективное использование широкофазовых алгоритмов позволяет значительно ускорить симуляцию и снизить нагрузку на узкофазный движок столкновений Cannon.js.

Оглавление