Bounding Volume Hierarchy

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

История

Идея использования иерархии объёмов-ограничителей для ускорения геометрических запросов возникла в 1970-х годах в рамках развития методов трассировки лучей (ray tracing) и алгоритмов обнаружения коллизий. Одним из первых опубликованных описаний BVH считается работа Джеймса Ф. Блинна (James F. Blinn) 1978 года, где он предложил использовать сферы как объёмы-ограничители для ускорения рендеринга. В 1980-х годах BVH получил широкое распространение в системах компьютерной анимации и физических симуляциях, особенно в контексте обнаружения столкновений между сложными объектами. Значительный вклад в развитие BVH внесли работы по построению сбалансированных деревьев и оптимизации алгоритмов обхода.

В 1990-е годы, с ростом вычислительных мощностей и развитием аппаратного ускорения трассировки лучей, BVH стал стандартной структурой данных в интерактивной компьютерной графике. В 2010-х годах компания NVIDIA (организация, зарегистрированная в США) внедрила аппаратную поддержку BVH в свои графические процессоры архитектуры Turing, что позволило выполнять трассировку лучей в реальном времени в играх и приложениях виртуальной реальности.

Классификация

BVH классифицируется по нескольким признакам:

По типу объёмов-ограничителей

• Сферические BVH — каждый узел содержит сферу, охватывающую все объекты поддерева. Просты в вычислении, но часто менее эффективны, чем прямоугольные объёмы.
• Осеориентированные прямоугольные параллелепипеды (AABB) — наиболее распространённый тип. AABB — это прямоугольник, выровненный по осям координат, что упрощает проверку пересечений.
• Ориентированные прямоугольники (OBB) — повёрнутые относительно осей, что позволяет точнее охватывать объекты произвольной формы, но требует больше вычислений.
• Выпуклые оболочки — используются для максимально точного охвата, но сложны в построении и проверке.

По способу построения

• Сверху вниз (top-down) — рекурсивное разбиение множества объектов на подмножества (например, по медиане координат). Простота реализации, но может давать несбалансированное дерево.
• Снизу вверх (bottom-up) — построение начинается с листьев (каждый объект — отдельный лист), затем узлы группируются. Требует больше времени, но часто даёт более качественную иерархию.
• Инкрементальное (insertion-based) — объекты добавляются по одному, дерево перестраивается локально. Используется в динамических сценах, где объекты движутся.

По степени ветвления

• Бинарное BVH — каждый узел имеет ровно два потомка. Наиболее распространённый вариант.
• N-арное BVH — узел может иметь более двух потомков (например, 4 или 8). Уменьшает глубину дерева, но увеличивает время проверки одного узла.

Устройство и характеристики

Структура узла

Каждый узел BVH хранит:

• Объём-ограничитель — геометрическая фигура, охватывающая все объекты поддерева.
• Ссылки на потомков — указатели на левый и правый дочерние узлы (для бинарного дерева).
• Список объектов — только для листьев; для внутренних узлов объекты хранятся в потомках.

Построение BVH

Алгоритм построения BVH сверху вниз (top-down) включает следующие шаги:

1. Выбор оси разбиения — обычно по оси с наибольшим разбросом координат объектов.
2. Разбиение множества — объекты сортируются по выбранной оси, и множество делится на две части (например, по медиане).
3. Рекурсия — для каждой части строится поддерево.
4. Вычисление объёма-ограничителя — для каждого узла вычисляется минимальный объём, охватывающий все объекты поддерева.

Обход BVH

Основная операция — поиск пересечения луча с объектами. Алгоритм обхода:

1. Начать с корня дерева.
2. Проверить пересечение луча с объёмом-ограничителем текущего узла.
3. Если пересечения нет — завершить обход для этого узла.
4. Если пересечение есть — рекурсивно обойти потомков (сначала ближайший, если луч не бесконечный).
5. В листьях проверить пересечение с каждым объектом.

Сложность

• Построение — в среднем O(N log N) для top-down, где N — количество объектов.
• Обход — в среднем O(log N) для одного луча, но в худшем случае O(N) (если все объёмы-ограничители пересекаются).
• Память — O(N) узлов (для бинарного дерева — примерно 2N узлов).

Применение

Трассировка лучей (Ray Tracing)

BVH является стандартной структурой для ускорения трассировки лучей в рендеринге. Используется в:

• Интерактивной графике — в играх и приложениях виртуальной реальности (например, в технологии NVIDIA RTX).
• Офлайн-рендеринге — в программах Blender, Autodesk Maya, Cinema 4D.
• Научной визуализации — для визуализации сложных трёхмерных данных.

Обнаружение коллизий (Collision Detection)

В физических симуляциях и игровых движках BVH применяется для быстрого определения столкновений между объектами. Например, в движке PhysX (NVIDIA) и Bullet Physics.

Обработка облаков точек

BVH используется для ускорения запросов ближайших соседей и поиска пересечений в больших наборах трёхмерных точек.

Вычислительная геометрия

Применяется для задач, связанных с пространственными запросами, таких как поиск объектов в заданной области или определение видимости.

Примеры реализации

В игровых движках

• Unreal Engine — использует BVH для ускорения трассировки лучей в реальном времени (Lumen, Nanite).
• Unity — поддерживает BVH для физических симуляций и рендеринга (High Definition Render Pipeline).

В библиотеках

• Embree (Intel) — библиотека для трассировки лучей, использующая BVH.
• OptiX (NVIDIA) — фреймворк для трассировки лучей с аппаратным ускорением BVH.
• PBRT — учебный рендерер, реализующий BVH.

В научных проектах

• Open3D — библиотека для обработки трёхмерных данных, включающая построение BVH.
• CGAL (Computational Geometry Algorithms Library) — содержит реализации BVH для геометрических запросов.

Критика и ограничения

• Перекрытие объёмов — в отличие от k-d дерева или октодерева, BVH допускает перекрытие объёмов-ограничителей, что может снижать эффективность обхода.
• Динамические сцены — при движении объектов BVH требует перестроения или обновления, что может быть затратно по времени.
• Память — для сложных сцен с миллионами объектов BVH может потреблять значительный объём памяти (особенно при хранении AABB для каждого узла).
• Качество построения — эффективность BVH сильно зависит от алгоритма разбиения; плохое разбиение может привести к O(N) обходу.

Источники

• Blinn, J. F. (1978). Simulation of Wrinkled Surfaces. Computer Graphics (SIGGRAPH '78 Proceedings).
• Goldsmith, J., & Salmon, J. (1987). Automatic Creation of Object Hierarchies for Ray Tracing. IEEE Computer Graphics and Applications.
• Wald, I., & Havran, V. (2006). On building fast kd-trees for ray tracing, and on doing that in O(N log N). Proceedings of the IEEE Symposium on Interactive Ray Tracing.
• Pharr, M., Jakob, W., & Humphreys, G. (2016). Physically Based Rendering: From Theory to Implementation (3rd ed.). Morgan Kaufmann.
• NVIDIA Corporation. (2018). NVIDIA Turing GPU Architecture. NVIDIA Whitepaper.