Game Engine своими руками #6: Radiosity

Эта тема не входила в мои планы, но выискался один неугомонный чел (dan-leech, привет!), который решил, что рассказанного мной про освещение в играх ему недостаточно и попросил поведать всему миру о такой шняге, как Radiosity, посетовав на то, что, мол, в инете нету путевых туторов и экзамплов по этой немаловажной теме.

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

Физика света

Для того чтобы построить точное освещение 3D сцены, нам необходимо определить каким образом происходит распределение света, а точнее световой энергии в пространстве.

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

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

Но фотоны не движутся все в одну сторону, сталкиваясь с различными препятствиями, они разлетаются и движутся по различным направлениям, поэтому для полного описания распределения света в 3D сцене, нам потребуется некая функция, которая позволила бы определить энергетическую освещенность для любой точки сцены и для любого направления. Таким образом, мы приходим к понятию силы излучения.

Силой излучения называется поток излучения источника в рассматриваемом направлении, отнесенный к единичному телесному углу:

Важное свойство силы излучения: Для любых двух взаимовидимых точек x и y (разделенных вакуумом) сила излучения выходящая из точки x в направлении точки y будет такой же, как и сила излучения приходящая в точку y по направлению из точки x.

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

Чтобы количественно описать процесс отражения падающего света поверхностью, вводят, так называемую, функцию двунаправленного отражения (Bidirectional Reflection Distribution Function) сокращенно BRDF. Функция BRDF показывает, какая именно доля световой энергии, пришедшей в направлении, задаваемом вектором l, уходит в направлении, задаваемом вектором v, и имеет вид:

В общем случае BRDF удовлетворяет условию симметричности (принцип Гельмгольца), т.е. BRDF(l, v) = BRDF (v, l).

Вспомогательные функции

Так как мы рассматриваем освещение 3D сцены, то вполне допустимым является тот факт, что луч от одной точки пространства не дойдет до другой точки из-за того, что пересечет какую-нибудь поверхность, поэтому вводят вспомогательную функцию V(x, y), которая равняется 0 если луч, пущенный из точки x в точку y, будет загорожен поверхностью, и 1 в противном случае.

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

И наконец, функция E(x, y) показывает какая часть самостоятельного излучения точки х дойдет до точки y.

Основное уравнение визуализации

Под этим страшным названием я имел ввиду ни что иное, как всем известное Rendering Equation, с решением которого можно постичь таинство построения фотореалистичных изображений 🙂

Представь себе точку x' на поверхности. Откуда взялась световая энергия, которая излучается этой точкой в направлении другой точки x''? А это всего лишь сумма отраженной энергии и энергии излучаемой точкой самостоятельно. А чего отражалось? Правильно, лучи, которые пришли в эту точку от всех остальных точек х.

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

Global illumination

Для моделирования освещения объектов и сцен существует огромное количество различных алгоритмов, но в общем случае их можно разделить на две группы: алгоритмы локального освещения (local illumination) и алгоритмы глобального освещения (global illumination).

Алгоритмы локального освещения - это самые простые способы расчета освещенности поверхностей. Они рассматривают каждую поверхность 3D сцены независимо от других поверхностей, принимая во внимание, при расчете освещения, только первичные источники света. В играх алгоритмы local illumination используются для расчета динамического освещения моделей.

Для расчета более корректного и реалистичного освещения применяются алгоритмы глобального освещения, т.е. алгоритмы, которые учитывают весь путь света от первичных источников, до его полного затухания, в результате переотражения, преломления, рассеивания и т.п. Главной целью алгоритмов global illumination ставится решение основного уравнения визуализации, но ввиду того, что это уравнение не имеет аналитического решения, на практике применяются два основных способа аппроксимации - это метод трассировки лучей (ray tracing) и Radiosity.

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

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

Метод Radiosity лишен подобного недостатка, т.к. позволяет выполнить расчет всего освещения заранее.

Radiosity

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

После принятия такого упрощения мы можем вынести функцию BRDF из-под знака интеграла, т.к. она будет постоянной. В результате имеем основное уравнение
Radiosity:

Здесь B(x) - это энергия рассеиваемая элементом:

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

В результате описанных выше не сложных умозаключений мы на качественно новом уровне приходим к понятию карт освещенности (см. #4), т.е. лайтмэпам (light map). И ты, наверное, уже сам догадался, что под "дискретными элементами конечной величины" подразумевались именно точки лайтмэпов.

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

Затем, собственно, и начинается само Radiosity: представив, что каждый элемент поверхности является самостоятельным источником световой энергии, которую он получил от первичных источников света, мы рассчитываем вторичную освещенность, т.е учитываем влияние одних элементов на другие. Каждый элемент, получив какое-то количество световой энергии, часть этой энергии поглощает, а другую часть рассеивает обратно в пространство, таким образом, проход за проходом мы рассчитываем распределение световой энергии между поверхностями сцены до тех пор, пока не установится некоторое равновесие.

Очевидно, что из-за наложенных ограничений, метод Radiosity подходит только для расчета диффузных межотражений света между поверхностями (что, кстати, не под силу методу трассировки лучей) и не позволяет передать зеркальные отражения и элементы прозрачности. Поэтому обычно в профессиональных системах визуализации используются комбинированные алгоритмы, совмещающие трассировку лучей и Radiosity. Но в играх, где требуется рендеринг сложных сцен в реальном времени, трассировка лучей обычно заменяется более простыми методами, так вместо честного расчета отражений на блестящих объектах применяется наложение карт среды (environmental mapping), а для передачи полупрозрачности используется альфа-блендинг.

Оптимизация

В отличие от пакетов трехмерного моделирования и визуализации, где сцены представлены грубым набором полигонов безо всякого порядка
"polygon soup", твой движок, скорее всего, будет использовать какой-нибудь тип деревьев для установления иерархических взаимоотношений между элементами геометрии, будь то Quad-деревья, Oct-деревья, BSP или порталы. Этим-то и надо воспользоваться в первую очередь для ускорения расчета освещения.

Во-первых, при расчете освещения нужно использовать только те элементы поверхностей, которые точно будут оказывать какое-то влияние на данный элемент. Т.е. если у нас имеется построенный набор PVS, то мы легко можем определить, какие поверхности смогут передать часть своей световой энергии полигону, а какие нет. Поверхности, повернутые обратной стороной к элементу, так же не оказывают ни какого воздействия на элемент.

Во-вторых, вместо тупого перебора всех пар элементов, что приводит к расчету освещения N^2 раз между N элементов, для каждого полигона можно построить quad-дерево элементов (Hierarchical Radiosity) и воспользоваться очевидными плюсами этого подхода. То есть мы рассматриваем влияние окружающих поверхностей на корневой элемент дерева, а потом рекурсивно спускаемся по ветвям дерева, избегая ветви на которые ни какого влияния оказано не было.

В общем, оптимизация процесса Radiosity полностью определяется контекстом применения, поэтому тебе самому решать, что и как можно оптимизировать 😉

Реализация

Написать программу реализующую расчет освещения с применением Radiosity не так сложно, как это может показаться на первый взгляд. Для начала нам нужно придумать структуру, которая могла бы описать один элемент поверхности, например:

typedef struct {
bool enabled;
int planenum;
float origin[3];
float color[3];
float emitColor[3];
} sample_t;

bool enabled: Этот флажок будет говорить нам о том стоит или нет учитывать данный элемент при расчете освещения.

int planenum: Это номер поверхности которой принадлежит данный элемент. 

float origin[3]: Это координаты (x, y, z) элемента в пространстве.

float color[3]: Это результирующий цвет, приобретенный элементом в результате освещения принятого от первичных и вторичных источников. Цвет задается тремя нормализованными (приведенными к интервалу [0..1]) компонентами RGB.

float emitColor[3]: Это цвет излучаемый элементом, т.е. это световая энергия, которую элемент отражает в окружающий мир.

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

/* Простой алгоритм для расчета первичной освещенности элемента. */

// одна треть рассеивается
sample->emitColor[0] += 0.3333 * add * light.color[0];
sample->emitColor[1] += 0.3333 * add * light.color[1];
sample->emitColor[2] += 0.3333 * add * light.color[2];
}

В листинге встретилась функция TraceLine - это твой трассировщик лучей, возвращает FALSE если луч из одной точки до другой был пересечен каким-нибудь полигоном сцены и TRUE если луч не был загорожен.

После расчета первичной освещенности начинается процесс расчета Radiosity. Чтобы рассчитать распределение энергии (form factor) между двумя элементами можно воспользоваться следующей простой аппроксимацией, которая следует непосредственно из основного уравнения Radiosity:

F(i, j) = cos(Ai) * cos(Aj) * Aj / (PI * Rsqr + Aj)

Здесь F(i, j) - количество энергии переданное от элемента i элементу j.
Ai - это угол между нормалью в точке i и отрезком L соединяющем элементы.
Aj - это угол между нормалью в точке j и L.
Rsqr - это квадрат расстояния между элементами, т.е. L^2.
PI - это число ПИ (приблизительно 3.14159265358979323846)

Здесь листинг тебе особо не поможет т.к. расчет Radiosity - процесс сугубо индивидуальный для каждой программы, но вот как должна примерно выглядеть функция, которая рассчитывает form factor между двумя элементами.

/*
==============
FormFactor
==============
*/
void FormFactor (sample_t *sample1, sample_t *sample2)
{
float ffactor, dist, angle1, angle2;
float dir[3];

}

Когда мы рассчитали влияние одного элемента на все остальные элементы, то должны обнулить его излучающую энергию (emitColor). Затем когда мы будем рассчитывать Radiosity от другого элемента, то к первому элементу опять перейдет частичка чужой энергии. Так световая энергия будет распределятся между элементами и когда она станет меньше какого-то значения, мы должны все прекратить.

#define MIN_ENERGY 0.01

if (sample->emitColor[0] +
sample->emitColor[1] +
sample->emitColor[2] < MIN_ENERGY)
sample->enabled = false;

Бонус

Ну и напоследок я расскажу об одном классном бонусе Radiosity.

Помнится в третьем Кваке была такая фишка как "светящиеся поверхности", т.е. специальный тип шейдеров, который учитывался при расчете освещения утилитой q3map. Так вот если покопаться в исходниках этого q3map, то можно выяснить, что для имитации светящихся поверхностей Кармак не придумал ни чего умнее кроме как развесить кучи лампочек над этими поверхностями и таким вот образом изобразить их светимость. В результате если сделать в третьем Кваке здоровый бассейн светящейся лавы, то можно увидеть, что его поверхность будет покрыта яркими пятнами - это места, над которыми и вешались эти лампочки. Так вот если бы Кармак не поленился и написал достойную реализацию Radiosity, такой проблемы вообще бы не было. И действительно, достаточно точкам светящихся поверхностей, участвующих в расчете освещения, присвоить дополнительные порции световой энергии, как после расчета Radiosity эти поверхности засветятся сами собой!

Блин, по-моему, я тебя уже достал этой мурой 😉

Поки!