Иерархия ограничивающего объема - Bounding volume hierarchy - Wikipedia

Пример иерархии ограничивающих объемов с использованием прямоугольников в качестве ограничивающих объемов.

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

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

Проблемы дизайна BVH

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

Существует несколько желаемых свойств 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 также можно комбинировать с граф сцены методы и создание экземпляров геометрии, чтобы уменьшить использование памяти, улучшить обновление структуры и производительность полного перестроения, а также улучшить разбиение объектов или примитивов.

Смотрите также

внешняя ссылка

[1] Кристер Эриксон, Обнаружение столкновений в реальном времени, стр. 236–237

[2] Эриксон, Кристер. Обнаружение столкновений в реальном времени. п. 238. ISBN 1-55860-732-3.

[AAC-3] Y. Gu, Y. He, K. Fatahalian и G. Blelloch. Эффективное строительство BVH за счет приближенной агломеративной кластеризации. HPG 2013.

[4] Йоханнес Гюнтер, Стефан Попов, Ханс-Петер Зайдель и Филипп Слусаллек, Трассировка лучей в реальном времени на графическом процессоре с обходом пакетов на основе BVH

[1]

[2]

[3]

[4]