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

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

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

Проблемы проектирования 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.
  3. ^ Y. Gu, Y. Он, К. Fatahalian и G Blelloch. Эффективное строительство BVH с помощью приближенной агломеративной кластеризации . HPG 2013.
  4. ^ Йоханнес Гюнтер, Стефан Попов, Ханс-Петер Зайдель и Филипп Слусаллек, Трассировка лучей в реальном времени на графическом процессоре с обходом пакетов на основе BVH

Внешние ссылки [ править ]

  • BVH в Javascript .
  • Динамический BVH в C #
  • Библиотека Intel Embree с открытым исходным кодом BVH