Rambler's Top100
  -   !    !
 


???????@Mail.ru

Rambler's Top100


 

мастерскаяизлучательность

 

Краткий обзор

Общие понятия о синтезе изображений в компьютерной графике.

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

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

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

Конвейерный рендеринг.

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

  • обход сцены;
  • модельные преобразования;
  • простое отсеивание невидимых поверхностей;
  • освещение;
  • преобразования вида;
  • отсечение невидимых поверхностей;
  • преобразование в экранное пространство;
  • растеризация.

На пути реализации вышеприведенных восьми шагов объекты сцены проходят четыре пространства. Первым из этих пространств является локальное пространство объекта. В нем объект имеет только начальные данные: размеры, координаты вершин или формулы поверхностей, цвет – причем все эти данные относительны. Т.е., если радиус шара равен 3, то мы не можем сказать, что это 3 миллиметра или 3 километра. Обход сцены, который представляет собой простое чтение информации о ее объектах и модельные преобразования (перенос, масштабирование, поворот) позволяют создать второе – глобальное пространство сцены, в нем объекты уже получают точные размеры относительно друг друга, мы получаем сцену. Затем производится простое отсеивание «лишних» объектов, например тех, которые находятся позади камеры, так видимые объекты переходят в новое пространство – пространство глаза. Затем сцена входит в фазу обработки освещения, хотя этого вопроса мы еще коснемся позже, потому что эта фаза необязательно производится только над объектами пространства глаза, и необязательно занимает это место в конвейере. Далее следуют перспективные преобразования (видовые), при этом корректируются размеры объектов в зависимости от их удаленности от наблюдателя. Затем происходит еще одна фаза удаления невидимых деталей уже более детальная, причем критерии удаления объектов в первой и второй фазах могут быть различными, в зависимости от построения рендерера. После этого заканчивается пространственная обработка сцены, и все видимые объекты, после соответствующих преобразований переводятся в заключительное, экранное, пространство. В завершение производится растеризация, которая сопоставляет каждой точке экрана цветовую информацию, в зависимости от всех полученных ранее данных, текстуры поверхности, освещения.

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

Методы расчета освещения в сцене.

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

Их можно подразделять по разным параметрам: зависимости от положения наблюдателя, учету всех или только первичных источников света и др. Я остановлюсь на втором случае. С этой точки зрения все алгоритмы расчета освещения можно разделить на две группы: те, которые работают с локальной освещенностью (local illumination) и глобальной освещенностью (global illumination).

Локальная освещенность.

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

Методы этой группы можно разделить на те, которые предполагают, что поверхности рассеивают свет только диффузно (diffuse reflection), т. е. одинаково по всем направлениям и углам отклонения от направления на источник. Представителем таких моделей является, например модель Ламберта.

рис1. Диффузное отражение.

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

рис2. Зеркальное отражение.

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

I = Ia*ka + S Ii*(kd*cosqi + ks*cosnai)

где

Ia – второстепенный свет сцены – не от источников света;

Ii – свет от источника света;

k – соответствующие коэффициенты пространственного, диффузного и зеркального света.

Глобальная освещенность.

Описанные выше модели хороши тем, что они просты в реализации даже на графических акселераторах. Но они не годятся для достижения достаточной реалистичности в сложных сценах. Для того, чтобы корректно учесть взаимодействие между всеми объектами, необходимо использовать системы рендеринга, которые могут рассчитывать глобальную освещенность. В этом случае все объекты сцены воспринимаются, как источники света. Приведу простой пример: луна, сама по себе, не является источником света, но, отражая солнечный свет, она дает большую часть ночного света. Работы в этой области ведутся в текущее время с наибольшей интенсивностью. Существует уже немалое количество методов, с каждым годом они становятся все более корректными физически, также постоянно улучшается их быстродействие. Их можно подразделить на методы, использующие трассировку лучей (ray tracing), фотонные карты (photon mapping), излучательность (radiosity) и методы Монте-Карло. Эта классификация в большой степени условная, потому что многие наработки последних лет совмещают преимущества разных методов.

Трассировка лучей.

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

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

рис3. Трассировка лучей.

Фотонные карты.

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

Затем, после возможных промежуточных действий, на основе энергетической информации фотонных карт производится окончательное формирование засветки. Один из методов реализации окончательных расчетов – оценка плотности (density estimation). В данном случае поверхность разбивается на отдельные участки, на которых рассчитывается количество энергии, попавшей на них, затем световая информация сглаживается относительно соседних участков.

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

Излучательность.

Кратко рассмотрим еще один видонезависимый подход к обработке световой информации о сцене, позже мы остановимся на нем более подробно.

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


БАЗОВЫЙ МЕТОД РАСЧЕТА ИЗЛУЧАТЕЛЬНОСТИ

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

Уравнение излучательности и переход к конечным элементам.

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

(1)

где

Bi – излучательность исследуемого элемента;

Bj – излучательность элемента, взаимодействующего с исследуемым;

Ei – энергия, излучаемая поверхностью, не равна нулю только для источников света и зеркальных поверхностей;

ri – коэффициент отражения поверхности;

A – площадь элемента;

Обычно интегральный элемент(2) за меняется на Fij, эта величина называется коэффициентом формы (Form Factor), она довольно сложна в вычислении. О методах вычисления коэффициентов формы поговорим позже.

Bi = Ei + ri*SBj*Fji(Aj/Ai)

Последнее уравнение легко упрощается до

Bi = Ei + ri*SBj*Fji

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

рис5. Переход к конечным элементам

Вычисление коэффициентов формы проецированием на полукуб.

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

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

F = Aр/pr2 = Aр/p , т.к. описана единичная сфера.

где Ар – проекция на сферу.

рис6. Вычисление коэффициентов формы.

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

Матрица излучательности.

В итоге мы получаем систему уравнений излучательности:
B1 = E1 + (r1 F11 + r1 F12 + … + r1 F1n)*B1
B2 = E2 + (r2 F21 + r1 F22 + … + r1 F2n)*B2
………………………………………………….
Bn = En + (rn Fn1 + r1 Fn2 + … + r1 Fnn)*Bn

Эта система решается просто численными методами, например, методом Гаусса-Зейделя. С этого момента нам известны все излучательности в сцене, остается только последний этап – реконструкция изображения.

Реконструкция.

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

Проблемы.

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

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

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

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

УСОВЕРШЕНСТВОВАННЫЕ МЕТОДЫ РАСЧЕТА ИЗЛУЧАТЕЛЬНОСТИ

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

Прогрессивный выбор элементов.

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

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

рис7. Отдача излучательности.

Описанный метод по-другому называют методом отдачи излучательности, в то время как метод Гаусса-Зейделя – метод сбора.

Структурирование и адаптивное разбиение.

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

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

Иерархический.

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

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

рис8. Иерархическое разбиение.

Разбиение на кластеры.

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

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

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

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

рис9. Альфа- и бета-связи.

Дополительно можно почитать:

  1. Эдвард Эйнждел Интерактивная компьютерная графика. Вводный курс на базе OpenGL».
  2. Andrew Wilmott, Paul Heckbert “An empirical comparison of radiosity algorithms”.
  3. Stephan Scafer “Efficient object-based hierarchical radiosity methods”.
  4. Frank Bullesfeld “Final gathering”.
  5. Michael Cohen, Shenchang Chen, John Wallace, Donald P. Greenberg “A progressive refinement approach to fast radiosity image generation”.
  6. Michael Cohen, Donald P. Greenberg “The hemicube: a radiosity solution for complex environments”.
  7. Per Christensen “Hierarchical techniques for glossy global illumination”.
  8. Michael Cohen, John Wallace “Radiosity and realistic image synthesis”.
  9. Andrew Glassner “Introduction to ray tracing”.