Иерархия ограничивающих объемов ( BVH ) — это древовидная структура на наборе геометрических объектов. Все геометрические объекты, которые образуют конечные узлы дерева, обернуты в ограничивающие объемы . Затем эти узлы группируются в небольшие наборы и заключаются в более крупные ограничивающие объемы. Они, в свою очередь, также группируются и заключаются в другие более крупные ограничивающие объемы рекурсивным образом, в конечном итоге приводя к древовидной структуре с одним ограничивающим объемом наверху дерева. Иерархии ограничивающих объемов используются для эффективной поддержки нескольких операций над наборами геометрических объектов, таких как обнаружение столкновений и трассировка лучей .
Хотя обертывание объектов в ограничивающие объемы и выполнение тестов на столкновения на них перед тестированием самой геометрии объекта упрощает тесты и может привести к значительному повышению производительности, по-прежнему выполняется то же количество парных тестов между ограничивающими объемами. Расположив ограничивающие объемы в иерархии ограничивающих объемов, временная сложность (количество выполненных тестов) может быть снижена до логарифмической по количеству объектов. При наличии такой иерархии во время тестирования столкновений дочерние объемы не должны проверяться, если их родительские объемы не пересекаются (например, если ограничивающие объемы двух бамперных машин не пересекаются, ограничивающие объемы самих бамперов не должны проверяться на столкновение).
Выбор ограничивающего объема определяется компромиссом между двумя целями. С одной стороны, мы хотели бы использовать ограничивающие объемы, которые имеют очень простую форму. Таким образом, нам нужно всего несколько байт для их хранения, а тесты пересечения и вычисления расстояний просты и быстры. С другой стороны, мы хотели бы иметь ограничивающие объемы, которые очень плотно соответствуют соответствующим объектам данных. Одним из наиболее часто используемых ограничивающих объемов является минимальный ограничивающий прямоугольник, выровненный по осям . Минимальный ограничивающий прямоугольник, выровненный по осям, для заданного набора объектов данных легко вычислить, он требует всего несколько байт для хранения, а надежные тесты пересечения легко реализовать и они чрезвычайно быстры.
Существует несколько желаемых свойств BVH, которые следует учитывать при его проектировании для конкретного применения: [1]
С точки зрения структуры BVH, необходимо решить, какую степень (количество потомков) и высоту использовать в дереве, представляющем BVH. Дерево с низкой степенью будет иметь большую высоту. Это увеличивает время обхода от корня до листьев. С другой стороны, меньше работы должно быть затрачено на каждый посещенный узел для проверки его потомков на перекрытие. Обратное справедливо для дерева с высокой степенью: хотя дерево будет иметь меньшую высоту, больше работы тратится на каждый узел. На практике бинарные деревья (степень = 2) являются наиболее распространенными. Одна из главных причин заключается в том, что бинарные деревья проще строить. [2]
Существует три основные категории методов построения деревьев: сверху вниз, снизу вверх и методы вставки.
Методы сверху вниз осуществляют разбиение входного набора на два (или более) подмножества, ограничивая их в выбранном ограничивающем объеме, затем продолжают разбиение (и ограничение) рекурсивно, пока каждое подмножество не будет состоять только из одного примитива (достигнуты конечные узлы). Методы сверху вниз легко реализовать, быстро построить и, безусловно, являются самыми популярными, но в целом не приводят к наилучшим возможным деревьям.
Методы «снизу вверх» начинают с набора входных данных в качестве листьев дерева, а затем группируют два (или более) из них для формирования нового (внутреннего) узла, продолжая тем же образом, пока все не будет сгруппировано под одним узлом (корнем дерева). Методы «снизу вверх» сложнее в реализации, но, вероятно, в целом дадут лучшие деревья. Некоторые недавние исследования [3] показывают, что в низкоразмерном пространстве скорость построения может быть значительно улучшена (что соответствует или превосходит подходы «сверху вниз») путем сортировки объектов с использованием кривой заполнения пространства и применения приблизительной кластеризации на основе этого последовательного порядка.
Оба метода, «сверху вниз» и «снизу вверх», считаются офлайн-методами , поскольку оба требуют, чтобы все примитивы были доступны до начала построения. Методы вставки строят дерево, вставляя по одному объекту за раз, начиная с пустого дерева. Место вставки должно быть выбрано так, чтобы дерево росло как можно меньше в соответствии с метрикой стоимости. Методы вставки считаются онлайн-методами, поскольку они не требуют, чтобы все примитивы были доступны до начала построения, и, таким образом, позволяют выполнять обновления во время выполнения.
BVH часто используются в трассировке лучей для устранения потенциальных кандидатов на пересечение в пределах сцены путем исключения геометрических объектов, расположенных в ограничивающих объемах, которые не пересекаются текущим лучом. [4] Кроме того, в качестве общей оптимизации производительности, когда интерес представляет только ближайшее пересечение луча, поскольку алгоритм обхода трассировки лучей является нисходящими узлами, а несколько дочерних узлов пересекают луч, алгоритм обхода сначала рассмотрит более близкий объем, и если он найдет там пересечение, которое определенно ближе, чем любое возможное пересечение во втором (или другом) объеме (т. е. объемы не перекрываются), он может безопасно игнорировать второй объем. Аналогичные оптимизации во время обхода BVH могут использоваться при спуске в дочерние объемы второго объема, чтобы ограничить дальнейшее пространство поиска и, таким образом, сократить время обхода.
Кроме того, для BVH было разработано много специализированных методов, особенно основанных на AABB (axis-aligning bounding boxs), таких как параллельное построение, ускоренный обход SIMD , хорошая эвристика разделения (SAH - эвристика площади поверхности часто используется в трассировке лучей), широкие деревья (4-арные и 16-арные деревья обеспечивают некоторые преимущества в производительности, как при построении, так и при выполнении запросов для практических сцен) и быстрое обновление структуры (в приложениях реального времени объекты могут перемещаться или деформироваться в пространстве относительно медленно или оставаться неподвижными, и тот же BVH можно обновить, чтобы он оставался действительным без выполнения полной перестройки с нуля).
BVH также естественным образом поддерживают вставку и удаление объектов без полной перестройки, но в результате BVH обычно имеет худшую производительность запросов по сравнению с полной перестройкой. Чтобы решить эти проблемы (а также быстрое обновление структуры, которое не является оптимальным), новый BVH может быть построен асинхронно, параллельно или синхронно, после обнаружения достаточного изменения (большое перекрытие листьев, количество вставок и удалений превысило пороговое значение и другие более тонкие эвристики).
BVH также можно комбинировать с методами графа сцены и созданием экземпляров геометрии для сокращения использования памяти, повышения производительности обновления структуры и полной перестройки, а также для лучшего разделения объектов или примитивов.
BVH часто используются для ускорения вычислений обнаружения столкновений . В контексте моделирования ткани BVH используются для вычисления столкновений между тканью и самой собой, а также с другими объектами. [5]
Другим мощным вариантом использования BVH является вычисление парного расстояния. Наивный подход к поиску минимального расстояния между двумя наборами объектов вычислил бы расстояние между всеми парными комбинациями. BVH позволяет нам эффективно отсекать многие сравнения без необходимости вычисления потенциально сложного расстояния между всеми объектами. Псевдокод для вычисления парного расстояния между двумя наборами объектов и подходы к построению BVH, хорошо подходящие для вычисления расстояния, обсуждаются здесь [6]
BVH может значительно ускорить приложения трассировки лучей, сократив количество вычислений пересечения лучей с поверхностью. Аппаратная реализация операций BVH, таких как обход, может еще больше ускорить трассировку лучей. В настоящее время трассировка лучей в реальном времени доступна на нескольких платформах. Аппаратная реализация BVH является одним из ключевых нововведений, делающих это возможным.
В 2018 году Nvidia представила ядра RT с архитектурой Turing GPU как часть платформы RTX. Ядра RT — это специализированные аппаратные блоки, разработанные для ускорения тестов обхода BVH и пересечения лучей и треугольников. [7] Сочетание этих ключевых функций позволяет выполнять трассировку лучей в реальном времени, которую можно использовать в видеоиграх. [8] а также в приложениях для проектирования.
Архитектура AMD RDNA (Radeon DNA) , представленная в 2019 году, включает аппаратно-ускоренную трассировку лучей с момента ее второй итерации, RDNA 2. Архитектура использует выделенные аппаратные блоки, называемые ускорителями лучей, для выполнения тестов пересечения луча с ящиком и луча с треугольником, которые имеют решающее значение для обхода иерархий ограничивающих объемов (BVH). [9] В RDNA 2 и 3 шейдер отвечает за обход BVH, в то время как ускорители лучей обрабатывают тесты пересечения для узлов ящика и треугольника. [10]
Первоначально разработанный для ускорения трассировки лучей, теперь исследователи изучают способы использования быстрого обхода BVH для ускорения других приложений. К ним относятся определение содержащего тетраэдра для точки [11] , улучшение моделирования гранулярной материи [12] и выполнение вычислений ближайшего соседа [13] . Некоторые методы перепрофилируют основные компоненты RT Nvidia, переформулируя эти задачи как задачи трассировки лучей. Это направление кажется многообещающим, поскольку сообщается о существенном ускорении производительности в различных приложениях.