BVH-дерево как структура ускорения

Bounding Volume Hierarchy (BVH) — это иерархическая структура, используемая для ускорения вычислений столкновений в физических движках, таких как Oimo.js. Основная идея BVH заключается в том, чтобы сгруппировать объекты сцены в иерархию ограничивающих объёмов (bounding volumes), что позволяет быстро исключать объекты, которые не могут столкнуться друг с другом, без необходимости проверки каждой пары тел.

В Oimo.js BVH реализован для оптимизации broad-phase collision detection. На этом этапе движок определяет потенциальные пары объектов для более точного анализа на столкновение. Использование BVH существенно сокращает количество проверок, повышая производительность, особенно при большом количестве объектов.

Структура BVH

BVH-дерево представляет собой бинарное дерево, где каждый узел содержит ограничивающий объём, охватывающий все объекты в поддереве. Основные компоненты узла:

  • AABB (Axis-Aligned Bounding Box) — осе-ориентированный ограничивающий параллелепипед, который полностью содержит все тела поддерева.
  • Ссылки на потомков — левый и правый узел, представляющие разбиение объектов.
  • Список тел — хранится только в листовых узлах; содержит объекты сцены, которые непосредственно участвуют в столкновениях.

Ключевое свойство BVH: узлы и их потомки образуют иерархическую упаковку объектов, позволяющую быстро исключать целые группы тел при проверке столкновений. Если AABB узла не пересекается с AABB другого узла, нет необходимости проверять пересечения для всех объектов внутри этих поддеревьев.

Создание и обновление BVH

В Oimo.js BVH строится на основе текущих позиции и размеров тел. Основные шаги:

  1. Инициализация узлов: для каждого тела создаётся AABB.
  2. Сортировка объектов: объекты сортируются по выбранной оси (обычно X, Y или Z) для минимизации объёмов объединённых AABB.
  3. Рекурсивное разбиение: объекты делятся на две группы до тех пор, пока в листовых узлах не окажется минимальное количество тел (обычно 1 или 2).
  4. Обновление при движении: при каждом шаге симуляции AABB тел обновляются, что может потребовать перестройки дерева или локального пересчёта узлов.

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

Применение BVH в обнаружении столкновений

BVH участвует в broad-phase, определяя потенциальные пары объектов. Алгоритм работы:

  1. Начало с корневых узлов двух деревьев.

  2. Проверка пересечения их AABB.

  3. Если узлы пересекаются:

    • Рекурсивно проверяются пары потомков.
    • Листовые узлы формируют потенциальные пары тел для точной проверки столкновения (narrow-phase).

  4. Если AABB не пересекаются, все тела поддеревьев исключаются из дальнейшей проверки.

Эта стратегия снижает сложность с O(n²) для прямой проверки всех пар до O(n log n) в большинстве практических случаев.

Параметры оптимизации BVH

Эффективность BVH зависит от нескольких факторов:

  • Выбор оси разбиения: статический выбор оси X, Y, Z может быть простым, но использование SAH (Surface Area Heuristic) улучшает качество разбиения.
  • Минимальный размер листа: слишком маленький лист увеличивает глубину дерева, слишком большой — приводит к большему числу проверок в листе.
  • Динамическая перестройка: для быстрого перемещения объектов можно применять частичное обновление дерева, пересчитывая только изменённые узлы.

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

В Oimo.js BVH автоматически используется для всех тел, созданных через World.addBody(). Пример создания динамических тел:

const world = new OIMO.World();

const box1 = world.addBody({
  type: 'box',
  size: [1, 1, 1],
  pos: [0, 5, 0],
  move: true
});

const box2 = world.addBody({
  type: 'box',
  size: [1, 1, 1],
  pos: [0, 10, 0],
  move: true
});

world.step(); // обновление BVH и проверка столкновений

В этом коде BVH автоматически объединяет объекты в дерево, ускоряя broad-phase проверку столкновений между box1 и box2 и всеми другими телами в сцене.

Вывод о BVH

BVH является критически важным компонентом для производительности Oimo.js при больших сценах. Оно обеспечивает:

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

Правильная настройка и понимание структуры BVH позволяет создавать физические симуляции с высокой точностью и производительностью, особенно в интерактивных 3D-приложениях.

Оглавление