Иерархия ограничивающих объемов

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

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

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

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

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

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

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

Строительство

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

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

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

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

Использование

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

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

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

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

См. также

Ссылки

^ Эриксон, Кристер (2005). «§6.1 Проблемы проектирования иерархии» . Обнаружение столкновений в реальном времени . Серия Моргана Кауфмана по интерактивным 3D-технологиям. Морган Кауфманн. стр. 236–7. ISBN 1-55860-732-3 .
^ Эриксон 2005 , с. 238
^ Гу, Ян; Он, Йонг; Фатахалян, Кайвон; Беллох, Гай (2013). «Эффективное строительство BVH посредством приблизительной агломерационной кластеризации» (PDF) . HPG '13: Материалы 5-й конференции по высокопроизводительной графике . АКМ. стр. 81–88. CiteSeerX 10.1.1.991.3441 . дои : 10.1145/2492045.2492054 . ISBN 9781450321358 . S2CID 2585433 .
^ Гюнтер, Дж.; Попов С.; Зайдель, Х.-П.; Слусаллек, П. (2007). «Трассировка лучей в реальном времени на графическом процессоре с обходом пакетов на основе BVH». Симпозиум IEEE 2007 г. по интерактивной трассировке лучей . IEEE. стр. 113–8. CiteSeerX 10.1.1.137.6692 . дои : 10.1109/RT.2007.4342598 . ISBN 978-1-4244-1629-5 . S2CID 2840180 .

Внешние ссылки

[1] Эриксон, Кристер (2005). «§6.1 Проблемы проектирования иерархии» . Обнаружение столкновений в реальном времени . Серия Моргана Кауфмана по интерактивным 3D-технологиям. Морган Кауфманн. стр. 236–7. ISBN 1-55860-732-3 .

[2] Эриксон 2005 , с. 238

[AAC-3] Гу, Ян; Он, Йонг; Фатахалян, Кайвон; Беллох, Гай (2013). «Эффективное строительство BVH посредством приблизительной агломерационной кластеризации» (PDF) . HPG '13: Материалы 5-й конференции по высокопроизводительной графике . АКМ. стр. 81–88. CiteSeerX 10.1.1.991.3441 . дои : 10.1145/2492045.2492054 . ISBN 9781450321358 . S2CID 2585433 .

[4] Гюнтер, Дж.; Попов С.; Зайдель, Х.-П.; Слусаллек, П. (2007). «Трассировка лучей в реальном времени на графическом процессоре с обходом пакетов на основе BVH». Симпозиум IEEE 2007 г. по интерактивной трассировке лучей . IEEE. стр. 113–8. CiteSeerX 10.1.1.137.6692 . дои : 10.1109/RT.2007.4342598 . ISBN 978-1-4244-1629-5 . S2CID 2840180 .

[1]

[2]

[3]

[4]