Войти
Пример иерархии ограничивающих объемов с использованием прямоугольников в качестве ограничивающих объемов. A иерархия ограничивающих объемов hy (BVH ) - это древовидная структура на наборе геометрических объектов. Все геометрические объекты заключены в ограничивающие объемы, которые образуют конечные узлы дерева. Эти узлы затем группируются в небольшие наборы и заключаются в большие ограничивающие объемы. Они, в свою очередь, также сгруппированы и заключены в другие большие ограничивающие объемы рекурсивным образом, что в конечном итоге приводит к древовидной структуре с одним ограничивающим объемом в верхней части дерева. Иерархии ограничивающих объемов используются для эффективной поддержки нескольких операций с наборами геометрических объектов, таких как обнаружение столкновений и трассировка лучей.
, несмотря на то, что объекты помещаются в ограничивающие объемы и выполняются тесты на столкновения перед тестированием геометрия объекта сама по себе упрощает тесты и может привести к значительному повышению производительности, то же количество парных тестов между ограничивающими объемами все еще выполняется. Путем организации ограничивающих объемов в иерархию ограничивающих объемов временная сложность (количество выполненных тестов) может быть уменьшена до логарифмической по количеству объектов. При наличии такой иерархии во время тестирования на столкновение дочерние тома не нужно проверять, если их родительские тома не пересекаются.
Выбор ограничивающего объема определяется компромиссом между двумя целями. С одной стороны, мы хотели бы использовать ограничивающие объемы очень простой формы. Таким образом, нам нужно всего несколько байтов для их хранения, а тесты пересечения и вычисления расстояний просты и быстры. С другой стороны, мы хотели бы иметь ограничивающие объемы, которые очень точно соответствовали бы соответствующим объектам данных. Одним из наиболее часто используемых ограничивающих объемов является выровненная по оси минимальная ограничивающая рамка. Выровненный по оси минимальный ограничивающий прямоугольник для заданного набора объектов данных легко вычислить, для этого требуется всего несколько байтов памяти, а надежные тесты пересечения легко реализовать и чрезвычайно быстро.
Есть несколько желаемых свойств для BVH, которые следует учитывать при проектировании для конкретного приложения:
С точки зрения структуры BVH, необходимо решить, какую степень (количество дочерних элементов) и высоту использовать в дерево, представляющее BVH. Дерево низшей ступени будет большей высоты. Это увеличивает время обхода от корня к листу. С другой стороны, на каждый посещаемый узел нужно затрачивать меньше работы, чтобы проверить его дочерние узлы на перекрытие. Обратное верно для дерева с высокой степенью: хотя дерево будет меньше по высоте, на каждый узел тратится больше работы. На практике бинарные деревья (степень = 2) являются наиболее распространенными. Одна из основных причин заключается в том, что бинарные деревья строить проще.
Существует три основных категории методов построения дерева: сверху вниз, снизу вверх и методы вставки.
Нисходящие методы осуществляются путем разделения входного набора на два (или более) подмножества, ограничивая их в выбранном ограничивающем объеме, а затем продолжают рекурсивное разделение (и ограничение) до тех пор, пока каждое подмножество не будет состоять только из одного примитива ( листовые узлы достигнуты). Нисходящие методы легко реализовать, быстро построить и, безусловно, самые популярные, но в целом они не приводят к созданию наилучших возможных деревьев.
Методы снизу вверх начинаются с ввода, заданного как листья дерева, а затем группируют два (или более) из них, чтобы сформировать новый (внутренний) узел, действуйте таким же образом, пока все не будет сгруппировано под одним узлом (корнем дерева). Методы снизу вверх труднее реализовать, но в целом они, вероятно, позволят получить более качественные деревья. Некоторые недавние исследования (например) показывают, что в низкоразмерном пространстве скорость построения может быть значительно улучшена (что соответствует или превосходит подходы сверху вниз) путем сортировки объектов с использованием кривой заполнения пространства и применения приблизительной кластеризации на основе этого последовательного порядка.
И нисходящие, и восходящие методы считаются автономными, поскольку они оба требуют, чтобы все примитивы были доступны до начала построения. Методы вставки создают дерево, вставляя по одному объекту за раз, начиная с пустого дерева. Место вставки должно быть выбрано таким образом, чтобы дерево росло как можно меньше согласно метрике стоимости. Методы вставки считаются интерактивными, поскольку они не требуют, чтобы все примитивы были доступны до начала построения, и, таким образом, позволяют выполнять обновления во время выполнения.
BVH часто используются в трассировке лучей для исключения потенциальных кандидатов на пересечение внутри сцены путем исключения геометрических объектов, расположенных в ограничивающих объемах, которые не пересекаются текущим лучом.. Кроме того, в качестве общей оптимизации производительности, когда представляет интерес только ближайшее пересечение луча, так как алгоритм обхода трассировки лучей представляет собой нисходящие узлы, а несколько дочерних узлов пересекают луч, алгоритм обхода сначала рассмотрит ближайший объем, и если он найдет пересечение там, которое определенно ближе, чем любое возможное пересечение во втором (или другом) объеме (т.е. объемы не перекрываются), он может спокойно игнорировать второй объем. Подобные оптимизации во время обхода BVH можно использовать при спуске в дочерние тома второго тома, чтобы ограничить дальнейшее пространство поиска и, таким образом, сократить время обхода.
Кроме того, для BVH было разработано множество специализированных методов, особенно на основе AABB (выровненных по оси ограничивающих рамок), таких как параллельное построение, SIMD ускоренное прохождение, хорошая эвристика разделения (SAH - часто используется при трассировке лучей), широкие деревья (4-х и 16-ти мерные деревья дают некоторые преимущества в производительности, как в сборке, так и в производительности запросов для практических сцен) и быстрое обновление структуры (в приложениях реального времени объекты могут перемещаться или деформироваться в пространстве относительно медленно или оставаться неподвижными, и тот же самый BVH может быть обновлен, чтобы он оставался действительным без выполнения полной перестройки с нуля).
BVH также, естественно, поддерживают вставку и удаление объектов без полной перестройки, но в результате BVH обычно имеет худшую производительность запросов по сравнению с полной перестройкой. Для решения этих проблем (а также для того, чтобы быстрое обновление структуры было неоптимальным), новый BVH может быть построен асинхронно, параллельно или синхронно, после того, как будет обнаружено достаточное изменение (перекрытие листьев большое, количество вставок и удалений пересекло пороговое значение и другие более тонкие эвристики).
BVH также можно комбинировать с методами графа сцены и экземпляром геометрии, чтобы уменьшить использование памяти, улучшить обновление структуры и производительность полного перестроения, а также улучшить руководство объектное или примитивное разбиение.
