Иерархии объемов (BVH)

Суббота, 10 августа 2024 г. / Просмотров: 192

"The first tenet of optimization is that nothing is faster than not having to perform a task in the first place." [Real-Time Collision Detection – Christer Ericson]

Введение

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

Вариант визуализации BVH (только листовые узлы) в среде Analysis Situs.

Построение эффективной ускоряющей структуры для лучевых алгоритмов — это сложная исследовательская проблема. Заинтересованного читателя мы отсылаем к диссертации Д.К. Боголепова [1], особенно к ее разделу 3.1. Отметим здесь ключевые моменты.

Среди ускоряющих структур принято выделять:

Структуры разбиения пространства (такие как воксели или k-d деревья).
Структуры разбиения объекта (такие как иерархии ограничивающих объемов).

Иерархия объемов (англ. Bounding Volume Hierarchy, BVH) в классическом исполнении представляет собой дерево выровненных параллелепипедов, заключающих некоторый объект, подлежащий трассировке. Мы используем термин «трассируемый объект» условно, поскольку в действительности применение BVH в задачах геометрического моделирования далеко не ограничивается лучевыми методами визуализации. Напротив, как мы заметили в самом начале, привлечение механизма BVH оказывается удивительно плодотворным в задачах, едва ли имеющих отношение к компьютерной графике в узком смысле (т.е. к рендерингу объектов). Нам доводилось использовать BVH для решения, например, следующих задач:

Нахождение скрытых объектов сцены (коммерциализовано в нашем приложении BitterCut).
Проецирование точек и сегментов линий на триангуляцию для интерактивного задания контура.
Сэмплирование граничного представления модели для ее преобразования в облако точек.
Создание поля дистанций для модели в граничном представлении.
Детектирование коллизий.
Измерение расстояния между объектами.
Детектирование самопересечений.
Совмещение облака точек с CAD-моделью (задача регистрации).

Помимо указанного, структуры BVH используются в библиотеке OpenCascade как для трассировки лучей (то есть, непосредственно по назначению), так и для интерактивной селекции в AIS (Application Interactive Services).

Модель ANC101 и ее BVH. Красным показаны левые дочерние элементы бинарного дерева, зеленым — правые.

Словом, BVH — это универсальный инструмент вычислительной геометрии, эффективный для решения разнообразных алгоритмических задач. Ниже мы поговорим о реализации и применении структур BVH в составе библиотеки геометрического моделирования OpenCascade.

Реализация

В конце 2013-го года в библиотеке OpenCascade поселился пакет BVH (благодаря Боголепову Д.К. [1], см. также рендерер [2]), реализующий базовую структуру данных и пару стратегий ее построения: «линейную» и «ячеистую» на основе SAH (Surface Area Heuristic). Теперь этот пакет используется повсеместно как в самой библиотеке, так и в ее приложениях. Появление BVH стало, пожалуй, одним из наиболее концептуальных нововведений в ядре за многие годы. Дело, конечно, не в том, что иерархии ограничивающих объемов оказались волшебной пилюлей. Напротив, ничего особенного в применении специальных структур данных для ускорения вычислений в геометрических ядрах нет — тесты на пересечения с габаритными объемами используются в графических библиотеках повсеместно, и в OpenCascade вместо BVH долгое время были адаптированы другие структуры данных, например, UB-деревья. Оказалось, однако, что именно ускоряющая структура трассировщика лучей является наиболее эффективным, универсальным и удобным инструментом для оптимизации старых и создания новых алгоритмов. Не будет преувеличением сказать, что здесь мы наблюдаем синергию бурно развивающейся компьютерной графики и консервативного геометрического моделирования. Читатель может самостоятельно ознакомиться с составом пакета BVH в ядре OpenCascade (библиотека TKMath). Рассмотрим лишь ключевые аспекты использования этой ускоряющей структуры на CPU (реализацию для графических процессоров оставим специалистам).

BVH — это (как правило) бинарное дерево вложенных габаритов (axis-aligned bounding boxes, AABB). Реализация BVH в OpenCascade выглядит немного сложно, вероятно, из-за того, что архитектура дерева прошла длинный путь из академических стен университета Лобачевского и затачивалась под графические процессоры, в то время как библиотека OpenCascade, конечно, ориентирована исключительно на центральный процессор (CPU). Само дерево состоит из вложенных кортежей по 4 элемента в каждом: x, y, z, w (как в однородных координатах). Интерпретация элементов кортежа зависит от того, является ли соответствующий узел дерева листовым или промежуточным.

========================================================
 coord |         leaf        |        sub-volume       |
========================================================
   x   |          !0         |             0           |
-------+---------------------+-------------------------+
   y   | idx of 1-st element | idx of left child node  |
-------+---------------------+-------------------------+
   z   | idx of last element | idx of right child node |
-------+---------------------+-------------------------+
   w   |      depth of the node in the BVH tree        |
========================================================

Расшифруем шпаргалку, данную выше:

x — признак того, является ли данный узел листовым (1) или промежуточным (0).
y — индекс левого дочернего узла или первого геометрического примитива, если текущий узел является листовым.
z — индекс правого дочернего узла или последнего геометрического примитива, если текущий узел является листовым.
w — глубина вложенности данного узла.

Каждый промежуточный (НЕ листовой) узел BVH соответствует габаритному параллелепипеду, содержащему все объекты, находящиеся иерархически ниже данного узла. Поскольку дерево бинарное, то, спускаясь в глубину, мы увидим, что количество узлов прибавляется как степень двойки, однако в какой-то момент дерево перестает ветвиться, и мы достигаем обернутых геометрических примитивов «живьем». Анимация ниже показывает вид каждого уровня BVH при спуске в глубину (габаритные бруски исчезают по достижении листьев дерева):

Неотъемлемым качеством BVH, в отличие от структур пространственного разбиения, является неоднозначность представления точек пространства: габариты имеют взаимные наложения, чего нет, например, в октодеревьях. Важными же достоинствами структур типа BVH (то есть разбиений не пространства, а объекта) является их компактность по памяти и отличная производительность на построении, особенно в случае линейного алгоритма (LBVH).

Построение дерева

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

class GeomTriangleSet : public BVH_PrimitiveSet<double, 3>
{
  ...
};

Новый тип GeomTriangleSet — это, с одной стороны, адаптор между структурами данных нашего приложения и библиотекой OpenCascade, а с другой — собственно BVH. Триангуляция в конечно-пользовательском приложении может быть представлена в любом удобном нам виде, и требуется лишь обеспечить конвертацию этого типа в формат, употребимый геометрическим ядром. Базовый класс BVH_PrimitiveSet объявляет чисто виртуальные методы, которые требуется реализовать в классе-наследнике:

int Size() const возвращает количество треугольников в структуре данных.
BVH_Box Box(const int index) const возвращает габаритный параллелепипед треугольника с индексом index.
T Center(const int index, const int axis) const возвращает геометрический центр треугольника с индексом index по X (axis == 0), Y (axis == 1) или Z (axis == 2).
void Swap(const int index1, const int index2) меняет местами треугольники с индексами index1 и index2.

По существу BVH_PrimitiveSet — это список примитивов, допускающий перестановки и отдаваемый алгоритмам построения и обхода BVH как входные данные. Алгоритм построения BVH («ячеистый» или «линейный») вызывает виртуальные методы, определенные выше, для пространственной сортировки объектов тем или иным способом. Вообще, построение BVH оптимальным (для задач трассировки) способом считается NP-полной задачей, поэтому алгоритмы построения, реализованные в OpenCascade, являются, конечно, эвристическими.

Конструирование BVH из примитивов откладывается до первого вызова метода BVH_PrimitiveSet::BVH(). Таким образом, наполнение коллекции примитивов и собственно построение дерева — процессы, вообще говоря, разнесенные во времени.

Перестроение BVH на деформируемой модели листового металла в процессе развертки.

Эвристических способов разбиения набора примитивов на иерархию объемов можно придумать много, но в библиотеке OpenCascade реализованы две стратегии: «ячеистая» (binned) и «линейная» (linear). При этом «ячеистая» стратегия является, как правило, предпочтительной и, что интересно, на момент написания этой заметки, «линейная» стратегия, хотя и оставалась работоспособной, но не позволяла отследить глубину узла дерева, т.е. компонент w узлового кортежа в итоговом дереве всегда оставался равным нулю. Данное обстоятельство не влияет на работоспособность BVH, но осложняет визуальную инспекцию «линейного» дерева в среде Analysis Situs.

Фрезерная деталь и два варианта BVH.

Обход дерева

За обход дерева в среде Analysis Situs отвечает класс-итератор asiAlgo_BVHIterator. Надо сказать, что разработчики OpenCascade тоже (спустя много лет после появления BVH в библиотеке) добавили похожий класс BVH_Traverse для унификации обхода дерева с проверкой некоторого критерия отсева габаритных блоков. Последний итератор задействован в булевых операциях, а также в паре других низкоуровневых алгоритмов библиотеки (Extrema, OBB).

Алгоритм обхода спускается по бинарному дереву в глубину, на каждом шаге позволяя «блокировать» левую или правую ветвь дерева, в зависимости от того, выполняется ли в соответствующем габаритном параллелепипеде условие отсева. Алгоритмы, привлекающие BVH в качестве вспомогательных структур данных, как правило, строятся на логике обхода дерева с различными условиями блокировки ветвей. Так, логика пересечения луча и триангуляции по существу состоит в следующем цикле:

// Traverse BVH.
for ( asiAlgo_BVHIterator it(bvh); it.More(); it.Next() )
{
  const BVH_Vec4i& nodeData = it.Current();
  
  if ( it.IsLeaf() )
  {
    // If we are here, then we are close to solution. It is a right
    // time now to perform a precise check.
    
    /* precise intersection test goes here */
  }
  else // sub-volume.
  {
    const BVH_Vec3d& minCorner_Left  = bvh->MinPoint( nodeData.y() );
    const BVH_Vec3d& maxCorner_Left  = bvh->MaxPoint( nodeData.y() );
    const BVH_Vec3d& minCorner_Right = bvh->MinPoint( nodeData.z() );
    const BVH_Vec3d& maxCorner_Right = bvh->MaxPoint( nodeData.z() );
    
    const bool isLeftOut  = IsOut(ray, minCorner_Left, maxCorner_Left, precision);
    const bool isRightOut = IsOut(ray, minCorner_Right, maxCorner_Right, precision);
    
    if ( isLeftOut )
      it.BlockLeft();
    if ( isRightOut )
      it.BlockRight();
  }
}

На каждой итерации проверяем, был ли достигнут листовой узел дерева. Если да, то выполняем алгоритм точного пересечения луча и набора треугольников, заключенного в листовом параллелепипеде. Если нет, то снимаем с текущего элемента его дочерние узлы и выполняем проверку пересечения луча и выровненного параллелепипеда для выяснения критерия отсева. В зависимости от результата, блокируем итерации на левом поддереве (BlockLeft()), правом поддереве (BlockRight()) или обоих сразу.

Открытые вопросы

Алгоритмы построения BVH, реализованные в библиотеке OpenCascade, быстры и эффективны. При этом сцена предполагается статичной, то есть набор примитивов, разбиваемый на выровненные параллелепипеды, моделируется один раз и в этом виде используется в трассировке (или любом другом алгоритме с использованием обхода дерева). Предположим теперь, что сцена меняется динамически, например, мы моделируем какой-то производственный процесс, скажем, фрезеровку или гиб листового металла. На каждом шаге набор примитивов видоизменяется, и иерархия объемов должна перестраиваться заново. Как указано в разделе 5.3.1 обзорной работы D. Meister et al. [3], для «динамической геометрии» может оказаться разумным подход «подстраивания» BVH, особенно, если используется ресурсоемкий алгоритм построения дерева. Способы подстраивания BVH под динамические сцены представляют, с нашей точки зрения, большой практический интерес.

Библиография

Боголепов, Д.К. 2013. Методы глобального освещения для интерактивного синтеза изображений сложных сцен на графических процессорах (full text).
Light Tracer Render (www.lighttracer.org).
Meister, Daniel & Ogaki, Shinji & Benthin, Carsten & Doyle, Michael & Guthe, Michael & Bittner, Jiri. (2021). A Survey on Bounding Volume Hierarchies for Ray Tracing. Computer Graphics Forum. 40. 683-712 (full text).

Want to discuss this? Jump in to our forum.