Skip to main content

Основы алгоритма трассировки лучей. Третья часть.

AA

При рендеринге методом трассировки лучей возникает проблема так называемых «лесенок» на границах объектов и текстур. Источник проблемы заключается в том, что мы пытаемся аналитическую функцию дискретизировать с некоторым постоянным шагом отчетов. Это ведет к неизбежной потере данных и, как следствие, к потере качества изображения. Процесс устранения таких лесенок называется Anti-Aliasing.

No AA
No AA

With AA
With AA

FSAA

Full Screen Anti Aliasing. Метод, заключающийся в увеличении частоты отчетов при дискретизации функции. Самый топорный способ — отрендерить картинку N раз с небольшим смещением наблюдателя относительно исходной точки, результат усреднить. Структура алгоритма трассировки лучей позволяет сделать это немного по другому. Можно выполнять субпиксельный рендеринг ( вместо 1го луча на пиксель посылать N, распределенных по равномерной сетке внутри пикселя). Результат опять же усреднять. По сути результат близок к тому, что мы генерируем картинку высокой четкости, а потом масштабируем ее к заданному разрешению с размытием.
Плюсы:

  • Хорошее качество

Минусы:

  • Ну оооочень долго

Адаптивный АА

Суть заключается в том, чтобы просчитывать дополнительные лучи только там, где это действительно необходимо. Адаптивное сглаживание выполняется в несколько шагов.
Сначала нам надо отрендерить изображение в обычном качестве. Потом надо определить области, где нужно сделать уточненный перерасчет. Обычно такими областями являются границы объектов или края не текстурах. Для их определения используется, чаще всего, оператор Собеля   \begin{bmatrix}  +1 & +2 & +1 \\  0 & 0 & 0 \\  -1& -2 & -1  \end{bmatrix}
Линейная свертка изображения с таким ядром дает на выходе карту вертикальных краев (для горизонтальных оператор надо транспонировать) изображения.

Sobel Input
Sobel Input
Sobel Result
Sobel Result

В пикселях, где интенсивность карты больше некоторого порога — производится уточнение.

Sobel Input Binarized
Sobel Input Binarized

Ну и для верности, результат порога немного расширить, для того чтобы обсчитать соседние пиксели.

Sobel Input Binarized and Dilated
Sobel Input Binarized and Dilated

Таким образом можно получать более производительное сглаживание.

Минусами данного алогоритма является то, что он плохо работает на похожих областях.

Ambient Occlusion

Один из методов глобального освещения, также иногда называемый SkyLight. Идея заключается в том, что мы используем небо как источник света. Чем больше неба видно из точки, в которой мы рассчитываем освещения, тем больше освещена эта точка. Формально, метод можно описать интегралом по полусфере вокруг точки:
I_s\left(z\right)=\frac{1}{2\pi}\int\limits_{\Omega}V(z,r) dr,

Ambient Occlusion
Ambient Occlusion

где V(z,r) — функция видимости неба из точки z в направлении r, равная 1, если есть прямая видимость и 0 в противном случае.
Для вычисления этого интеграла пользуются различными техниками, самым распространенной является метод Монте-Карло ( интегрирование по случайным лучам ).

Ambient Occlusion дает приятный результат даже сам по себе, без применения прямого освещения, но очень трудоемок в вычислении. Поэтому для вычисления AO лучше использовать kd-Деревья, которые существенно ускоряют поиск пересечений

Пример SkyLight
Ambient Occlusion

Имитация АО с помощью 400 источников света
Имитация АО с помощью 400 источников света

Kd-Деревья

Kd(imensional)-tree — это многомерное дерево, которое используется для описания структуры сцены. Использование заложенной в сцену информации о положении объектов существенно ускоряет обработку. Идея заключается в том, что мы делим пространство плоскостью пополам, далее левое полупространство и правое рекурсивно. Постепенно мы таким образом разделим наше пространство на некоторые не пересекающиеся блоки. Зная направление луча мы можем определить, какие блоки пересечет наш луч, и искать пересечения только с теми объектами, которые попали в эти блоки. Таким образом мы существенно ускоряем обработку пересечений лучей.

Построение kd-tree

Можно рассмотреть несколько методов построения деревьев. Они различаются между собой сложностью расчетов и вычислительной эффективностью.

Октодерево

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

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

SAH

Использование Surface Area Heuristic метрики позволяет быстро отбрасывать пустые области в блоке. Идея метода заключается в том, что вводится стоимость обработки блока, разделенного плоскостью x.
Cost(x) = T_t  + p_a*N_a*t_i + p_b*N_b*t_i, где
T_t — время (стоимость) обработки пустого блока;
T_i — время расчета пересечений ( T_i = 80 * T_t );
p_a = \frac{S_a}{S} — относительная площадь левого подблока;
p_b = \frac{S_b}{S} — то же для правого;
N_a — количество объектов в левом подблоке;
N_b — то же в правом подблоке.

SAH
SAH

Тогда минимум стоимости будет наилучшим разбиением блока с точки зрения производительности. Чтобы не делать полный перебор плоскостей можно заметить, что функция изменяет свое значение только в тех местах, где изменяется количество объектов в подблоках. То есть на границах объектов. Таким образом достаточно перебрать всего 2*N плоскостей, чтобы найти минимум, где N — количество объектов в блоке.

Ограничением на глубину дерева является стоимость обработки блока. Как только стоимость обработки блока, как целого, дороже, чем обработка двух подблоков — построение прекращается.

Аналитически бесконечные объекты

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

Итог. Алогоритм постороения

  1. Поместить объекты в начальный бокс — корень дерева
  2. Если не выполнен критерий остановки построения — продолжить
  3. Выбрать плоскость разбиения
  4. Выполнить построение для левого подблока и правого подблока

Разбор kd-tree

Разбор дерева осуществляется рекурсивно, начиная с корня. Вычисляются точки пересечения луча с подблоками в параметрических координатах. Координата входа в блок — T_{near}, выхода T_{far}, пересечения разделяющей плоскости — T_{split}.

kd-tree traverse
kd-tree traverse

Если latex path not specified.: T_{near} < T_{far} < T_{split}[/latex], тогда луч пересекает только первый блок. Если [latex]T_{near} < T_{split} < T_{far} [/latex], то оба, а если [latex]T_{near} < T_{far} < T_{split} [/latex], то только второй блок. Таким образом рекурсивно мы сначала обрабатываем ближний блок, если в нем не нашли пересечения, то дальний (или только один, если второй не пересекается). Когда у нас остаются только листовые блоки в дереве, то в них мы вычисляем все пересечения перебором (брутфорсом). Подробней, по работе с kd-деревьями, в частности, о методах разбора на GPU, можно почитать, например, на блоге ray-tracing.ru.