Иерархия ограничивающих интервалов - Bounding interval hierarchy

А иерархия ограничивающих интервалов (БиГ) является разбиением структура данных аналогично тому из ограничивающие иерархии томов или же kd-деревья. Иерархии ограничивающих интервалов могут использоваться с высокой производительностью (или в реальном времени) трассировка лучей и может быть особенно полезно для динамических сцен.

BIH впервые был представлен под названием SKD-Trees,[1] представленный Ooi et al. и BoxTrees,[2] независимо изобретен Захманном.

Обзор

Иерархии граничных интервалов (BIH) демонстрируют многие свойства обоих ограничивающие иерархии томов (BVH) и kd-деревья. В то время как конструкция и хранение BIH сравнимы с BVH, обход BIH напоминает обход kd-деревья. Кроме того, БиГ также бинарные деревья точно так же, как 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), равного оси разделения текущего узла, обход продолжается сначала влево (положительное направление) или вправо (отрицательное направление). направлении) ребенок, а другой толкается на куча для отложенного потенциального обхода.

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

Также можно добавить пятый случай обхода, но это также требует немного сложного этапа построения. Меняя местами значения левой и правой плоскости узла, можно отрезать пустое пространство по обе стороны от узла. Для этого требуется дополнительный бит, который должен быть сохранен в узле для обнаружения этого особого случая во время обхода. Обработка этого случая на этапе обхода проста, поскольку луч

  • просто пересекает единственный дочерний элемент текущего узла или
  • ничего не пересекается

Характеристики

Численная стабильность

Все операции при построении иерархии / сортировке треугольников - это min / max-операции и сравнения. Таким образом, обрезка треугольников не требуется, как в случае с kd-деревьями, и это может стать проблемой для треугольников, которые лишь слегка пересекают узел. Даже если реализация kd тщательно написана, числовые ошибки могут привести к необнаруженному пересечению и, таким образом, к ошибкам рендеринга (дырам в геометрии) из-за пропущенного пересечения луча и объекта.

Расширения

Вместо использования двух плоскостей на узел для разделения геометрии также можно использовать любое количество плоскостей для создания n-арного BIH или использовать несколько плоскостей в стандартном двоичном BIH (одна и четыре плоскости на узел уже были предложены в[4] а затем правильно оценивается в[5]) для лучшего разделения объектов.

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

Рекомендации

Статьи

  1. ^ Нам, Бомсок; Сассман, Алан. Сравнительное исследование методов пространственного индексирования многомерных наборов научных данных
  2. ^ Захманн, Габриэль. Обнаружение минимальных иерархических столкновений В архиве 2007-02-10 на Wayback Machine
  3. ^ Уолд, Инго; Булос, Соломон; Ширли, Питер (2007). Деформируемые сцены с трассировкой лучей с использованием динамических иерархий ограничивающих объемов
  4. ^ а б c Вехтер, Карстен; Келлер, Александр (2006). Мгновенная трассировка лучей: иерархия ограничивающих интервалов
  5. ^ Вехтер, Карстен (2008). Квази-Монте-Карло Моделирование транспорта света с помощью эффективной трассировки лучей

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