Иерархия граничных интервалов
Иерархия ограничивающих интервалов ( BIH ) — это структура данных разделения, аналогичная структуре иерархий ограничивающих томов или kd-деревьев . Иерархии ограничивающих интервалов могут использоваться при высокопроизводительной трассировке лучей (или в реальном времени) и могут быть особенно полезны для динамических сцен.
BIH впервые был представлен под названием SKD-Trees. [1] представлено Ooi et al. и BoxTrees, [2] независимо изобретен Захманом.
Обзор
[ редактировать ]Иерархии ограничивающих интервалов (BIH) обладают многими свойствами как иерархий ограничивающих объемов (BVH), так и kd-деревьев . В то время как построение и хранение BIH сравнимо с обходом BVH, обход BIH напоминает обход kd-деревьев . Более того, BIH также являются двоичными деревьями , как и kd-деревья (и фактически их надмножество, BSP-деревья ). Наконец, BIH выровнены по оси, как и его предки. Хотя более общая реализация BIH без выравнивания по осям должна быть возможна (аналогично BSP-дереву, которое использует невыровненные плоскости), она почти наверняка будет менее желательной из-за снижения числовой стабильности и увеличения сложности лучевого моделирования. обход.
Ключевой особенностью BIH является хранение двух плоскостей на узел (в отличие от 1 для дерева kd и 6 для иерархии ограничивающих рамок, выровненных по оси ), что позволяет перекрываться дочерним элементам (точно так же, как BVH), но в то же время время с указанием порядка детей по одному измерению/оси (как в случае с деревьями kd).
Также можно просто использовать структуру данных BIH на этапе построения, но перемещаться по дереву так, как это делает традиционная иерархия ограничивающих рамок с выравниванием по оси. Это позволяет выполнить некоторые простые оптимизации ускорения для больших пучков лучей. [3] сохраняя при этом низкое использование памяти / кэша .
Некоторые общие атрибуты иерархий ограничивающих интервалов (и методов, связанных с BIH), как описано в [4] являются:
- Очень быстрые сроки строительства
- Низкое потребление памяти
- Простой и быстрый обход
- Очень простое построение и алгоритмы обхода
- Высокая числовая точность при построении и обходе
- Более плоская древовидная структура (уменьшенная глубина дерева) по сравнению с kd-деревьями.
Операции
[ редактировать ]Строительство
[ редактировать ]Для построения любой разделения пространства структуры та или иная форма эвристики обычно используется . Возможным кандидатом для этого является эвристика площади поверхности , обычно используемая во многих схемах разделения. Другая, более упрощенная эвристика — это «глобальная» эвристика. [4] для которого требуется только ограничивающая рамка, выровненная по оси , а не полный набор примитивов, что делает его гораздо более подходящим для быстрого построения.
Общая схема строительства БИГ:
- вычислить ограничивающую рамку сцены
- используйте эвристику для выбора одной оси и кандидата на разделенную плоскость, перпендикулярного этой оси
- сортировать объекты по левому или правому дочернему элементу (исключительно) в зависимости от ограничивающей рамки объекта (обратите внимание, что объекты, пересекающие разделенную плоскость, могут быть отсортированы либо по ее перекрытию с дочерними объемами, либо по любой другой эвристике)
- вычислить максимальное граничное значение для всех объектов слева и минимальное граничное значение для объектов справа для этой оси (можно объединить с предыдущим шагом для некоторых эвристик)
- сохраните эти 2 значения вместе с 2 битами, кодирующими разделенную ось, в новом узле
- продолжите с шага 2 для детей
Потенциальные эвристики для поиска кандидатов на расщепленную плоскость:
- Классический вариант: выберите самую длинную ось и середину ограничивающей рамки узла на этой оси.
- Классика: выберите самую длинную ось и разделите плоскость, проходящую через медиану объектов (в результате получается левое дерево, что часто неудачно для трассировки лучей)
- Глобальная эвристика: выберите плоскость разделения на основе глобального критерия в форме регулярной сетки (избегает ненужных разделений и сохраняет объемы узлов как можно более кубическими)
- Эвристика площади поверхности: вычислите площадь поверхности и количество объектов для обоих детей по множеству всех возможных кандидатов на расщепленную плоскость, затем выберите тот, у которого наименьшие затраты (который считается оптимальным, хотя функция стоимости предъявляет необычные требования для доказательства формула, которую невозможно выполнить в реальной жизни, а также исключительно медленная эвристика)
Обход лучей
[ редактировать ]Фаза обхода очень напоминает обход kd-дерева: нужно выделить четыре простых случая, когда луч
- просто пересекает левого дочернего элемента
- просто пересекает правого дочернего элемента
- пересекает обоих детей
- не пересекает ни одного дочернего элемента (единственный случай, который невозможен при обходе kd)
Для третьего случая, в зависимости от направления луча (отрицательного или положительного) компонента (x, y или z), равного расщепленной оси текущего узла, обход продолжается сначала влево (положительное направление) или вправо (отрицательное направление). направлении) дочерний элемент, а другой помещается в стек для отложенного потенциального обхода.
Обход продолжается до тех пор, пока не будет найден листовой узел. После пересечения объектов в листе следующий элемент обхода извлекается из стека. Если стек пуст, возвращается ближайшее пересечение всех проколотых листьев. Если вытолкнутый элемент полностью находится за пределами текущего ближайшего пересечения, его обход пропускается.
Также возможно добавить пятый случай обхода, но для этого также потребуется немного усложненный этап построения. Поменяв местами значения левой и правой плоскостей узла, можно отрезать пустое пространство с обеих сторон узла. Для этого требуется дополнительный бит, который должен быть сохранен в узле, чтобы обнаружить этот особый случай во время обхода. Обработка этого случая на этапе обхода проста, поскольку луч
- просто пересекает единственного дочернего элемента текущего узла или
- ничего не пересекает
Характеристики
[ редактировать ]Численная стабильность
[ редактировать ]Все операции при построении иерархии/сортировке треугольников являются мин/макс-операциями и сравнениями. Таким образом, не нужно выполнять отсечение треугольников, как в случае с kd-деревьями, что может стать проблемой для треугольников, которые лишь слегка пересекают узел. Даже если реализация kd написана тщательно, числовые ошибки могут привести к необнаружению пересечения и, следовательно, к ошибкам рендеринга (дыры в геометрии) из-за пропущенного пересечения луча и объекта.
Расширения
[ редактировать ]Вместо использования двух плоскостей на узел для разделения геометрии также можно использовать любое количество плоскостей для создания n-арного BIH или использовать несколько плоскостей в стандартном двоичном BIH (одна и четыре плоскости на узел уже были предложены в [4] и затем должным образом оценены в [5] ), чтобы добиться лучшего разделения объектов.
Ссылки
[ редактировать ]Статьи
[ редактировать ]- ^ Нам, Бомсок; Сассман, Алан. Сравнительное исследование методов пространственной индексации многомерных наборов научных данных. [ мертвая ссылка ]
- ^ Захманн, Габриэль. Минимальное иерархическое обнаружение столкновений. Архивировано 10 февраля 2007 г. на Wayback Machine.
- ^ Вальд, Инго; Булос, Соломон; Ширли, Питер (2007). Трассировка лучей в деформируемых сценах с использованием динамических иерархий ограничивающих объемов
- ^ Перейти обратно: а б с Вахтер, Карстен; Келлер, Александр (2006). Мгновенная трассировка лучей: иерархия ограничивающих интервалов
- ^ Вехтер, Карстен (2008). Квази-Монте-Карло моделирование светового транспорта с помощью эффективной трассировки лучей
Внешние ссылки
[ редактировать ]- Реализации BIH: Javascript , C++ .