История развития алгоритмов глобального освещения

В данной статье рассматривается широко распространенный класс алгоритмов фотореалистичного синтеза – алгоритмы глобального освещения


Введение

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

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

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

 В данной статье рассматривается широко распространенный класс алгоритмов фотореалистичного синтеза – алгоритмы глобального освещения. Прежде чем дать точное определение, обратимся к некоторым известным фактам по природе света.

1.История развития знаний о природе света.

Первые теории о физической природе света зародились еще в Древней Греции. Свой вклад внесли такие известные древнегреческие философы, как Пифагор, Демокрит, Платон, Аристолель и др. Многие представления о природе света в то время были противоречивы. Несмотря на неверные посылки, именно тогда впервые было открыто важное свойство света – закон прямолинейного распространения света. Появились и первые работы об отражении света (Евклид).

 В средние века знание о природе света практически не развивалось. Основным достижением того времени является закон идеального отражения. Позже в 1611 году Кеплер  открыл эффект полного внутреннего отражения. В 1621 году Снелл вывел закон преломления света. В 1657 году Ферма преобразует принцип прямолинейного распространения света в принцип наикратчайшего времени. В это время полностью сформировалась теория геометрической оптики.

 Более поздние открытия дифракции, поляризации, дисперсии (Ньютон), интерференции (Юнг) света показали несостоятельность корпускулярной модели света, что привело к рождению волновой модели света. В 1821 году Френель вывел закон расчета интенсивности света, основываясь на его волновой природе. Параллельно с этим появились работы Максвелла и Герца, подтверждавшие волновую природу света.

 Позднее уже в XX веке с развитием квантовой механики(Планк) пришло осознание неполноты волновой теории света. Стало очевидно, что природа света противоречива – свет ведет себя и как поток частиц, и как волна. Ряд великих ученых (Бор, Шредингер, Дирак и др.) сформулировали концепцию дуализма природы света.

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

2. Определение глобального освещения

Различные материалы, из которых сделаны объекты сцены, по-разному взаимодействуют со светом. Часть энергии при таком взаимодействии отражается, часть – преломляется, а оставшаяся часть – поглощается. Возможен еще случай, когда материал сам излучает свет. Когда луч света приходит от источника света и попадает на поверхность объекта, он может отразиться. При этом отраженный луч может попасть на поверхность другого (или того же) объекта. Луч, который приходит непосредственно от источника света, называется первичным. Луч, который претерпел одно или несколько переотражений, называется вторичным. Можно построить такую физическую модель света, которая будет учитывать только первичное освещение (первичные лучи). При этом может значительно пострадать качество синтезируемых изображений (пример на Рис. 1).













             Рис.1. Изображения только с первичным освещением (слева) и со вторичным освещением (справа).


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

Локальные модели исторически появились на более раннем этапе. Сначала Гуро и Фонг  предложили собственные алгоритмы расчета каждого пикселя изображения. При этом учитывалось только взаимодействие материала со светом непосредственно от источника света. Фонг предложил модель отражательных свойств материала, которая не являлась физически корректной, однако она была удачна с точки зрения фотореалистичности и простоты расчета освещенности. Позже исследователи занялись вопросом наложения текстур на объекты. Появились также первые методы расчета теней – сначала от точечных источников света, затем – более общего вида.

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

Другой знаменитый алгоритм был разработан в Корнельском университете в 1984 году. Это алгоритм излучательности (radiosity). Физическая модель у этого алгоритма более простая, чем у трассировки лучей – система должна быть замкнута (чтобы соблюдался закон сохранения энергии) и все материалы в сцене должны быть диффузными (определение см. ниже). Алгоритм был очень популярен в свое время (в основном из-за возможности интерактивной реализации, т.е. когда возможен расчет порядка 15-25 изображений в секунду), однако обладал рядом недостатков.

В 1986 году Каджия формализовал задачу, которую должны решать алгоритмы глобального освещения. В своей работе он привел полное уравнение распространения света в сцене.. В частности, именно тогда зародилось понятие двулучевой функции отражения (ДФО или BRDF). ДФО [14] – это характеристика конкретного материала, показывающая долю энергии, отраженной от материала в зависимости от направления на источник света и на камеру и длины волны света (см. Рис.2):

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

Рис.2. Двулучевая функция отражения (ДФО)

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

 Поскольку интегралы можно вычислять и более изощренными методами, то появление новых алгоритмов не заставило себя ждать. Наиболее распространенным примером является алгоритм трассировки Монте-Карло (направление стохастических алгоритмов трассировки  Идея этого алгоритма широко используется в настоящее время.

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

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

3. Алгоритм излучательности (radiosity).

 Алгоритм излучательности рассматривает частный случай решения уравнения освещенности, когда материалы являются диффузными. Материал называется диффузным, если вся энергия, отраженная от его поверхности рассеивается равномерно по всем направлениям. ДФО диффузных материалов равняется константе, поэтому интеграл в уравнении освещенности принимает более простой вид. На практике материалы далеко не всегда являются диффузными, возможен случай существования нескольких максимумов ДФО (в англоязычной литературе такие материалы называются glossy materials– см. Рис. 1).

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

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

4. Алгоритмы на базе трассировки лучей, стохастические алгоритмы (метод Монте-Карло).

 Как было упомянуто в  фотореалистичный синтез изображений основан на расчете интеграла освещенности. Стандартное решение – использовать квадратуры. Для этого необходимо разбить пространство, по которому производится интегрирование, равномерной сеткой. Количество узлов при этом существенно зависит от размерности пространства. Пусть N – шаг сетки, тогда общее число узлов будет равно Nd, где d – размерность пространства. Рост числа узлов приводит к росту вычислительной сложности алгоритма.

 Альтернативным решением является метод Монте-Карло. Узлы для интегрирования выбираются случайно (часто специальным образом), и их число не зависит от размерности пространства, по которому считается интеграл. При увеличении числа узлов (или сэмплов в терминологии алгоритма трассировки лучей) интеграл, рассчитанный методом Монте-Карло, приближается к точному значению. При этом результирующее изображение сильно зашумлено при недостаточном количестве узлов. По мере увеличения числа узлов качество изображения улучшается (см. Рис.6).

Рис.6. Результаты визуализации одной и той же сцены методом Монте-Карло с разным количеством узлов на пиксель (слева направо - 8, 40, 200, 1000, 5000, 25000)

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

4.1. Алгоритм Ray-casting.

Данный алгоритм не является полноценным алгоритмом глобального освещения. Тем не менее, он позволяет помимо расчета первичного освещения производить расчет теней. Идея алгоритма очень проста. Из камеры испускаются лучи, для каждого луча ищется первое пересечение с объектом. Далее из каждой точки пересечения испускается луч до источника света. Если этот луч пересечется с каким-то другим объектом по пути к источнику, то это означает, что точка находится в тени. Иначе можно рассчитать долю энергии, которая доходит от источника до камеры. Схема алгоритма представлена на Рис.7.

Рис. 7. Схема алгоритма Ray-casting (сферами обозначены объекты, лампочкой - источник света).

4.2. Алгоритмы Visibility ray-tracing и трассировка фотонов.

Более сложным алгоритмом является алгоритм Visibility ray-tracing. Схема алгоритма приведена на Рис.8. Основная идея состоит в том, что луч из камеры претерпевает несколько идеальных отражений и преломлений, прежде чем будет произведена проверка нахождения точки в тени (последний луч всегда идет в источник, как и в ray-casting). Преломленные и отраженные вектора рассчитываются по известным законам идеального отражения и преломления. Стоит заметить, что в этом алгоритме считается, что материалы имеют постоянные коэффициенты отражения и преломления (независимо от угла падения и отражения/преломления света). Для других материалов отражением и преломлением пренебрегается, луч идет сразу в источник света.

Рис. 8. Схема алгоритма Visibilty ray-tracing.

Трассировка фотонов – это инверсия Visibility ray-tracing. Лучи трассируются из источника света (он может быть и не точечный). Схема приведена на Рис.9.

Рис.9. Схема алгоритма трассировки фотонов.

4.3. Распределенная трассировка лучей(distributed ray-tracing).

В 1984 году Кук предложил алгоритм распределенной трассировки лучей (см. Рис. 10). Этот алгоритм позволял визуализировать материалы с произвольными двулучевыми функциями отражения. В отличие от алгоритма Visibility ray-tracing модель отражения в этом алгоритме более сложная (можно моделировать не только идеальные зеркала). При попадании луча на поверхность генерируется множество отраженных лучей. Процесс испускания множества лучей называется сэмплированием ДФО (BRDF sampling). Направления лучей выбираются в зависимости от значения ДФО – количество испускаемых лучей по направлению пропорционально значению ДФО по этому же направлению. Качество этого алгоритма самое высокое из всех рассмотренных выше. Однако из-за сэмплирования алгоритм имеет и самую высокую вычислительную сложность.

Рис.10. Распределенная трассировка лучей.

4.4. Алгоритм трассировки путей.

 В 1986 году Каджия предложил новый алгоритм под названием трассировка путей (Рис.11). При попадании луча на поверхность испускается два новых луча: один - в произвольном направлении («русская рулетка»), другой – до источника света. Доля отразившейся энергии при этом рассчитывается на основе ДФО (либо испускается луч с одной и той же энергией по принципу «русской рулетки», при этом вероятность испускания вычисляется на основе ДФО). Работа алгоритма прекращается, если длина пути достигает некоторой константы, называемой глубиной трассировки. 

Рис.11. Трассировка путей.

4.5. Алгоритмы прямой трассировки лучей.

 Практически все рассмотренные выше алгоритмы являлись примерами обратной трассировки лучей, когда трассировка ведется от камеры. Трассировка фотонов  – чуть ли не единственное исключение. Причина довольно редкого использования прямой трассировки (от источника света) в более медленной скорости сходимости алгоритма. Однако есть ряд эффектов, которые лучше моделируются при помощи прямой трассировки. Например, эффект каустиков от преломляющих поверхностей (см. Рис. 12). Существуют гибридные алгоритмы, умело использующие это свойство прямой трассировки.

Рис.12. Примеры каустиков.

5. Гибридные алгоритмы.

 После появления и развития двух основных алгоритмов расчета глобального освещения (трассировка лучей и алгоритм излучательности) появилось большое число работ, попытавшихся совместить положительные качества обоих алгоритмов. Метод излучательности позволяет быстро рассчитывать освещение для диффузных поверхностей. Применять его для поверхностей с произвольными ДФО невозможно. У метода излучательности есть проблемы с расчетом мягких теней, в то время как у трассировки лучей таких проблем нет. Основным же недостатком трассировки лучей является низкая скорость. В многопроходных алгоритмах расчет освещенности делится на независимые этапы. Например, алгоритм излучательности рассчитывает только влияние диффузных слагаемых материалов друг на друга (из любой ДФО всегда можно выделить диффузную часть и зеркальную), трассировка же учитывает взаимодействие зеркальных слагаемых с другими зеркальными или диффузными слагаемыми. Наиболее известными многопроходными алгоритмами являются двухпроходный алгоритм Силлиона, трехпроходный Ширли и многопроходный прогрессивный алгоритм Чена.

 Заключение. . . 

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

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