Широкофазовое и узкофазовое обнаружение столкновений

Cannon.js — это физический движок для JavaScript, реализующий твердотельную динамику, включая столкновения, силы, инерцию и пружинные связи. Одной из ключевых задач любого физического движка является обнаружение столкновений, которое в Cannon.js разделено на два этапа: широкофазовое (broadphase) и узкофазовое (narrowphase) обнаружение. Такой подход позволяет повысить производительность и точность симуляции.

Широкофазовое обнаружение (Broadphase)

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

Основные задачи

  • Сократить количество проверок столкновений между объектами.
  • Обеспечить высокую производительность при работе с большим количеством тел.

Реализации в Cannon.js

Cannon.js поддерживает несколько алгоритмов широкофазового обнаружения:

  1. NaiveBroadphase

    • Проверяет каждую пару объектов на возможное пересечение O(n²).
    • Подходит для небольших сцен с малым количеством тел.
    • Простая реализация, не требует дополнительных структур данных.

  2. SAPBroadphase (Sweep and Prune)

    • Использует осьную сортировку объектов по координатам.
    • Эффективен для сцен с большим количеством объектов.
    • Работает по принципу: если два AABB (axis-aligned bounding box) не пересекаются по выбранной оси, дальнейшие проверки не требуются.
const world = new CANNON.World();
world.broadphase = new CANNON.SAPBroadphase(world);
world.broadphase.axisIndex = 0; // сортировка по X-оси

Выбор Broadphase

  • NaiveBroadphase подходит для учебных проектов и тестов.
  • SAPBroadphase предпочтителен для динамических игр и симуляций с десятками и сотнями тел.

Узкофазовое обнаружение (Narrowphase)

После определения потенциальных пар объектов широкофазовым этапом, Cannon.js выполняет узкофазовую проверку, которая вычисляет:

  • Точные точки контакта.
  • Нормали столкновения.
  • Глубину проникновения объектов.

Алгоритмы узкофазового столкновения

Cannon.js реализует несколько типов коллайдеров:

  1. Сферы (Sphere)

    • Проверка столкновения двух сфер сводится к вычислению расстояния между центрами.
    • Если расстояние меньше суммы радиусов, создается контакт.

  2. Коробки (Box)

    • Используется алгоритм Separating Axis Theorem (SAT).
    • Проверяются все оси, нормальные к граням и рёбрам, на наличие разделяющей плоскости.

  3. Капсулы, цилиндры, конусы и полигоны

    • Для сложных форм используется комбинация SAT и специальных эвристик.
    • Контактные точки и нормали вычисляются с учетом точной геометрии.

Создание контакта

Контакт представляет собой объект с параметрами:

  • bi, bj — столкнувшиеся тела.
  • ni — нормаль столкновения, направленная от bi к bj.
  • ri, rj — точки на телах относительно центра масс.
  • penetration — глубина проникновения.
world.addEventListener('postStep', () => {
  world.contacts.forEach(contact => {
    console.log(contact.bi.id, contact.bj.id, contact.penetration);
  });
});

AABB и BVH

Для ускорения столкновений Cannon.js использует AABB (Axis-Aligned Bounding Box):

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

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

Настройка производительности

  1. Увеличение шага интеграции снижает количество проверок, но ухудшает точность.
  2. Использование SAPBroadphase для динамических сцен с большим количеством объектов.
  3. Объединение статических объектов в один меш уменьшает число проверок столкновений.
  4. Использование простых коллайдеров (сферы, коробки) для сложных объектов с визуальной детализацией через меши.

События столкновений

Cannon.js позволяет подписываться на события столкновений:

  • collide — при начале контакта двух тел.
  • collideBegin и collideEnd — для детальной обработки фаз столкновения.
bodyA.addEventListener('collide', function(e) {
  console.log('Столкновение с', e.body.id, 'на точке', e.contact.rj);
});

Это позволяет создавать реакции на столкновения: звук, эффект, изменение состояния объекта.

Интеграция с Three.js

Для визуализации столкновений часто используют комбинацию Cannon.js и Three.js:

  • Геометрия Three.js отображает тело,
  • Cannon.js вычисляет физику.
  • Синхронизация выполняется каждый кадр:
mesh.position.copy(body.position);
mesh.quaternion.copy(body.quaternion);

Такой подход позволяет использовать точные физические столкновения, сохраняя высокую производительность рендеринга.

Заключение по фазам

  • Широкофазовое обнаружение экономит ресурсы, исключая очевидно не столкнувшиеся пары.
  • Узкофазовое обнаружение обеспечивает точность физики, вычисляя реальные точки контакта.
  • Правильное сочетание алгоритмов и структур данных повышает производительность и позволяет создавать сложные сцены с большим количеством динамических объектов.
Оглавление