Интерактивный рендеринг при помощи сферических дизайнов для низкочастотного окружающего освещения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Свистунов, Сергей Сергеевич

• Свистунов, Сергей Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Свистунов, Сергей Сергеевич

Оглавление

Список основных обозначений

Введение

Глава 1. Моделирование на основе уравнения рендеринга для

первичного отраженного освещения

1.1. Задача моделирования отраженного освещения

1.1.1. Уравнение рендеринга для первичного освещения

1.1.2. Интегральное уравнение рендеринга Каруа

1.1.3. Описание функций из уравнения рендеринга

1.2. Низкочастотное окружающее освещение

1.2.1. Элементы гармонического анализа на сфере Б2

1.2.2. Численные методы интегрирования

1.2.3. Определение низкочастотного окружающего освещения

1.3. Аппроксимация уравнения рендеринга для первичного освещения

1.3.1. Учет низкочастотного окружающего освещения

1.3.2. Метод РКГ

Глава 2. Аппроксимация уравнения рендеринга при помощи

метода сферических дизайнов

2.1. Взвешенные сферические дизайны

2.1.1. Определение дизайнов

2.1.2. Примеры дизайнов для единичного веса

2.2. Метод сферических дизайнов

2.2.1. Приближение функции видимости

2.2.2. Приближенное вычисление отраженного освещения

при помощи сферических дизайнов

2.3. Численные методы построения взвешенных дизайнов

2.3.1. Метод проекции градиента

2.3.2. Метод произведения гауссовских квадратур

Глава 3. Реализация метода сферических дизайнов

3.1. Задача интерактивного рендеринга

3.1.1. Постановка задачи

3.1.2. Используемые технологии

3.2. Вычислительные модели метода сферических дизайнов

3.2.1. Случай приближения функции видимости V частичной суммой ряда Фурье

3.2.2. Случай приближения V частичными суммами ряда Фурье произведений Vyim

3.3. Алгоритмы метода сферических дизайнов

3.3.1. Логика организации вычислений

3.3.2. Предрасчитываемая информация

3.3.3. Расчеты в интерактивном режиме

3.4. Описание комплекса программ

3.4.1. Структура и утилиты

3.4.2. Интерфейс и демонстрационное приложение

Список литературы

Список основных обозначений

М — числовая ось, R3 — трехмерное евклидово пространство

ху = х • у = xiyi + Х2У2 + ХзУз — скалярное произведение векторов х = (Х1,Х2,Х3), у = (ух, У2, Уз) Е М3

= у/хх — длина вектора х

е\ = (1,0,0), ег = (0,1,0), ез = (0,0,1) — единичные орты

S2 — {х € К3: = 1} — единичная евклидова сфера в R3

dfx(x) = dx/(47t) — инвариантная относительно вращений SO(3) нормированная (fs2 dju(x) — 1) мера на сфере

L/2{S2) — пространство функций /: S2 ->1с конечной нормой ||/||\ — (/, /) = fs2 f(x)dfi(x)

д £ 50(3) — вращение или ортогональная матрица размера 3x3, ддт = е,

т ( 1 о о \

д — транспонированная матрица, е = I о i о J — единичная матрица,

det д —

дх G SO(3) — вращение, переводящее орт ез в точку х G S2

(<р,0) — сферические координаты точки х = (cos (р sin в, sin <р sin 0, cos в) G S2, 0 ^ <р < 2тг, ОО^тг

р G К3 — точка (вершина) поверхности модели п = пр £ S2 — вектор нормали к поверхности модели в точке р хп — (2(пх)п — х) — зеркальный к х относительно п вектор (£)+ = max (0, t)

6(t) = 1 при t > 0 и Q(t) = 0 при t ^ 0 (функция Хевисайда)

Ь(х) — функция яркости удаленного окружающего освещения

Ур(ж) — функция видимости в точке модели р, равная 0, если луч, выпущенный из р по направлению х, пересекает модель, и 1 иначе

рр(х,у) — двунаправленная функция отражательной способности (ДФОС) с учтенным ламбертовским множителем (прх)+

рь{пх) = 4(пх)+ — ДФОС Ламберта

и)а(хпУ) — и>а(упх) — ДФОС Фонга, где и>а(Ь) = (2а + 2), <х > О — показатель Фонга

— функция яркости отраженного освещения в точке р по направлению V е Б2

— одно из приближенных выражений для Вр(у,д)

У 1т, I — 0,1,2,..., т — — действительные ортонормированные сфе-

рические гармоники

<51т,1'т' = &и>5гпт' = (У1гп,У1>т>) — символы Кронекера

¿1 — 21 + 1 — размерность базиса гармоник у1т порядка I

Р™ — присоединенные функции Лежандра

Рг — многочлены Лежандра

р(а,р) — многочлены Якоби

В[пт> (я) — матрицы вращения сферических гармоник (/^-функции Вигнера)

Сгт7'т' — (,У1тУ1>т',У1"т") — коэффициенты Клебша-Гордана для сферических гармоник, \1-1'\ + I', -I" ^ га" = т + т! ^ I"

К8 — сферическое ядро Дирихле

$1гп — коэффициенты Фурье функции / € 1/2 (52)

Е^О /1тУ1тп — ряд Фурье функции / € Ь2(52)

1 - о Е|т|</ /1тУ1тп ~ частичная сумма ряда Фурье функции / € Ь2(32) порядка в

и(ах) — зональная функция, а € Я2 — фиксированная точка (полюс) сферы,

^ = (1/2

(ш * f)(x) = Js2 tü(xx')f(x')dß(x') — сферическая свертка зональной функции uj с функцией /

Vb = Voo = Js2 dß(x) — коэффициент затенения

X = {x ши, ^шиУи^х — взвешенный сферический дизайн с неотрицательной весовой функцией (весом) и>

О(-),

Буфер глубины — двумерный массив данных (текстура), в котором сохраняется расстояние от наблюдателя до поверхности объекта

Графический конвейер — программно-аппаратный многоступенчатый процесс, преобразующий 3D-сцепу в кадр

Кубическая карта окружения (Cubemap) — текстура из шести изображений (фотографий)

Рендеринг (моделирование или визуализация) — процесс получения изображения по данным ЗО-сцены

Модель (меш) — множество вершин, нормалей, полигонов и других параметров, задающих объект (модель) в сцене

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

Шейдер (Shader) — программа, выполняемая на GPU для одной из ступеней графического конвейера

Ядро (Kernel) — программа, выполняемая в параллельном режиме на GPU

CPU (Central Processing Unit) — центральный процессор

DirectX, OpenGL — графические библиотеки

FPS (Frame per second) — число кадров в секунду

GPU (Graphics Processing Unit) — графический процессор (видеокарта)

NVIDIA CUDA, OpenCL — технологии, позволяющие использовать GPU для параллельных вычислений

Offline (предрасчет) — предварительный этап сложных вычислений, па котором рассчитывается и сохраняется необходимая для вычислений в реальном времени информация

Online — этап вычислений в режиме реального времени

PRT (Precomputed Radiance Transfer) — метод предварительного расчета из-лучательной способности модели

Realtime — режим реального времени

Reflection Equation — уравнение рендеринга для первичного отраженного освещения

Введение диссертации (часть автореферата) на тему «Интерактивный рендеринг при помощи сферических дизайнов для низкочастотного окружающего освещения»

Введение

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

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

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

Информацию о ЗБ-модели образуют координаты вершин модели, полигоны (индексы вершин, с помощью которых они образуются), нормали (задаются для вершин и/или полигонов), ребра (пары индексов вершин).

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

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

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

Свет от источника освещения (L), попадая на различные поверхности, отражается. Именно на основе отраженного освещения (В) строиться итоговое изображение (кадр). При этом фотореалистичность достигает за счет учета физических законов распространения света. В работе рассматривается случай первичного освещения, когда лучи света однократно отражаются от поверхности. Такой модели распространения света в компьютерной графике отвечает уравнение рендеринга для первичного отраженного освещения (Reflection Equation) [17, 37]. Оно имеет вид

Здесь 52 — единичная сфера, (¿//(ж) = ¿х/(4тг), Вр(у,д) — функция яркости отраженного освещения в точке модели р по направлению V £ д 6 50(3) — вращение карты окружения относительно базового положения, Ь Е 1,2 (52) — функция яркости удаленного окружающего

ДФОС с учтенным ламбертовским множителем (прх)+ = max (0, прх), где пр — нормаль поверхности модели в точке р.

(1)

освещения, Vp € L2(S2) — функция видимости в точке р, pp(x,v)

Приведем вывод уравнения (1) на основе физики света, который содержится в книге [16]). Необходимо выразить яркость отраженного освещения в точке р (Вр) через яркость падающего окружающего освещения (L). Пусть Ф = — поток лучистой энергии (Вт), где

(JLL

Q = Q(p>t) ~~ энергия светового потока (Дж), р € К3, t — время (с). Рассматривается случай стационарного потока (Ф не зависит от времени). Через dA обозначим некоторую элементарную площадку в пространстве (м2) с центром в точке р и нормалью п. Освещенность Е

,, г, йФ

площадки аА определяется равенством: Ь — -—.

аА

Пусть х е S2 — некоторое направление в точке р, dx — соответствующий этому направлению телесный угол, ¿¡i{x) = dx/(4тт) — нормированный телесный угол. Тогда яркость падающего освещения определяется формулой

Цх) = -^Рг-у (2)

cos в dfi(x)

где в — угол между х и п. Для непрозрачной площадки учитываются только направления, для которых в G [0,7г/2). В случае удаленного окружающего освещения L зависит только от х (не зависит от положения площадки).

Определим яркость отраженного освещения В в точке р по направлению v Е S2 с учетом излучательных свойств материала модели. Они задаются при помощи ДФОС

I \ dB(v)

p{x'v) = шщ- (3)

ДФОС p(x,v) является безразмерной функцией, определяющей как окружающее освещение, приходящее в точку р с направления х (Е(х)), рассеивается в направлении v (B(v)). Из формул (2) и (3) следует, что

dB{v) = p(x,v) dE(x) = L(x)p(x,v) cosO dfi(x),

или, учитывая непрозрачность модели,

dB(v) = L(x)p(x,v) dfi(x), 10

где р(х,у) — р(х,у) сов 9 = р(х,у)(пх)+ — ДФОС с учтенным ламбер-товским множителем. Отсюда, окончательно, получаем уравнение рендеринга в виде

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

Уравнение (1) отвечает локальной модели освещения, поскольку не учитываются переотраженные от точек модели лучи. Оно является частным случаем общего уравнения рендеринга Ка,цуа [17, 27] для вторичного освещения, которое включает первичное освещение и учитывает переотражения. Уравнение Ка.цуа отвечает глобальной модели освещения. Оно имеет сложный вид и применяется в методе трассировки лучей. Для интерактивного режима уравнение Ка^уа используется, в основном, при моделировании диффузных поверхностей.

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

Задача интерактивного рендеринга, когда в качестве источника освещения выступает карта окружения, исследовалась многими авторами [24, 36, 38, 44]. При этом моделирование, как правило, осуществлялось именно на основе аппроксимации уравнения рендеринга для первичного отраженного освещения (1).

В начале 2000 годов для аппроксимации уравнения рендеринга был

(4)

11

разработан метод предварительного расчета излучательной способности модели — Precomputed Radiance Transfer или PRT. Этот метод использует разложения подинтегральных функций в сферические ряды Фурье и их приближения частичными суммами (метод сферических гармоник). В PRT рассматривается только низкочастотное окружающее освещения, когда L хорошо приближается в Z^S2) частичной суммой ряда Фурье L малого порядка. В случае высокочастотного освещения возникают суммы большого порядка, которые не применяются при вычислениях в интерактивном режиме.

В 2001 году R. Ramamoorthi, P. Hanrahan [38] рассмотрели уравнение рендеринга (1) без учета функции видимости (т.е. в виде (4)). В этом случае не учитывается затенения и картинка получается не совсем реалистичной. Результаты работы [38] вошли в диссертацию R. Ramamoorthi [36], в которой были рассмотрены диффузные, зеркальные и более общие поверхности.

Собственно метод PRT с учетом функции видимости и, как следствие, более реалистичной картинкой был разработан в 2002 году P. Sloan, J. Kautz и J. Snyder в [44]. В нем для решении задачи интерактивного рендеринга со сложным освещением используется некоторая заранее рассчитанная информация — сферические коэффициенты Фурье падающего освещения и функции транспорта модели, содержащей функцию видимости и ДФОС. Отметим, что результаты работы [44] оказались особенно эффективными в диффузном случае ДФОС Ламберта, когда свет рассеивается во всех направлениях одинаково. В зеркальном же случае ДФОС Фонга, когда есть яркая зависимость от заранее неизвестного направления, возникли сложности при реализации.

В 2003 году R. Green в статье [24] приводит подробные сведения, необходимые для реализации метода PRT в случае диффузной поверхности. В частности, он привел расчетные формулы Монте-Карло для сферических коэффициентов Фурье карты окружения, формулы для быстрого вычисления матриц вращения сферических гармоник и примеры программного кода.

В 2009 году R. Ramamoorthi [37] подробно изложил историю отмеченных задач и достигнутые на тот момент результаты по проблематике интерактивного рендеринга, включая многие аспекты метода PRT: использование вейвлетов, высокочастотное освещение, проблемы обратного рендеринга и др. Эти задачи имеют свою специфику и здесь не рассматриваются.

Метод PRT на основе сферических гармоник продолжает развиваться. Он реализован в SDK DirectX [50], но только для ламбертовских поверхностей.

Актуальной проблемой интерактивного рендеринга, в том числе основанного на методе PRT, является задача получения мягких теней. Как уже упоминалось, моделирование освещения на основе уравнения рендеринга позволяет получить их за счет входящей в него функции видимости. Полноценный учет функции видимости весьма сложен [40]. Поэтому популярным подходом является ее аппроксимация частичной суммой ряда Фурье, часто просто константой. Случай аппроксимации константой (называемой коэффициентом затенения) связан с известной технологией генерации мягких теней Ambient Occlusion [31, 42]. Отметим, что приложения технологий, основанных на Ambient Occlusion и сферических гармониках (PRT), использованы в таких фильмах как «Аватар» и отмечены кинематографической премией «Оскар» [15, 33].

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

В данной работе используется идея статьи [7] о применении сферических кубатурных формул небольшого порядка в противовес сферическим коэффициентам Фурье. При этом мы предлагаем новые вычис-

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

Постараемся на простых примерах показать суть нашего метода сферических дизайнов (МСД) и его преимущества перед методом PRT.

В реальном режиме времени необходимо рассчитывать кадры с частотой, скажем, 25 кадров в секунду (25 fps). Для каждого кадра для получения фотореалистичности нужно рассчитать на основе уравнения рендеринга (1)

Bp(v,g)= / L(gx)Vp(x)pp(x,v)dfi(x). Js2

Ясно, что интеграл в нем на практике в любом случае необходимо вычислять приближенно при помощи конечной суммы, например, получаемой при помощи кубатуры большого порядка. Однако количество точек модели р может достигать сотен тысяч, соответственно столько же вычислений необходимо производить на каждый кадр. Очевидно, что выполнять такие вычисления при помощи сумм большого порядка практически невозможно. Поэтому необходимо на основе общепринятой физико-математической модели (1) разработать приближенную вычислительную модель, в которой отраженное освещение Вр с заданной точностью находится из сумм небольшого порядка (Вр). При этом слагаемые этих сумм должны легко определяться при помощи простых формул на основе константных и заранее рассчитанных по параметрам сцены значений. Тогда расчеты по предложенной вычислительной модели можно производить в параллельном режиме сразу для всех вершин на графическом процессоре (GPU). Если суммы совсем небольшие, то этот процесс удачно стыкуется с архитектурой шейдеров. В результате становится реальным производить вычисление порядка 25 х 105 сумм в секунду, что и отвечает интерактивному режиму. При этом тот факт, что в основе лежит физическая модель, делает картинку реалистичной.

Приведем идею метода PRT в нашем изложении. Первое упрощение модели (1) производится из информации о низкочастотности освеще-

пия. Тогда на основе неравенство Коши-Буняковского можно с необходимой точностью заменить в интеграле (1) функцию яркости падающего освежения L частичной суммой ее сферического ряда Фурье L = ]Г?=0 Е|т|<1 LimVim небольшого порядка s, где Lim — коэффициенты Фурье L, yim — ортонормированные сферические гармоники.

Рассмотрим вначале диффузный случай ДФОС Ламберта *рр(х, v) = 4(прх)+. Она не зависит от заранее изменяющегося в интерактивном режиме направления v, а зависит только от нормали пр в точке поверхности модели р. Для статической модели нормаль и функция видимости Vp в каждой точке будут неизменными. Поэтому такой будет функция транспорта Тр(х) = AVp(x)(npx)+. В итоге, применяя равенство Парсеваля, будем приближенно иметь

где Lim(g) — подкрученные с учетом вращения д коэффициенты Фурье Lim. Они вычисляются эффективно на центральном процессоре (CPU) сразу на весь кадр. Коэффициенты транспорта содержат сложно определяемую функцию видимости Vp. Обычно ее значения вычисляются для пучка лучей, выпускаемых из точки р. При этом необходимо решать классическую задачу ЗБ-графики об определении факта пересечения луча с полигональной поверхностью модели. Для ее эффективного решения применяются различные способы, например, kd-и окто-деревья. Также можно использовать предлагаемые в работе методы карт глубины и параллельных вычислений на GPU. Однако в любом случае для большого числа полигонов модели (сотни тысяч) и большого числа лучей (тысячи) эти вычисления производятся пока не в режиме реального времени (offline). Поэтому необходимый набор коэффициентов функции транспорта (Tp)im рассчитываются для каждой точки р в неинтерактивном режиме и сохраняются для последующего использования в интерактивном режиме (online). Заметим, что в этом и состоит суть названия метода PRT — Precomputed Radiance Transfer.

s

(5)

1=0 Iml^Z

15

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

Теперь рассмотрим зеркальный случай ДФОС Фонга pp(x,v) = ша(уПрх). В этом случае соответствующая функция транспорта, как и ее коэффициенты Фурье, будет зависеть от определяемого в интерактивном режиме вектора v. Поэтому заранее их можно рассчитать только для густого в каждой точке р пучка направлений v. Это приводит к очень большим объемам необходимой памяти и, кроме того, падает точность вычислений. Поэтому в качестве промежуточного можно использовать следующее приближение уравнения (1):

B(v,g)= L(gx)Vp(x)cjtr{vnx)dfjL(x), (6)

J s2

где Vp — частичная сумма ряда Фурье функции видимости небольшого порядка s'. Самый простой случай получается при s' = 0, когда Vp « (V^,)oo — аппроксимация константой, называемой коэффициентом затенения или Ambient Occlusion. Используя разложения в ряды Фурье подынтегральных функций в (6), получаем (см. лемму 1.2)

i+i'

С11тЛ>т'и<т1"У1" ,rn+m'{vn), (7)

i,m i',m' г"=|г-г'|

где / ^ s, V ^ s'. Это громоздкое выражение весьма сложно применять в интерактивном режиме прежде всего из-за относительно большого числа не совсем просто вычисляемых слагаемых. Нарушается основное требование интерактивного режима, заключающееся в простоте вычислительной модели.

Теперь посмотрим, что дает предлагаемый нами подход с использованием взвешенных сферических дизайнов с произвольной весовой функцией. В этом случае для величины приближенного отраженного освещения B(v:g) из (7) получаем другое выражение (см. теорему 2.1

и комментарии к ней):

Уп V

Шд Уп^Ша^ ) 1 (8)

и=1

где {хШ(т1/, Л— взвешенный дизайн порядка в + я', построенный по весовой функции В вычислительной модели (8) гораздо меньшее по сравнению с (7) число слагаемых (см. таблицу 1), значения Ь легко вычисляются по дизайну с весом Ь или просто берутся из текстуры. Для вычисления Ур также можно применить дизайны с весами Ур, которые заранее вычисляются и сохраняются (по аналогии с коэффициентами (Ур)гт). Интерактивность заключается в расчете вращений дг,п, что легко реализуется прямо в шейдере.

Теперь более четко изложим суть работы.

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

Для достижения поставленной цели выделяются следующие задачи.

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

2. В противовес известному методу РИТ, основанному на использовании сферических рядов Фурье разрабатывается метод сферических дизайнов (МСД). Для его применения необходимы простые численные методы построения взвешенных сферических дизайнов небольшого порядка с произвольной весовой функцией, задаваемой анали-

17

/ «.,< 1 <)«, ?< А, ' с1 Л^ч / '''к"« 4 '1\< !!

А/ «Л г'/л 'V.1 1

тически или картой окружения. Простота вычислительных формул необходима в том числе для построения дизайнов массированно в параллельном режиме. Также МСД требует эффективные способы вычисления сферических коэффициентов Фурье карты окружения и функции видимости. 3. Полноценная реализация МСД на основе этапов математического и численного моделирования требует алгоритмов вычисления эффективно реализуемых при помощи архитектуры современной вычислительной техники. К этим алгоритмам относятся вычисления взвешенных сферических дизайнов, сферических коэффициентов Фурье и отраженного освещения. В частности, учитывая специфику интерактивных ЗБ-приложений по использованию больших объемов сложно организованных данных и вычислений, разрабатываемые алгоритмы должны допускать параллельную реализацию. На основе предлагаемых алгоритмов с упором на применение свободно распространяемого программного обеспечения требуется выполнить программную реализацию МСД в виде комплекса программ.

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

Основные результаты диссертации являются новыми и состоят в следующем.

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

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

для применения параллельного программирования, что позволяет эффективно выполнять их на современных GPU. 3. Для интерактивного рендеринга при помощи МСД реализован комплекс программ, использующий вычислительные мощности современных GPU, в частности технологии NVIDIA CUDA и OpenCL.

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

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

По теме диссертации опубликованы 9 печатных работ [66-74], в том числе две в рецензируемом научном журнале, входящем в перечень ВАК [66, 67].

Результаты диссертационной работы докладывались на семинарах и конференция, материалы которых опубликованы в [68-74].

Первая глава посвящена моделированию на основе уравнения рендеринга для первичного отраженного освещения.

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

первичного освещения в низкочастотном случае. Кроме того, излагается известный метод предварительного расчета излучательной способности объекта визуализации (ЗБ-модели), который в графике принято называть PRT (Precomputed Radiance Transfer) [37]. Наше изложение PRT оригинально и во многом опирается на теорему 1.1. Так же мы предлагаем способ учета функции видимости при помощи ее частичной суммы ряда Фурье, что эффективно для МСД. В частном случае суммы нулевого порядка получаем учет функции видимости при помощи коэффициентов затенения, близкий к известному методу Ambient Occlusion [31, 42]. Он более подробно рассматривается в главе 2.

Основная проблема заключается в том, чтобы в интерактивном режиме для каждого кадра максимально быстро и качественно вычислить Bp(v,g) (1) во всех вершинах модели. При этом v и д могут быть произвольными.

Для решения проблемы необходимо аппроксимировать интеграл в (1) конечной суммой небольшого порядка, вычисление которой хорошо портируется на архитектуру современных GPU.

Функции L, Vp и рр неизменны, если соответственно освещение, геометрия модели и ее материал также не меняются. Более подробно о свойствах этих функциях и их примерах будет сказано в главе 1 п. 1.1.3.

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

В работе особое внимание уделяется ДФОС Фонга

pP(rv) = oja(rv) = (2а + 2 )(rv)°,

где г = хп = 2(пх)п — х — зеркальный к х относительно нормали п вектор, а > 0 — показатель Фонга. Это вызвано тем, что при использовании ДФОС Фонга возникают сложности в известном методе решения основной проблемы PRT. Для ДФОС Фонга справедливо другое представление, означающее ее зональность: u)a(rv) = ша(vnx).

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

на низких частотах. Освещение называется низкочастотным, если при небольшом s

||L-Z||2 = (||L||2-||Z||¡)1/2^e||L||2,

где е — малое положительное число, L(x) = ^ЧтУ1т{х)

мистичная сумма ряда Фурье порядка s по действительным сферическим гармоника yim. С физической точки зрения норма ЦЬЦ2 является энергией сигнала L, а ЦЬЦз — его энергия на низких частотах.

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

Теорема 1.1. Пусть

B(v,g)= [ L(gx)V(x)p(x,v)dfi(x). (9)

Js2

Тогда для любых v 6 S2 и g € 5(3) справедлива оценка

\B(v,g)-B(vig)\<e\\L\\2\\p\\,

где

1И= sup \\pMh- (10)

ves2

Из приведенной теоремы следует, что для не очень большой нормы (10) точность аппроксимации B(v,g) приближенной величиной B(v, g) будет определяться параметром е. Если он мал при небольшом s, что верно в низкочастотном случае, то аппроксимация будет хорошей.

В п. 1.3.2 описывается метод PRT [36, 44], который в настоящее время является основным для интерактивного рендеринга сцены со сложным освещением. Он создавался для низкочастотного освещения и основан на применении для расчета отраженного освещения Bp(v, g) приближенной функции Bp(v,g), разложенной в ряд Фурье. В п. 1.3.2 мы приводим подробные выкладки, которые отчасти дополняют результаты основополагающей работы [44], где многие формулы не приведены.

Метод PRT основывается на рассмотрении приближенной величины В (9) и подстановке в нее разложения вида

~ S I

L(dX) = Е Е Llm(g)yim(x)- (11)

1=0 m=-l

Коэффициенты вычисляются заранее (в offline-режиме).

Подставим разложение (11) в формулу (9). Имеем

S I

= Е Е Llm(g)Tlm(v), (12)

г=0 т=-1

где через

Tlm{v) = / T(x,v)yim(x)dfl(x)

Js2

обозначены коэффициенты Фурье функции T(x,v) = V(x)p(x,v), называемой в данном контексте транспортом (transfer). Теперь вся сложность перекочевала в вычисление коэффициентов транспорта Tim(v), которые зависят от точки модели р.

При этом ключевым числом является S = (s + I)2 ~ s2, равное числу слагаемых в частичной сумме ряда Фурье порядка s. На практике обычно применяются значения s = 1,..., 5 [36, 37, 44]. Так, в частности, реализовано в DirectX 9 [50]. Например, для s = 4 (основной случай в [44]) имеем S — 25.

В диффузном случае ДФОС Ламберта р(пх) = 4(пх)+ коэффициенты Фурье транспорта не зависят от направления v. Следовательно, их можно рассчитать одним из методов кубатурных формул в каждой вершине р заранее и сохранить для дальнейшего использования в интерактивном режиме (см. п. 1.3.2).

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

Список литературы

1. Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Высшая школа, 1994.

2. Бейтман Г., Эрдей А. Высшие трансцендентные функции. Т. 2. — М.: Наука, 1974.

3. Бондаренко A.B., Горбачев Д.В. Минимальные взвешенные 4-дизайны на сфере S2 // Матем. заметки. 2012. Т. 91, № 5. С. 787-790.

4. Боресков A.B., Харламов A.A. Основы работы с технологией CUDA. — М.: Издательство Московского университета, 2010.

5. Боресков A.B., Харламов A.A. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. — М.: ДМК-Пресс, 2010.

6. Виленкин Н.Я. Специальные функции и теория представления групп. — М.: Мир, 1990.

7. Горбачев Д.В., Иванов В.И., Странковский С.А. Моделирование освещения в интерактивной графике при помощи сферических дизайнов // Изв. ТулГУ. Сер. Естественные науки. 2007. Т. 1. Вып. 1. С. 17-36.

8. Корн Г., Корн Т., Справочник по математике, М., Наука, 1974

9. Лебедев В.И., Лайков Д.Н. Квадратурная формула для сферы 131-го алгебраического порядка точности // Докл. РАН. 1999. Т. 366, № 6. С. 741-745.

10. Мысовских И.П. Интерполяционные кубатурные формулы. М.: Наука, 1981.

11. Попов A.C. Кубатурные формулы на сфере, инвариантные относительно группы вращений икосаэдра // Сиб. журн. вычисл. матем. 2008. Т. 11, № 4. С. 433-440.

12. Сборник задач по математике: Методы оптимизации, Уравнения в частных производных, Интегральные уравнения / Под ред. A.B. Ефимова. — М.: Наука 1990

13. Соболь И.М. Численные методы Монте-Карло. — М.: Наука, 1973

14. Эйнджел Э. Интерактивная компьютерная графика. — М.: Вильяме, 2001

15. Scientific and Technical Achievements to be Honored with Academy Awards, 2010. http ://www.oscars.org/press/pressreleases/2010/20100107.html

16. Akenine-Moiler T., Haines E., Hoffman N. Real-Time Rendering. Third Edition. — Wellesley, 2008.

17. Cohen M.F., Wallace J.R. Radiosity and realistic image synthesis. 3 ed. Boston, Mass.: Academic Press Professional, 1998.

18. Crassin C. GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration of Large And Detailed Scenes // Ph. D. dissertation. Universite de grenoble. 2006. http://maverick.inria.fr/Membres/Cyril.Crassin/thesis/ CCrass inThe s i s_EN_Web.pdf

19. Delsarte P., Goethals J.M., Seidel J.J. Spherical codes and design // Geom. Dedi-cata. 1977. V. 6. P. 363-388.

20. Gassenbauer V., Krivanek J., Bouatouch K., Bouville C., Ribardiere M. Improving Performance and Accuracy of Local PCA // Computer Graphics Forum. 2011. V. 30, № 7. P. 1903-1910.

21. Golub G.H., Welsch J.H. Calculation of Gauss Quadrature Rules // Math. Comp. 1969. V. 23, № 106. P. 221-230.

22. Graf M., Potts D. On the computation of spherical designs by a new optimization approach based on fast spherical Fourier transforms // Numerische Mathematik. 2011. V. 119, № 4. P. 699-724.

23. Graf M., Kunis S., Potts D. On the computation of nonnegative quadrature weights on the sphere // Applied and Computational Harmonic Analysis. 2009. V. 27, № 1. P. 124-132.

24. Green R. Spherical Harmonic Lighting: The Gritty Details, http://www.research, scea.com/gdc2003/spherical-harmonic-lighting.html

25. Hardin R.H., Sloane N.J.A. McLaren's Improved Snub Cube and Other New Spherical Designs in Three Dimensions // Discrete and Computational Geometry. 1996. V. 15. P. 429-441.

26. Hardin R.H., Sloane N.J.A. Spherical designs, a library of putatively optimal spherical t-designs. http://neilsloane.com/sphdesigns, 2002.

27. Kajiya J. T. Rendering equation // In SIGGRAPH 86. 1986. P. 143-150.

28. Kajiya J., Kay T. Rendering fur with three dimensional textures // In SIGGRAPH 89. 1989. P. 271-280.

29. Kendall A. Numneric Integration on the Sphere // J. Austral. Math. Soc. (Series B). 1982. V. 23. P. 332-347.

30. King G. Shadow Mapping Algorithms ftp://download.nvidia.com/developer/ presentations/2004/GPU_Jackpot/Shadow_Mapping.pdf

31. Kontkahen J., Samuli L. Ambient occlusion fields, http://www.tml.tkk.fi/~janne/ aofields/aofields.pdf

32. Marsaglia Q. Choosing a Point from the Surface of a Sphere // Ann. Math. Statist. 1972. V. 43, № 2. P. 645-646.

33. Pantaleoni J., Fascione L., Hill M., Aila T. PantaRay: Fast Ray-Traced Occlusion Caching of Massive Scenes // ACM Trans, on Graph. (SIGGRAPH 10). 2010. V. 29, № 4. P. 37:1-37:10.

34. Pilgrim M. Dive Into Python. 2004.

35. Popov A.S. Cubature formulae for a sphere invariant under cyclic rotation groups // Russian J. Numer. Anal. Math. Modelling. 1994. V. 9, № 6. 535-546.

36. Ramamoorthi R. A signal-processing framework for forward and inverse rendering // Ph. D. dissertation. Stanford University. 2002.

37. Ramamoorthi R. Precomputation-Based Rendering // Foundations and Trends in Computer Graphics and Vision. 2009. V. 3, № 4. P. 281-369. http://www.es. berkeley.edu/~ravir/

38. Ramamoorthi R, Hanrahan P. An Efficient Representation for Irradiance Environment Maps // SIGGRAPH'01. 2001. P. 497-500.

39. Randi J. Rost OpenGL Shading Language, Second Edition. Addison Wesley Professional. 2006.

40. Ren Z., Wang R., Snyder J. Real-time Soft Shadows in Dynamic Scenes using Spherical Harmonic Exponentiation, http://research.microsoft.com/en-us/ people/bainguo/p977-ren.pdf

41. Shreiner D., Sellers G., Kessenich J., Licea-Kane B. OpenGL Programming Guide Eighth Edition. 2013.

42. Shanmugam P., Arikan O. Hardware accelerated ambient occlusion techniques on GPUs. http: //perumaal. googlepages. com/ao. pdf.

43. Sloan P., Hall J., Hart J., Snyder J. Clustered principal components for precom-puted radiance transfer // ACM Transactions on Graphics, Proceedings of SIGGRAPH 03. 2002. V. 22, № 3. P. 382-391.

44. Sloan P., Kautz J., Snyder J. Precomputed Radiance Transfer for Real-Time Rendering in Dynamic, Low-Frequency Lighting Environments, http://web4.cs.ucl. ac.uk/staff/j.kautz/publications/prtSIG02.pdf

f

45. Stroud A. Approximate Calculation of Multiple Integrals. — N.J.: Prentice Hall, 1971.

46. Tsuchiyama R., Nakamura Т., Iizuka Т., Akihiro A., Son J., Miki S. The OpenCL Programming Book. Fixstars. 2012.

47. Wald I., Havran V. On building fast kd-Trees for Ray Tracing, and on doing that in 0(N log N) http://dcgi.felk.cvut.cz/home/havran/ARTICLES/ingo06rtKdtree. pdf

48. Wu Z., Zhao F., Liu X. SAH KD-Tree Construction on GPU http://kusma. demoscene.no/dump/HPG-ll/content/071-wu.pdf

49. Liu X., Sloan P., Shum H., Shy der J. All-Frequency Precomputed Radiance Transfer for Glossy Objects // Eurographics Symposium on Rendering. 2004.

50. Precomputed Radiance Transfer (Direct3D 9) (Windows) http://msdn.microsoft. com/en-us/library/windows/desktop/bbl47287(v=vs.85).aspx

51. http://www.python.org/getit/

52. http://www.scipy.org/install.html

53. http://mathema.tician.de/software/pyopencl

54. http://mathema.tician.de/software/pycuda

55. http://www.pythonware.com/products/pil/

56. http://www.makotemplates.org/

57. http://www.panda3d.org/download.php?runtime

58. http://wiiw.blender.org/

59. http://ru.wikipedia.org/wiki/Z-буферизация

60. http://http.developer.nvidia.com/GPUGems/gpugems_chl7.html

61. http://graphics.Stanford.edu/data/3Dscanrep/

62. http://www.humus.name/index.php?page=Textures&&start=0

63. http://www.mathworks.com/matlabcentral/fileexchange/ 27097-getlebedevsphere

64. http://www.panda3d.org/manual/index.php/Cube_Maps

65. http://www-user.tu-Chemnitz.de/~potts/workgroup/graef/quadrature/

Публикации автора по теме диссертации в ведущих рецензируемых научных жерналах:

66. Свистунов С. С. Интерактивный рендеринг при помощи сферических дизайнов (SDPRT) для низкочастотного окружающего освещения и BRDF Фонга // Изв. ТулГУ. Естественные науки. 2011. Вып. 1. С. 188-199.

67. Свистунов С. С. Применение GPU для вычисления коэффициентов затенения в задаче моделирования интерактивного освещения // Изв. ТулГУ. Естественные науки. 2012. Вып. 3. С. 142-152.

В трудах и тезисах конференций:

68. Свистунов С. С. Метод SDPRT интерактивного рендеринга для низкочастотного окружающего освещения // Материалы международной научной конференции «Современные проблемы математики, механики, информатики». — Тула: Изд-во ТулГУ, 2010. С. 264-266.

69. Свистунов С.С., Горбачев Д.В. Расчет функции видимости с помощью NVIDIA CUDA // Материалы международной научной конференции «Современные проблемы математики, механики, информатики». — Тула: Изд-во ТулГУ, 2011. С. 259-261.

70. Свистунов С. С. Расчет функции видимости на GPU // Материалы международной научной конференции «Современные проблемы математики, механики, информатики». — Тула: Изд-во ТулГУ, 2012. С. 264-266.

71. Свистунов С. С. Интерактивный рендеринг на GPU: вычисление функции видимости // Материалы XII Всероссийской конференции / Под ред. В.П. Гергеля. — Нижний Новгород: Изд-во Нижегородского госуниверситета, 2012. С. 360-364.

72. Свистунов С. С. Интерактивный рендеринг при помощи сферических дизайнов // XX Международная конференция «Ломоносов-2013». — М.: МГУ, 2013, С. 117-119.

73. Свистунов С. С. Интерактивный рендеринг при помощи сферических дизайнов для низкочастотного окружающего освещения // ГрафиКон'2013: 23-я Международная конференция по компьютерной графике и зрению. Труды конференции. — Владивосток, Институт автоматики и процессов управления ДВО РАН, 2013. С. 203-206.

74. Свистунов С. С. Аппроксимация уравнение рендеринга для первичного освещения при помощи сферических дизайнов // Материалы международной научной конференции «Современные проблемы математики, механики, информатики». — Тула: Изд-во ТулГУ, 2013. С. 573-574.