Иерархия ограничивающих объёмов (Nyjgj]nx kijguncnfgZpn] kQa~bkf)

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

Хотя помещение объектов в ограничивающие объемы и выполнение на них проверок на столкновение перед проверкой самой геометрии объекта упрощает тесты и может привести к значительному повышению производительности, по-прежнему выполняется такое же количество парных тестов между ограничивающими объемами. Организовав ограничивающие объемы в иерархию ограничивающих объемов, временную сложность (количество выполненных тестов) можно уменьшить до логарифмического числа объектов. При наличии такой иерархии во время проверок на столкновение не нужно проверять дочерние объемы, если их родительские объемы не пересекаются (например, если ограничивающие объемы двух автомобилей не пересекаются, ограничивающие объемы их бамперов сами по себе не нужно проверять на столкновение).

Проблемы выбора BVH

Выбор ограничивающего объема определяется компромиссом между двумя целями. С одной стороны, мы хотели бы использовать ограничивающие объемы очень простой формы. Таким образом, нам нужно всего несколько байтов для их хранения, а проверки на пересечения и вычисления расстояний выполняются просто и быстро. С другой стороны, нам хотелось бы иметь ограничивающие объемы, которые бы очень плотно соответствовали соответствующим объектам данных. Один из наиболее часто используемых ограничивающих объемов - это выровненный по осям минимальный ограничивающий параллелепипед (AABB). AABB для заданного набора объектов данных легко вычисляется, требуется всего несколько байт памяти, и надежные проверки на пересечения легко реализуются и выполняются очень быстро.

Существует несколько желаемых свойств BVH, которые следует учитывать при проектировании для конкретного применения^[1]:

Узлы, содержащиеся в любом поддереве, должны находиться рядом друг с другом. Чем ниже дерево, тем ближе должны быть узлы друг к другу.
Каждый узел в BVH должен быть минимального объема.
Сумма всех ограничивающих объемов должна быть минимальной.
Большее внимание следует уделять узлам вблизи корня BVH. Удаление узла рядом с корнем дерева позволяет исключить из рассмотрения большее количество объектов.
Объем перекрытия родственных узлов должен быть минимальным.
BVH должен быть сбалансирован как по структуре узлов, так и по содержанию. Балансировка позволяет обрезать как можно большую часть BVH всякий раз, когда ветвь не пересекается.

Что касается структуры BVH, необходимо решить, какую степень (количество дочерних элементов) и высоты использовать в дереве, представляющем BVH. Дерево низкой степени будет большей высоты. Это увеличивает время прохождения от корня к листу. С другой стороны, на каждом посещенном узле требуется затрачивать меньше работы на проверку его дочерних узлов на предмет перекрытия. Для дерева высокой степени справедливо обратное: хотя дерево будет меньшей высоты, на каждом узле затрачивается больше работы. На практике бинарные деревья (степень = 2) являются наиболее распространенными. Одна из основных причин заключается в том, что бинарные деревья легче строить^[2].

Построение

Существует три основные категории методов построения деревьев: методы сверху вниз, снизу вверх и методы вставки.

Методы «сверху вниз» осуществляют разбиение исходного набора данных на два (или более) подмножества, ограничивая их выбранным ограничивающим объемом, затем продолжают рекурсивное разбиение (и ограничение) до тех пор, пока каждое подмножество не состоит только из одного примитива (достигнуты листовые узлы). Методы сверху-вниз легки в реализации, быстры в построении и являются наиболее популярными, однако в общем случае не приводят к наилучшим возможным деревьям.

Методы «снизу вверх» начинают с входного набора данных, который представляет собой листья дерева, и затем объединяют два (или более) из них, чтобы сформировать новый (внутренний) узел. Этот процесс продолжается до тех пор, пока все не будет объединено в одном узлом (корнем дерева). Методы «снизу вверх» сложнее реализовать, но обычно дают более качественные деревья. Некоторые последние исследования ^[3] показывают, что в низкоразмерном пространстве скорость построения может значительно улучшиться (что соответствует или превосходит методы «сверху вниз»), если объекты сортируются с использованием кривой заполнения пространства, и применяется приближенная кластеризация на основе этого последовательного порядка.

Методы «сверху вниз» и «снизу вверх» считаются автономными методами, поскольку оба требуют наличия всех примитивов перед началом построения. Методы вставки строят дерево, вставляя по одному объекту, начиная с пустого дерева. Место вставки должно быть выбрано так, чтобы дерево росло как можно меньше в соответствии с метрикой стоимости. Методы вставки считаются интерактивными методами, поскольку они не требуют наличия всех примитивов перед началом построения и позволяют выполнять обновления во время выполнения.

Применение

BVH часто используются при трассировке лучей для исключения потенциальных кандидатов на пересечение внутри сцены путем исключения геометрических объектов, расположенных в ограничивающих объемах, которые не пересекаются текущим лучом. ^[4] Кроме того, в качестве общей оптимизации производительности, когда интерес представляет только ближайшее пересечение луча, поскольку алгоритм обхода трассировки лучей представляет собой нисходящие узлы, а луч пересекает несколько дочерних узлов, алгоритм обхода сначала рассматривает ближайший объем, и если он находит пересечение там, которое определенно ближе, чем любое возможное пересечение во втором (или другом) томе (т. е. тома не перекрываются), он может безопасно игнорировать второй объем. Аналогичные оптимизации во время обхода BVH можно использовать при переходе к дочерним объемам второго объема, чтобы ограничить дальнейшее пространство поиска и, таким образом, сократить время обхода.

Кроме того, для BVH было разработано множество специализированных методов, особенно на основе AABB (выровненный по осям параллелепипед), такие как параллельное построение, ускоренный обход SIMD, хорошая эвристика разделения (SAH - эвристика площади поверхности часто используется в трассировке лучей), широкие деревья (4- и 16-мерные деревья обеспечивают некоторые преимущества в производительности как при построении, так и при выполнении запросов для практических сцен) и быстрое обновление структуры (в приложениях реального времени объекты могут перемещаться или деформироваться в пространстве относительно медленно или оставаться неподвижными, и тот же BVH можно обновить, чтобы он оставался действительным, без полной перестройки с нуля).

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

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

См. также

Разделение двоичного пространства, октодерево, k -d дерево
R-дерево, R+-дерево, R*-дерево и X-дерево
М-дерево
Sweep and prune
Иерархическая кластеризация
OptiX

Примечания

↑ Ericson, 2005, pp. 236—237.
↑ Ericson, 2005, p. 238.
↑ Gu, Yan. Efficient BVH Construction via Approximate Agglomerative Clustering // HPG '13: Proceedings of the 5th High-Performance Graphics Conference / Yan Gu, Yong He, Kayvon Fatahalian … [и др.]. — ACM, 2013. — P. 81–88. — ISBN 9781450321358. — doi:10.1145/2492045.2492054.
↑ Günther, J. Realtime Ray Tracing on GPU with BVH-based Packet Traversal // 2007 IEEE Symposium on Interactive Ray Tracing / J. Günther, S. Popov, H.-P. Seidel … [и др.]. — IEEE, 2007. — P. 113–8. — ISBN 978-1-4244-1629-5. — doi:10.1109/RT.2007.4342598.

Литература

Ericson, Christer. §6.1 Hierarchy Design Issues // Real-Time collision detection (англ.). — Morgan Kaufmann, 2005. — P. 236–237. — ISBN 1-55860-732-3.

Ссылки

[_b839c398c1e76310-1] Ericson, 2005, pp. 236—237.

[_457f0ce18297e0b4-2] Ericson, 2005, p. 238.

[AAC-3] Gu, Yan. Efficient BVH Construction via Approximate Agglomerative Clustering // HPG '13: Proceedings of the 5th High-Performance Graphics Conference / Yan Gu, Yong He, Kayvon Fatahalian … [и др.]. — ACM, 2013. — P. 81–88. — ISBN 9781450321358. — doi:10.1145/2492045.2492054.

[4] Günther, J. Realtime Ray Tracing on GPU with BVH-based Packet Traversal // 2007 IEEE Symposium on Interactive Ray Tracing / J. Günther, S. Popov, H.-P. Seidel … [и др.]. — IEEE, 2007. — P. 113–8. — ISBN 978-1-4244-1629-5. — doi:10.1109/RT.2007.4342598.

[1]

[2]

[3]

[4]