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

Oimo.js — это лёгкая физическая библиотека для JavaScript, ориентированная на симуляцию твёрдого тела и обработку столкновений. Ключевым компонентом любой физической симуляции является система обнаружения столкновений. В Oimo.js она реализована через двухфазный подход, включающий широкую (broad-phase) и узкую (narrow-phase) фазы. Каждая из них решает отдельные задачи и оптимизирует процесс вычислений.

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

Широкая фаза предназначена для предварительного фильтрования потенциально пересекающихся объектов. Главная цель — снизить количество пар, которые нужно проверять более детально, так как проверка всех объектов по принципу «каждый со всеми» приводит к экспоненциальному росту вычислений при увеличении числа тел.

Основные принципы работы:

  • Используется упрощённая геометрическая аппроксимация объектов, чаще всего оси-ориентированные ограничивающие прямоугольники (AABB — Axis-Aligned Bounding Box).
  • Вычисляется пересечение этих AABB. Если AABB двух объектов не пересекаются, дальнейшие проверки исключаются.
  • Oimo.js применяет структуры данных для ускорения поиска, например, spatial hashing или сортировку по осям (sweep and prune).

Sweep and Prune:

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

Преимущества широкого этапа:

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

Узкая фаза (Narrow Phase)

После того как широкая фаза выявила пары потенциально пересекающихся объектов, наступает узкая фаза — точная проверка столкновений. Здесь учитываются конкретные формы объектов, их ориентация и размер. В Oimo.js поддерживаются следующие базовые типы коллайдеров:

  • Box — параллелепипед, проверка пересечения по осям.
  • Sphere — проверка расстояния между центрами относительно радиусов.
  • Cylinder и Capsule — вычисление ближайшего расстояния между линиями или сегментами.
  • Convex Mesh — метод Гурвиц-Кардана или SAT (Separating Axis Theorem).

Особенности узкой фазы:

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

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

Широкая и узкая фазы неразрывно связаны:

  1. Инициализация AABB всех объектов.
  2. Широкая фаза выбирает пары для узкой проверки.
  3. Узкая фаза детально проверяет выбранные пары и формирует контактные данные.
  4. Решение столкновений — вычисление импульсов и сил на основе контактных точек.

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

Оптимизация и практические советы

  • Актуализация AABB: при движении объектов нужно своевременно обновлять ограничивающие коробки, иначе широкая фаза может пропустить столкновения.
  • Размер ячеек при spatial hashing: слишком маленькие ячейки создают множество пустых проверок, слишком большие — увеличивают количество ложных пересечений.
  • Кэширование контактов: для объектов, которые движутся медленно или находятся в покое, можно сохранять предыдущие контакты и проверять их в первую очередь.
  • Фильтры коллизий: можно использовать маски и группы, чтобы исключить столкновения между объектами, которым не нужно взаимодействовать.

Роль фаз в производительности

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

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

Заключение

Двухфазная система обнаружения столкновений в Oimo.js позволяет эффективно комбинировать производительность и точность. Широкая фаза фильтрует множество потенциальных взаимодействий, минимизируя нагрузку, а узкая фаза обеспечивает корректную физическую реакцию объектов. Глубокое понимание работы каждой из фаз и их оптимизация позволяет создавать сложные и реалистичные физические симуляции на JavaScript.

Оглавление