Широкая фаза: BroadPhase и её алгоритмы

В физическом движке Oimo.js широкая фаза (BroadPhase) отвечает за предварительное выявление пар объектов, которые потенциально могут столкнуться. Она является первой ступенью процесса обнаружения столкновений и работает до того, как вычисляются точные контакты. Эффективная реализация BroadPhase критически важна для производительности симуляции, особенно при большом количестве тел.

Основные принципы BroadPhase

Широкая фаза не вычисляет точные столкновения. Её цель — сократить число пар для дальнейшей проверки в узкой фазе (NarrowPhase). Основная идея состоит в том, чтобы быстро определить, какие объекты могут пересекаться по пространству, используя упрощённые формы — обычно AABB (Axis-Aligned Bounding Box).

Ключевые задачи BroadPhase:

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

Представление объектов

В Oimo.js каждый объект сцены имеет привязанный body с физическим телом. Для BroadPhase строится AABB, который охватывает тело. Этот прямоугольный параллелепипед выравнивается по осям координат (X, Y, Z), что позволяет быстро проверять пересечения с другими AABB.

Структура AABB в Oimo.js:

{
    min: { x: Number, y: Number, z: Number },
    max: { x: Number, y: Number, z: Number }
}
  • min — минимальные координаты по каждой оси.
  • max — максимальные координаты по каждой оси.

Проверка пересечения двух AABB сводится к простому сравнению координат:

function aabbIntersect(a, b) {
    return (a.min.x <= b.max.x && a.max.x >= b.min.x) &&
           (a.min.y <= b.max.y && a.max.y >= b.min.y) &&
           (a.min.z <= b.max.z && a.max.z >= b.min.z);
}

Алгоритмы BroadPhase

В Oimo.js реализованы несколько методов широкофазного обнаружения столкновений. Основные из них:

1. Brute Force (Прямой перебор)

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

for (let i = 0; i < bodies.length; i++) {
    for (let j = i + 1; j < bodies.length; j++) {
        if (aabbIntersect(bodies[i].aabb, bodies[j].aabb)) {
            potentialPairs.push([bodies[i], bodies[j]]);
        }
    }
}

2. Sweep and Prune (SAP)

Sweep and Prune — оптимизированный метод, который использует проекцию AABB на оси координат. Основная идея:

  • Все объекты сортируются по координате (обычно X).
  • Проходя по отсортированному массиву, добавляются пары, если их проекции пересекаются.
  • Алгоритм работает эффективно, когда объекты двигаются плавно и сортировка почти отсортированного массива занимает O(n).

Этапы:

  1. Построение AABB для всех тел.
  2. Сортировка объектов по min.x.
  3. Итеративное сравнение с объектами, которые потенциально могут пересекаться.
  4. Добавление пары в список для узкой фазы.
bodies.sort((a, b) => a.aabb.min.x - b.aabb.min.x);

for (let i = 0; i < bodies.length; i++) {
    let a = bodies[i];
    for (let j = i + 1; j < bodies.length; j++) {
        let b = bodies[j];
        if (b.aabb.min.x > a.aabb.max.x) break; // выход из внутреннего цикла
        if (aabbIntersect(a.aabb, b.aabb)) potentialPairs.push([a, b]);
    }
}

Sweep and Prune позволяет существенно уменьшить количество проверок, особенно при линейном распределении объектов.

3. Spatial Hashing (Пространственная хеш-таблица)

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

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

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

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

  1. Определяется размер ячейки cellSize.
  2. Для каждой AABB вычисляется диапазон ячеек, которые она занимает.
  3. Все объекты, попавшие в одну ячейку, сравниваются между собой.
  4. Повторяется для всех занятых ячеек.
function getCellIndex(x, cellSize) {
    return Math.floor(x / cellSize);
}

4. BVH (Bounding Volume Hierarchy)

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

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

  • Эффективно для статичных сцен или объектов с малой подвижностью.
  • Снижает сложность до O(n log n) при поиске потенциальных пересечений.

Оптимизация BroadPhase

Для повышения производительности Oimo.js использует следующие приёмы:

  • Кэширование AABB: пересчитываются только для тел, которые изменили положение или размер.
  • Инкрементальная сортировка в SAP: при малых смещениях объектов массив почти отсортирован, что позволяет использовать алгоритмы типа вставочной сортировки.
  • Использование массивов typed arrays: ускоряет сортировку и перебор объектов за счёт оптимизации памяти и доступа.

Интеграция с узкой фазой

После BroadPhase формируется список потенциальных пар объектов. Этот список передается в узкую фазу, где:

  • Выполняются точные проверки столкновений с использованием геометрии тел.
  • Рассчитываются контактные точки, нормали и силы взаимодействия.

Сокращение числа пар на этапе BroadPhase напрямую снижает нагрузку на узкую фазу и повышает общую производительность симуляции.

Заключение по алгоритмам

  • Brute Force — прост, но медленный для больших сцен.
  • Sweep and Prune — оптимален для динамичных объектов с небольшими перемещениями.
  • Spatial Hashing — эффективен для плотного распределения объектов.
  • BVH — подходит для статических или слабо подвижных объектов, позволяет глубоко оптимизировать вычисления.

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

Оглавление