Введение
Иерархия ограничивающих объемов (BVH) — это древовидная структура, построенная над набором геометрических объектов. Все геометрические объекты, формирующие листовые узлы дерева, заключены в ограничивающие объемы. Эти узлы затем группируются в небольшие наборы и помещаются внутрь более крупных ограничивающих объемов. Эти, в свою очередь, также группируются и заключаются в еще более крупные ограничивающие объемы рекурсивно, что в конечном итоге приводит к образованию древовидной структуры с одним ограничивающим объемом на вершине. Иерархии ограничивающих объемов используются для эффективной поддержки различных операций над наборами геометрических объектов, таких как обнаружение столкновений и трассировка лучей. Хотя заключение объектов в ограничивающие объемы и выполнение тестов на столкновение с ними перед проверкой самой геометрии объекта упрощает тесты и может значительно повысить производительность, количество парных тестов между ограничивающими объемами остается прежним. Организуя ограничивающие объемы в иерархию ограничивающих объемов, можно снизить временную сложность (количество выполняемых тестов) до логарифмической зависимости от количества объектов. При наличии такой иерархии, при проверке на столкновение нет необходимости проверять дочерние объемы, если их родительские объемы не пересекаются (например, если ограничивающие объемы двух автомобилей не пересекаются, то нет необходимости проверять на столкновение ограничивающие объемы самих автомобилей).
A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, which form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing. Although wrapping objects in bounding volumes and performing collision tests on them before testing the object geometry itself simplifies the tests and can result in significant performance improvements, the same number of pairwise tests between bounding volumes are still being performed. By arranging the bounding volumes into a bounding volume hierarchy, the time complexity (the number of tests performed) can be reduced to logarithmic in the number of objects. With such a hierarchy in place, during collision testing, children volumes do not have to be examined if their parent volumes are not intersected (for example, if the bounding volumes of two bumper cars do not intersect, the bounding volumes of the bumpers themselves would not have to be checked for collision).
Строительство
Существует три основные категории методов построения деревьев: сверху вниз, снизу вверх и методы вставки. Методы сверху вниз работают, разделяя входной набор на два (или более) подмножества, заключая их в выбранный ограничивающий объем, а затем рекурсивно продолжают разделять (и заключать в объем), пока каждое подмножество не будет состоять только из одного примитива (достигаются листовые узлы). Методы сверху вниз просты в реализации, быстро строятся и, безусловно, являются самыми популярными, но обычно не приводят к построению оптимальных деревьев. Методы снизу вверх начинают с входного набора, рассматриваемого как листья дерева, а затем группируют два (или более) из них для формирования нового (внутреннего) узла, продолжая в том же духе, пока все элементы не будут сгруппированы под одним узлом (корнем дерева). Методы снизу вверх сложнее в реализации, но, как правило, позволяют получить более качественные деревья. Некоторые недавние исследования показывают, что в пространствах низкой размерности скорость построения может быть значительно увеличена (сопоставима или превосходит методы сверху вниз) за счет сортировки объектов с использованием кривой, заполняющей пространство, и последующего применения приближенного кластеризования на основе этого последовательного порядка. Методы сверху вниз и снизу вверх считаются методами пакетной обработки, поскольку оба требуют наличия всех примитивов до начала построения. Методы вставки строят дерево, последовательно вставляя объекты, начиная с пустого дерева. Место вставки должно выбираться таким образом, чтобы минимизировать рост дерева согласно выбранной метрике стоимости. Методы вставки считаются методами онлайн-обработки, поскольку они не требуют наличия всех примитивов до начала построения и, следовательно, позволяют выполнять обновления во время работы.
Использование
BVH часто используются в трассировке лучей для исключения потенциальных кандидатов на пересечение в сцене, отбрасывая геометрические объекты, находящиеся в ограничивающих объемах, которые не пересекаются с текущим лучом. Кроме того, в качестве обычной оптимизации производительности, когда интересует только ближайшее пересечение луча, алгоритм обхода трассировки лучей, спускаясь по узлам, и при пересечении луча с несколькими дочерними узлами, сначала рассматривает ближайший объем. Если в нем найдено пересечение, которое однозначно ближе, чем любое возможное пересечение во втором (или другом) объеме (то есть объемы не перекрываются), второй объем можно безопасно игнорировать. Аналогичные оптимизации при обходе BVH могут применяться при спуске в дочерние объемы второго объема, чтобы ограничить область поиска и, следовательно, сократить время обхода. Для BVH также разработано множество специализированных методов, особенно основанных на AABB (axis aligned bounding boxes), таких как параллельное построение, обход с ускорением SIMD, эффективные эвристики разбиения (евристика площади поверхности SAH часто используется в трассировке лучей), широкие деревья (4-ичные и 16-ичные деревья обеспечивают определенные преимущества в производительности как при построении, так и при запросах для практических сцен), и быстрое обновление структуры (в приложениях реального времени объекты могут перемещаться или деформироваться в пространстве относительно медленно или оставаться неподвижными, и тот же BVH можно обновить, сохранив его валидность без полной перестройки с нуля). BVH также естественным образом поддерживают вставку и удаление объектов без полной перестройки, но результирующий BVH обычно имеет более низкую производительность запросов по сравнению с полной перестройкой. Для решения этих проблем (а также из-за неоптимальности быстрого обновления структуры) новый BVH может быть построен асинхронно параллельно или синхронно после обнаружения существенных изменений (большое перекрытие листьев, превышение порогового значения количества вставок и удалений, и другие более точные эвристики). BVH также можно комбинировать с методами графа сцены и инстанцированием геометрии для уменьшения использования памяти, повышения производительности обновления структуры и полной перестройки, а также для более эффективного разбиения объектов или примитивов.