Скитаясь по интернету в поисках алгоритмом освещения, которые бы удовлетворили мои потребности, я наткнулся на весьма новый алгоритм, разработанный компанией NVIDIA, название которого AOV (Ambient Occlusion Volumes). Имея в своём распоряжении тёмные осенние ночи и несколько чашек горячего кофе, я решился изучить данный алгоритм, следствием чего является данная статья. Прежде чем я начну, хотелось бы отметить своё удивление по поводу того, что данный алгоритм имеет незаслуженно малую популярность в кругах разработчиков игр, в отличии от всеми знакомого нам SSAO. Содержание данной статьи будет, по большей мере, состоять из теории.

Введение

В июне 2010 года Morgan McGuire, исследователь и разработчик компании NVIDIA, разработал алгоритм освещения, который носит название Ambient Occlusion Volumes. При разработке данного алгоритма, M. McGuire, ставил себе в цель добиться более высокой производительности и качества освещения. Производительность алгоритма, по словам разработчика, во многом независима от сложности моделей, а по качеству освещения не уступает Ray Tracing'у.

Немного об Ambient Occlusion

AO(Ambient Occlusion) является приближённым к GI(Global Illumination) алгоритмом, призванным к затенению пространств, на которых, фактически, не падают лучи света по причине того, что данные пространства условно перекрываются другими объектами, делая недоступным попадания лучей света к этому пространству. Сам алгоритм работает путём вычисления лучей, исходящих из точки, затенение которой мы проверяем, с последующей проверкой на пересечение объекта лучом. Если луч проходит без препятствий, то данная точка освещена, иначе — затенена.

Но при расчете таким алгоритмом возникают некие трудности. Через некоторое время на замену старому алгоритму пришёл SSAO(Screen Space Ambient Occlusion) от разработчиков компании Crytek. Сам алгоритм работал по такому принципу, что определяется некая сфера и в диапазоне этой сферы случайно отбираются точки после чего идёт проверка глубин(прежде записанных в буффер глубин) этих точек с той, для которой мы вычисляем затенение. Если глубина последней больше за глубину случайной точки, то она — затенена, а иначе, соответственно, освещена. Выполняется несколько таких проверок, после чего их результаты суммируются и вычисляется коэффициент затенения. Выглядит оно, примерно, так:


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

Далее мне бы хотелось рассмотреть еще одну немаловажную тему перед тем как будет описан AOV метод.

Radiosity

Многие из тех, кто знаком с названым методом нахмурились бы услышав данный метод в контексте Ambient Occlsuion. В действительности, эти методы тесно связаны друг с другом.

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

Метод radiosity, так же известный как метод излучательности, является одним из методов GI, который опирается на расчёт форм-факторов(form-factors), которые, в свою очередь, описывают обмен энергией между парами плоскостей в окружающей среде.

Если коротко, форм-факторы представляют собой некую часть энергии, которая излучается из одной плоскости и принимается другой. При расчёте форм-фактора учитывается расстояние между центрам плоскостей и углом поворота относительно друг друга.


Вычисляется форм-фактор таким образом:


где ?i,j — угол между нормалью плоскости и Ri,j,, dA1,2 — дифференциальная область плоскости, Ri,j — вектор расстояния между dA1,2. В данном уравнении HID равно единице, если dA1,2 видимы друг для друга и ноль, если наоборот.

На расцвете данного метода использовались два подхода: Full Matrix Radiosity и Progressive Refinement Radiosity.

Full Matrix Radiosity

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

Интенсивность света, который излучает плоскость вычисляем таким способом:


где pi -коэффициент отражения плоскости i; Fij — форм-фактор из плоскости i к плоскости j; Ii — raidosity плоскости i; Iei — интенсивность излучения плоскости i; N — количество плоскостей которые находятся в окружении.

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

Форм-фактор от патча к патчу вычисляется так:


где Ei — количество элементов в патче, Fej — форм-фактор от элемента e к патчу j, Ai,e — области патча и элемента.

Progressive Refinement Radiosity

Данный подход основан на предыдущем. Особенность данного подхода состоит в том, что после каждой итерации происходит перерасчёт, а именно инкремент значения излучательности плоскости. Рассчитывается оно таким образом:


где Ii — уже просчитанное значение излучательности.

Проблемой данных подходов является сложность расчётов даже при простых формах объектов. Чтобы вычислить форм-фактор плоскости нам нужно произвести два раза интегрирование, не говоря уже об лишних расчётах. На решение этой проблемы пришёл Hemi-Cube Radiosity.

Hemi-Cube Radiosity

HC имеет схожесть с алгоритмом Nussalt Analog. Суть его была в том, что вокруг точки на плоскости размещается так называемая проекционная полусфера с единичным радиусом. Другая плоскость проецируется на эту полусферу и размещается на базе полусферы. Таким образом форм-фактор будет равен отношению области спроецированной плоскости в базе полусферы к области самой базы полусферы. Алгоритм HC в своей реализации использует, как вы уже могли догадаться, полукуб.

Стороны полукуба разбиваются на набор небольших дискретизированных плоскостей(hemi-cube pixels), каждая из которых имеет свой предрассчитанный форм-фактор. Когда вторая плоскость проецируется на полукуб, сумма форм-факторов дискретных областей на которых была спроецированна плоскость будет равна значению форм-фактора от точки на первой плоскости до второй плоскости.


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

Ambient Occlusion Volume

Во время разработки метода radiosity, Baum D.R. предложил такой метод вычисления форм-фактора:


где Gi — набор граней плоскости, Nj — нормаль дифференциальной плоскости j, Гg — величина равная углу гамма и направлению полученного при векторном произведении Rg и R(g+1), как показано на рисунку снизу:


M. McGuire вдохновился данным подходом и на основе последнего придумал AO алгоритм. Описывал он его так:

Пусть X будет очень маленьким патчем гладкого многообразия. Центроид X будет в точке, которая является началом нормали n. Полигоном P будет полигон с вершинами {p0,...,pk?1}, который полностью расположен на позитивной части плоскости, при условии p*n > 0. Таким образом, преграждение лучей света, создаваемое полигоном P, будет равно форм-фактору излучательной способности между P и X.


где j = (i+1) mod k.

Реализация AOV's

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

Рассмотрим выпуклый полигон P с вершинами {p0,...,pk?1}, которые при любой комбинации из 3-х вершин не создают коллинеарности. Сперва, нам нужно рассчитать затухающую функцию, которая нам понадобиться чтобы добиться плавности при переходах от near- к far-field освещению. Вычисляется она таким образом:


где а — 1 для твёрдых плоскостей, m(i<k) — нормали к граням полигона P, mk — отрицательная нормаль к полигону P:



Выглядит оно таким образом:


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

Хочется внеси еще один новый термин, который называется obscurance. Он отвечает за затухание эффекта перекрытия со сменой расстояния.

Вектор смещения мы получаем таким образом:


где ? является тем самым obescurance на максимальной дистанции.

Для наглядности:


И последним нашим шагом будет произведение затухающей функции( g ) на перекрытие полигоном P ( AOp(n) ). Так же, после всех операций следует применить т.н. blending.

После всего написанного здесь было бы грехом не приложить скриншоты, которые продемонстрируют работу AOV алгоритма. Эти скриншоты были сделаны компанией NVIDIA, а демо можно найти внизу статьи(опять же от NVIDIA).




Для сравнения с Ray Tracing'ом:

Заключение

Мы рассмотрели довольно непростой способ AO. Многие могут остаться недовольны, так как, вероятнее всего, жаждали увидеть реализацию в виде кода. К сожалению, слишком много информации вышло бы лишь для одной статьи. Впрочем, те кто загорелся желанием реализовать данный метод, может копнуть вглубь демо от NVIDIA, которое я приложу снизу.

P.S. У меня есть убедительная просьба к вам, дорогие читатели. Если вы нашли то, что мной описанный метод в некоторых местах является неправильным или просто есть ошибки в плане языка, сообщите мне, попытаюсь исправить все свои недочёты. Если у вас есть потребность увидеть данный алгоритм в виде кода, я попытаюсь выделить время и сделать демо.

> Демо от NVIDIA

Литература

Мной было прочитано достаточное количество источников, но основной упор я делал именно на эти паперы:

— M. McGuire «Ambient Occlusion Volumes»
— «Improving radiosity solutions through the use of analytically determined form-factors»

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