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

На правах рукописи

БОГОЛЕПОВ Денис Константинович

Методы глобального освещения для интерактивного синтеза изображений сложных сцен на графических процессорах

Специальность: 05.13.17 - «Теоретические основы информатики» по техническим наукам

АВТОРЕФЕРАТ

диссертации на соискание ученой степени 1п «. рп ?П1

| 0 М11; -и 1

кандидата технических наук

00505741о

Нижний Новгород 2013 г.

005057418

Работа выполнена на кафедре математического обеспечения ЭВМ в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Нижегородский государственный университет им. Н.И.Лобачевского (г. Нижний Новгород)

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор технических наук, доцент, Турлапов Вадим Евгеньевич

Утробин Владимир Александрович, доктор технических наук, профессор, НГТУ им. P.E. Алексеева, кафедра «Вычислительные системы и технологии», профессор

Волобой Алексей Геннадьевич, кандидат физико-математических наук, доцент, Институт прикладной математики им. М.В. Келдыша РАН, ст. научный сотрудник

Факультет Вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, г. Москва

Защита диссертации состоится «25» апреля 2013 г. в 13 часов на заседании диссертационного совета Д.212.165.05 в Нижегородском государственном техническом университете им. Р.Е.Алексеева по адресу: 603000, г. Нижний Новгород, ул. Минина, 24, ауд. 1258.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. Р.Е.Алексеева.

Автореферат разослан марта 2013 г.

Ученый секретарь Диссертационного совета

A.C. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Традиционный способ визуализации динамических 3D сцен в реальном времени основан на растеризации, которая аппаратно ускоряется графическими процессорами и доступна через интерфейсы (API) OpenGL и Direct3D. Данный подход не позволяет обрабатывать вторичное освещение и физически достоверные модели материалов и источников света. К настоящему времени предложены разные подходы имитации тех или иных эффектов глобального освещения, среди которых следует отметить методы внешней преграды (ambient occlusion), отражающих теневых карт (reflective shadow maps), мгновенной излучательности (instant radiosity), а также методы фотонных карт в пространстве изображения (image space photon mapping). Перечисленные подходы позволяют добиться высокой производительности за счет аппаратной растеризации, однако воспроизводят только часть необходимых эффектов. Интерфейсы 3D графики не поддерживают трассировку лучей, на основе которой реализуются многие методы глобального освещения.

В последние годы появились и активно развиваются универсальные инструменты программирования (NVIDIA CUDA, OpenCL, Compute Shaders), которые позволяют задействовать вычислительные возможности графических ускорителей для широкого класса задач. Современный графический процессор NVIDIA GeForce GTX 680 имеет пиковую производительность свыше 3 Терафлопс, что позволяет говорить об эпохе персональных супервычислений. Основным препятствием на пути к использованию таких ресурсов является высокая сложность разработки для массивно-параллельных графических архитектур, связанная с необходимостью глубокой переработки традиционных алгоритмов.

Одна из актуальных задач современной компьютерной графики - портирование методов глобального освещения на графические процессоры с целью визуализации сложных 3D сцен в интерактивном режиме. Данная область активно исследуется как в России, так и за ее пределами. Подтверждением этому является значительное число публикаций, среди которых следует отметить работы I.Wald, J. Gunther, S. Popov, Н,-Р. Seidel, S. Boulos, T. Ize, W. Hunt, C. Benthin, M. Wagner, V. Havran, C. Wächter, A. Keller, C. Lauterbach, T. Purcell, I. Buck, T. Foley, J. Sugerman, D. Horn, N. Thrane, L. Simonsen, W. Mark, M. Houston, P. Hanrahan, H. Jensen, S. Parker, P. Shirley, P. Slusallek, S. Woop, J. Schmittler, D. Hall, T. Aila, S. Laine, К. Zhou, R.Wang, а также Ю.

Баяковского, В. Галактионова, А. Волобоя, Б. Барладяна, JI. Шапиро, К. Гаранжи, К. Вострякова, А. Игнатенко, А. Адинца, В. Фролова и др. Публикации последних лет показывают устойчивую тенденцию к возрастанию роли графического процессора в расчете глобального освещения. Вместе с тем, остаются актуальными как достижение интерактивности в синтезе изображений 3D сцен (с учетом глобального освещения), так и разработка системного решения для графических процессоров. Поиску данного решения и посвящено настоящее исследование.

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

Поставленная цель требует решения следующих задач:

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

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

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

• Разработать программный комплекс, реализующий предложенные решения с использованием инструментов параллельного программирования графических архитектур (NVIDIA CUDA, OpenCL, OpenGL).

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

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

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

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

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

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

2) Структура хранения и обработки 3D сцен, отличающаяся наличием двухуровне-невого представления модели: на верхнем (прикладном) уровне функционирует как граф сцены, а на нижнем обеспечивает эффективную сериализацию данных для потоковой обработки на графическом процессоре.

3) Программный конвейер трассировки лучей, который реализует типовые блоки (операции) лучевых алгоритмов визуализации и отличается универсальностью на классе методов глобального освещения и ориентированностью на массивно-параллельные вычислительные архитектуры. На базе блоков данного конвейера построены методы: испускание лучей (ray casting), трассировка лучей Уитгеда (Whitted ray tracing), стохастическая трассировка путей в прямом и обратном направлении (path tracing и light tracing), двунаправленная трассировка путей (bidirectional path tracing), а также предлагаемый в настоящем исследовании ее «усеченный» вариант.

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

5) Метод «усеченной» двунаправленной трассировки путей, который строится на типовых операциях конвейера трассировки лучей и отличается фиксированным объемом потребляемой памяти при обработке путей любой длины, эффективной реализацией многократной выборки по значимости, полным исключением фазы соединения путей.

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

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

• Программная библиотека графа сцены, которая отличается от аналогов (таких как OpenSceneGraph и OpenSG) поддержкой эффективной сериализации данных и гибридных сцен (сочетающих полигональные и нетесселированные объекты).

• Встраиваемый модуль визуализации («плагин») для системы 3D моделирования Blender, который базируется на разработанной библиотеке расчета глобального освещения (аналогичные модули могут быть разработаны для систем Autodesk 3D Studio Мах и Maya, Махоп Cinema 4D, DAZ Studio, Smith Micro Poser).

• Автономная система синтеза изображений методами глобального освещения в интерактивном режиме с поддержкой основных (более 20) форматов хранения геометрии и описания материалов. Система может служить методическим пособием к вузовским курсам по компьютерной графике и физической оптике.

Таким образом, получен ряд практических результатов, востребованных в различных областях компьютерной графики. Программная библиотека лучевых методов расчета изображений внедрена в комплекс научной визуализации ScView РФЯЦ-ВНИИЭФ. Лабораторные работы по лучевым методам, разработанные в процессе подготовки диссертации, внедрены в учебный процесс ННГУ.

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

Апробация работы. Основные результаты доложены и обсуждены на: международных конференциях по компьютерной графике и зрению GraphiCon (Москва, 2009, 2011, 2012; Санкт-Петербург, 2010); международной научной конференции «Параллельные Вычислительные Технологии» (Нижний Новгород, 2009); всероссийской

конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2011); семинарах кафедры МО ЭВМ факультета ВМК ННГУ. Лабораторные комплексы по трассировке лучей, глобальному освещению и вычислениям на GPU внедрены в курсы «Компьютерная графика» и «Современная компьютерная графика» на факультете ВМК ННГУ; использованы в образовательных проектах Intel Winter School 2008 и Intel Studio Graphics 2008; цикле Интернет-лекций и мастер-классов по компьютерной графике по гранту ФЦП СПбУ ИТМО (20 часов, ноябрь 2009); всероссийской научной школе для молодежи «Компьютерное зрение, 3D моделирование и компьютерная графика» 2010 (госконтракт №02.741.12.2170). Работа прошла конкурсный отбор для участия в программе У.М.Н.И.К (госконтракт №8753р/13130).

Публикации. Основные результаты исследования опубликованы в 13 работах, из них 4 - публикации в изданиях, рекомендованных ВАК.

Основные положения, выносимые на защиту:

1) Эффективная ускоряющая структура на базе иерархии объемов, отличающаяся наличием высокопроизводительного алгоритма ее параллельного построения на графическом процессоре.

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

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

4) Высокоуровневая библиотека для интерактивного синтеза изображений 3D сцен методами глобального освещения на графических процессорах и программный комплекс, реализующий выносимые на защиту положения и обеспечивающий производительность на уровне (а при увеличении глубины трассировки и до 2-х раз выше) библиотеки трассировки лучей NVIDIA OptiX.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 167 наименований. Общий объем - 185 стр.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе построена система моделей, которые лежат в основе физически достоверной визуализации. В разделе 2.1 взаимосвязано описаны основные величины для моделирования энергетических характеристик оптического излучения: лучистый поток (Ф), сила излучения (/), облученность (£), энергетическая светимость (М), энергетическая яркость (X) и ее свойства. В разделе 2.2 рассмотрено моделирование рассеяния света на поверхностях: двулучевые функции распределения отражения и пропускания В1ШР/ВТОР (ВхЭР) и обобщенная двулучевая функция распределения рассеяния ВББР. В частности, ВЮЭР в заданной точке х определяется как отношение приращения яркости, отраженной вдоль направления 0, к приращению облученности, падающей с направления Ч1:

сгЦх-*0) сгЦх-0)

^ (у Ш 0") = -Ь-! = -Ъ-;--(1)

,тК ' ' йЕ(х «- Ф) 1(х <- 40 со5(ЛГх, У) с1ш,¥

В разделе 2.3 исследованы специализированные формы уравнения визуализации, подлежащие реализации в методах глобального освещения.

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

Цх -> 0) = ¿е(х 0) + |/г(х/Н 0)Цх У) собСЛ^ЧО (2)

И

В плогцаднои форме (для специализации интегрирования по поверхностям сцены) интеграл по полусфере Я заменяется интегралом по поверхностям Л, видимым из точки х:

Цх -> 0) = Ье(х -> 0) + I /г(х, Ч< - 0Жу -Ч0С(х « у№у (3)

А

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

¿(х' -> х) = 1е(х' х) + | /г(х" х' х)/,(х" х')С(х' о х")сМх

(4)

А

В разделе 2.4 исследованы формы уравнения измерения, определяющего задачу синтеза изображения как проблему измерения яркости пикселя. Каждый пиксель / картинной плоскости моделируется в виде датчика площади I, суммарный отклик Му которого дает меру падающей яркости согласно заданной функции отклика IV,-:

М] = 11 \У](х Ч>Жх ЧОСОБ (Мх, ЧО^ц, сМх (5)

і н

И/ = 11 -* Х0)І(Х! -> Хо)С(Хі <-> х0)сІАХІ с1АХо = | /}(х0(6)

і н

м, С С

/ А ІХА

В разделе 2.5 дано моделирование пространства путей переноса излучения для решения уравнения измерения методом Монте-Карло, которое позволяет представить суммарную отраженную яркость как совокупность вкладов путей любой длины:

¿(хг -» Х0) = ¿е(Х! -> Х0) + ^ | /(Х0Х! ...Хк)с1АХ2

_ .......а (7)

к=2 мк-1

Символом I здесь обозначена функция переноса излучения, I: М1+1 -» К, которая определяется как

(8)

1(Х0Х1 ...Хк) = ]~[/г(х,+1 -» X¡ Х;_!)С(Х( «-» Хт) Ц(хк

(=1

Путь переноса излучения Хк определяется произвольной последовательностью точек х0хг ...хк е / х Ак, первая вершина которой лежит на картинной плоскости /, а остальные - на поверхностях сцены А. Множество всех путей длины к обозначается через С1к = I х Лк, а пространство всех возможных путей - через П = и^ IV Что позволило записать уравнение измерения в удобном для вычислений виде:

Щ = | /ДХ)сгп(Х) (9)

п

сШ(х0 ...хк) = Л4Хо х йАХ1 х ... х сМХ|1 Здесь /у: П -» Е - функция измерения, которая позволяет выразить суммарный отклик датчика ] через интеграл по пространству путей переноса излучения. /;(х0 ...хк) = ИДх! -» х0)

ГТ ГТ (10)

х| |С(х,«х,+1)| |/г(х;+1 -»X, ->хк_г)

¡=0 ¡=1

Реализованные в рамках настоящего исследования алгоритмы глобального освещения строят приближенное решение уравнения измерения (9) методом Монте-Карло.

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

9

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

й^х, - х0) = ЩЪ х0)С(х0 « Х1) МХо1а(Х1) (1 •)

Все методы генерации случайных путей, которые применяются в настоящей работе, являются комбинацией трех стратегий:

• Из вершины Х(_! в произвольном направлении трассируется луч, ближайшая точка пересечения которого определяет вершину х, («прямая»),

• Из вершины х(+1 в произвольном направлении трассируется луч, ближайшая точка пересечения которого определяет вершину х( («обратная»).

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

В разделе 2.7 дана алгоритмизация метода стохастической трассировки путей на основе разработанной системы моделей. В данном методе пути строятся с помощью «прямой» стратегии, при этом начальная вершина выбирается на диафрагме камеры. Путь х0 ...хк наращивается за счет поэтапного присоединения вершин и завершается в произвольной точке методом «русской рулетки». Каждая вершина хг соединяется теневым лучом со случайной точкой ъ на источнике света, за счет чего формируется явный путь переноса излучения х0 ...х;г. Если в процессе расширения пути очередная вершина хк была выбрана на источнике света, то промежуточная последовательность вершин х0 ...хк называется неявным путем переноса излучения. Вклад неявного пути Х0 ...хк в Монте-Карло оценку уравнения измерения записывается в виде:

Р,(х0...х*) Л1 07 И р^(х,-»х,+1) Вклад явных путей х0 ...хк записывается аналогично:

/ДХо-ХЕ) ГТ/г^-»^-»^)

к-2

-т-^СХ! ->Х0)П^ , -

р£(х0...хк) ри1(х, ->хг+1)

Гг(хк -> -> Хк.2)С(Хк <-> Х^) ,

х Ш) 1е(-Хк Хк-1}

(13)

При вычислении вклада пути учитывается относительная «значимость» применяемой стратегии. Данная задача решается разработанным блоком многократной выборки по значимости, который вычисляет весовые функции вкладов согласно энергетической эвристике (/? = 2):

гие(х„ ...кк) =

ре(х0 ...Х(£)"

ре(х0 ...хк)1> +рг(Хо ■■■ХкУ РмСхк)"

Рм&кУ + хк)С(хк_1 <-> хк)]"

Ш((х0 ...хк) =

р,(х0...хку

ре(х0 ...Хк)'1 +Р((х0 ...х^

(15)

Рм(Хк)" + хк)С(хк_! « хк)]"

:-1

В разделе 2.8 строится эффективная алгоритмизация нового метода «усеченной» двунаправленного трассировки, который оптимизирован для массивно-параллельных графических процессоров. Традиционная двунаправленная трассировка (независимо предложена Э. Лафорчуном и Э. Вичем) является слишком ресурсоемкой техникой для графического процессора, поскольку требует хранения всех вершин «светового» и «видового» пути, что в ~20 раз превосходит затраты памяти для однонаправленной трассировки путей.

«Усеченный» алгоритм формирует изображение за два прохода. На первом этапе выполняется обратная трассировка от объектива виртуальной камеры, в ходе которой строятся явные и неявные пути. На втором этапе выполняется прямая трассировка от источника света, в процессе которой вершины явно соединяются с камерой. Метод можно рассматривать как частный случай двунаправленной трассировки путей, при котором один из соединяемых путей содержит не более одной вершины (5 < 1 или t < 1). Преимущества подхода:

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

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

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

• Возможность простого распараллеливания: «прямой» и «обратный» проходы можно выполнять на разных графических процессорах (или других вычислительных устройствах) без какого-либо взаимодействия в ходе вычислений (для получения результата изображения необходимо сложить).

В методе «усеченной» двунаправленной трассировки каждый путь Хк = х0 ...хк может быть построен тремя способами: как явный путь у0 ... у)с_12 или неявный путь Уо •■■ Ук в ходе обратной трассировки или как световой путь г0 ... 1к_1у в ходе прямой

трассировки. Вклады неявного и явного пути определяются по формулам (12) и (13). Вклад светового пути можно выразить следующим образом:

= щъ - Х0) 'У • (х° - р^)

р^х0 ...хк; (ЛГ0 • (х! - х0))

к-1

х /г(х2 -»хг -»х0)

Уг(Х{+1 -* X; -> Х^) Ье(хк -> 1=2 Р^Схг-'Хг.!) рА(хк)рш1.(хк

(16)

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

-1 р,(х0...х,У | р^Хр ...х^ (17)

шЕ(х0...хк) рЕ(х0...хк)Р р£(х 0...хк)Р Поскольку явный и неявный пути различаются лишь способом генерации последней вершины хк, отношение их плотностей вероятности определяется по формуле:

р,(х0 ...Хк) _ Рмх(Хе_! -> Х^)С(Х)1.1 <->Хк) (18)

рЕ(х0 ...Хк) ~ Рл(Х(с)

Для светового и явного пути отношение плотностей вероятности можно выразить следующим образом:

к—2

рь(х0 ...Хк) _ С(хк <-> Хк_1)ршл.(Хк -* Х)1.1)рмх(Х)г.1 -> Хк_2) Т~ГРМ±(Х; ~> Х;^) (19) рЕ(Х0 ...Хк) ~ ру,(х1)рш±(х1 -> Х2) 1=1ршх(х( -> Х(+1)

На основе (19) построена эффективная итерационная процедура вычисления за счет декомпозиции данного выражения на отдельные компоненты: РоЕ = 1 /РдОч)

Р? = 1 /рш1(Х! - Х2)

ре = рур^с*. (20)

к—2

п^_-

I 1рш±(х( ->Х(+1)

(=2 '

Рк-1 = Рш^к-г хк_2) Л? = Р<^(х* -» Хк_!)С(хк <-> В формулах (20) величину Р1 можно вычислить сразу после генерации (1 4- 1)-ой вершины пути. С данными обозначениями отношение (19) принимает вид:

р,(х„ ...хк) =ГТгЕ (21)

рЕ(х0 ...хк) 1=1 1

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

Аналогичным образом определяется обратный вес неявного пути переноса света (для сокращения записи опущены аргументы функций):

В итоге, вычисление веса неявного пути также сводится к формуле (21). Аналогично определяется обратный вес светового пути с той лишь разницей, что величины Р{" — 1 /Pf накапливаются в обратном порядке (от хк до хх).

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

В разделе 3.1 описано построение на GPU эффективной ускоряющей структуры для лучевых методов синтеза изображений (SAH BVH). Предлагается набор методик, которые позволили получить 5-кратный прирост производительности по сравнению с лучшей известной реализацией (на момент публикации результатов). Для построения иерархии объемов применяется ячеечная (binned) техника. Последовательность операций делится на отдельные задания (по разбиению узлов), исполнение которых реализуется через концепцию очереди. Общая схема алгоритма:

• На каждом шаге построения иерархии выполняются все доступные задания независимо от их размера. В итоге достигнута полная утилизация ресурсов GPU и снижены накладные расходы, вызванные передачей заданий с CPU.

• Для обработки узлов с большим числом примитивов (N > 32К) применяется несколько групп работ (терминология OpenCL) на узел (Л//512). В сочетании с предыдущей оптимизацией данный подход позволил обеспечить оптимальное использование ресурсов.

• Построение дерева разбито на три этапа: обработка больших узлов (более 32К примитивов), средних узлов (от 256 до 32К примитивов) и малых узлов (менее 256 примитивов). Это позволило применить для каждого уровня дерева оптимизированные модификации алгоритма.

В разделе 3.2 предложен метод представления и сериализации иерархической объектно-ориентированной модели сложной сцены. В рамках принятого подхода сцена представляется графом - ориентированным деревом. Данное представление не допускает эффективного отображения на графическую архитектуру, которая ориентирована на потоковую обработку массивов данных. Предложен универсальный механизм для хранения и обработки моделей, который на пользовательском («верхнем») уровне имеет функционал графа сцены, а на нижнем («внутреннем») уровне обеспечивает эффективную сериализацию данных в массивы. Для перехода от графа сцены к набору массивов разработан эффективный механизм сериализации (популярные системы графов сцены - OpenSG и OpenSceneGraph - не обеспечивают эффективного отображения иерархии в массивы).

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

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

Т~| Attribut? Н»-

--] Kernel \oL

TronsformAttributs

VisibiiiiyAftrbute

Property

QuacncSurfsoe

Geometry

=r

Moteriol

РзМеСшпега | | AperiurgCatrera |

[ light :

ûânàà

Hs^ghtFietd

Рис. 1. Диаграмма основных классов графа сцены

Для каждого класса сериализуемых объектов (на схеме отнаследованы от базового типа Stashable) определяется специальное хранилище, которое содержит данные всех экземпляров соответствующего класса согласно принципу SoA (Structure of Arrays). Реализация хранилищ основана на контейнерах стандартной библиотеки шаблонов STL. Перед обработкой очередного кадра выполняется обход графа сцены, в процессе которого данные обновленных узлов записываются в соответствующие хранилища (список ассоциированных хранилищ определяется в классе Stashable).

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

Блок генерации световых лучей. Выполняет генерацию («первичных») исходящих лучей из источника света. Способ выборки лучей зависит от модели источника.

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

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

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

Блок расчета пересечений. Выполняет поиск точек пересечения с ближайшими объектами сцены. Для обработки полигональных сеток применяет разработанный вариант SAH BVH. Возможность обработки неполигональной геометрии показана на примере поверхностей второго порядка и 4D фрактальных множеств Джулиа.

Блок расчета освещенности. Выполняет вычисление вклада пути в оценку яркости пикселя. Использует модели материалов заданные функциями BSDF.

Блок генерации вторичных лучей. Выполняет генерацию вторичных лучей, за счет которых происходит расширение пути. Способ выборки вторичных лучей зависит от модели материала, построенной на комбинации «атомарных» для метода Монте-Карло (событийно-атомарных) материалов.

Генерация световых лучей

Генерация первичных лучей

г

Буфер световых лучей

N- І

Ф Importance

Sampling

г

Ускоряющая структура

\ Обработчики источников света

Поиск ближайшей точки пересечения

©

Генерация »{ теневых лучей

Поиск любой точки пересечения

ШЭ Расчет освещенности

Буфер

ВИДОВЫХ лучей

Буфер теневых лучей

Генерация вторичных лучей

Ф

Обработчики материалов

Рис. 2. Укрупненная схема конвейера трассировки лучей

На стороне графического процессора блоки конвейера реализуются с помощью технологии NVIDIA CUDA (возможно портирование на OpenCL).

Исследовано построение расширяемой подсистемы источников света. Введена удобная для реализации классификация источников:

• Локальные. К данному классу относятся источники, расположение и размеры которых определяются конечными координатами. Класс делится на точечные и протяженные (площадные) источники света.

• Бесконечно удаленные. К данному классу относятся источники, расположенные на бесконечном расстоянии от сцены. Класс делится на направленные и площадные (такие как небесная сфера) источники света.

Рис. 3. Примеры работы источников света (направленный, площадной, карта окружения)

Система поддерживает изотропные точечные источники, направленные источники, непрерывные диффузные источники, верхний свет и карты окружения, которые могут загружаться из различных ЬШК1 форматов и эффективно обрабатываются на основе выборки по значимости (рис. 3).

Исследовано построение расширяемой системы материалов, в основе которой -разделение типов рассеяния света на диффузное, размыто-зеркальное и зеркальное.

Рис. 4. Результаты синтеза изображений для некоторых «атомарных» ВІШБ

Для описания конкретных типов рассеяния применяются «атомарные» (неделимые), с точки зрения событий метода Монте-Карло, ВИ№ и ВТОР. Реализованы диффузные модели Ламберта и Орена-Найара, размыто-зеркальные модели Уорда и Блинна, а также модели идеального зеркального отражения и преломления (рис. 4). Комбиниро-

16

ванные материалы (рис. 5) задаются суммой нескольких типов отражения или пропускания света и определяются BSDF следующего вида:

N

fs(x, Ч> -» 0) = ^ аМх, f-.8) (23)

¡=i

Коэффициенты tTj являются векторными и задаются независимо для каждой полосы спектра (в текущей версии применяется трехканальный цвет RGB). В общем случае для каждой BxDF компоненты наряду с коэффициентом аг определяется текстурная карта Г( и коэффициент Френеля F(. В частности, в рамках данного подхода материал стекла моделируется как комбинация BxDF идеального отражения и преломления с единичными весовыми коэффициентами (рис. 5):

Здесь Re и Тв - направления идеального отражения и преломления для исходящего направления 0.

Рис. 5. Результаты синтеза изображений для некоторых составных ВЗОР

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

реализованных алгоритмов визуализации подтверждена посредством моделирования различных аспектов переноса излучения и сопоставления результатов с эталонными изображениями. Сравнение быстродействия с NVIDIA OptiX на ряде сцен показало превосходство разработанного комплекса, линейно возрастающее с ростом глубины трассировки. Подробно исследован новый алгоритм «усеченной» двунаправленной трассировки: замерена скорость сходимости в различных условиях освещения и дано сравнение со стандартной трассировкой путей, показывающее преимущество нового алгоритма. Основная идея алгоритма показана на рис. 6: окончательное изображение формируется из «значимых» фрагментов, полученных в процессе прямой и обратной трассировки путей.

Рис. 6. Пример работы «усеченного» двунаправленного алгоритма: вклад обратной (слева), прямой (центр) трассировки путей и результат (справа)

В заключении сформулированы основные результаты диссертационной работы. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1) Эффективная для статических и динамических сцен ускоряющая структура, на базе иерархии ограничивающих объемов, отличающаяся высокопроизводительным построением, реализованным полностью на графическом процессоре.

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

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

4) Программный конвейер трассировки лучей, который реализует типовые блоки (операции) лучевых алгоритмов синтеза изображений и отличается универсальностью на классе методов глобального освещения и ориентированностью на массивно-параллельные вычислительные архитектуры. На базе блоков данного конвейера построены методы: испускание лучей (ray casting), трассировка лучей Уитгеда (Whitted ray tracing), стохастическая трассировка путей в прямом и обратном направлении (path tracing и light tracing), двунаправленная трассировка путей (bidirectional path tracing), а также предлагаемый в настоящем исследовании ее «усеченный» вариант.

5) Метод «усеченной» двунаправленной трассировки путей, который строится на типовых операциях конвейера трассировки лучей и отличается фиксированным объемом потребляемой памяти при обработке путей любой длины, эффективной реализацией многократной выборки по значимости, полным исключением фазы соединения путей.

6) Высокоуровневая библиотека для интерактивного синтеза изображений 3D сцен методами глобального освещения на графических процессорах и программный комплекс, реализующий выносимые на защиту положения и обеспечивающий производительность на уровне (а при увеличении глубины трассировки и до 2-х раз выше) библиотеки трассировки лучей NVIDIA OptiX.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в научных журналах, рекомендованных ВАК.

1. Боголепов Д.К., Сопин Д.С., Турлапов В.Е. Упрощенный метод фотонных карт для визуализации каустик в реальном времени // Программирование. - 2011. - № 5. - С. 3-12. - ISSN 0132-3474.

2. Боголепов Д.К., Турлапов В.Е. Моделирование каустик в реальном времени на основе комбинированных возможностей OpenCL и шейдеров // Вестник Нижегородского университета им. Н.И. Лобачевского. - 2011. - Вып. 3(2). - С. 180-186.

3. Боголепов Д.К., Сопин Д.П., Ульянов Д.Я., Турлапов В.Е. Построение SAH BVH деревьев для трассировки лучей с использованием графических процессоров // Научно-технический журнал «Приборостроение». - 2011. - Вып. 10. - С. 92-94.

4. Боголепов Д.К., Сопин Д.П., Ульянов Д.Я., Турлапов В.Е. Интерактивное моделирование глобального освещения на GPU для анимированных гетерогенных сцен // Вестник Нижегородского университета им. Н.И.Лобачевского. - 2012. -Вып. 5(2).-С. 251-259.

Остальные публикации по теме диссертационной работы.

5. Боголепов Д.К., Турлапов В.Е. Вычисления общего назначения на графических процессорах с использованием шейдерных языков // Труды международной науч-

19

f

i

ной конференции «Параллельные вычислительные технологии». - Челябинск: Изд-во ЮУрГУ, 2009. - С. 40-47.

6. Боголепов Д., Трушанин В., Турлапов В. Интерактивная трассировка лучей на графическом процессоре // Труды 19-ой междунар. конференции по компьютерной графике и зрению (GraphiCon'2009). - M.: Изд-во МГУ, 2009. - С. 263-267.

7. Боголепов Д., Удалова Т., Турлапов В. Моделирование каустик на графическом процессоре // Труды 19-ой международной конференции по компьютерной графике и зрению (GraphiCon'2009). - M.: Изд-во МГУ, 2009. - С. 392-394.

8. Боголепов Д.К., Блохин О.Д., Захаров М.М., Сопин Д.П. GLSL и OpenCL - сравнительный опыт вычислений // Тезисы докладов научно-практической конференции «Вычисления с использованием графических процессоров в молекулярной биологии и биоинформатике». - М.: Изд-во МГУ, 2010. - С. 44-46.

9. Боголепов Д., Сопин Д., Турлапов В. Моделирование каустик в реальном времени // Труды 20-ой международной конференции по компьютерной графике и зрению (GraphiCon'2010). - СПб: Изд-во СПбГУ ИТМО, 2010. - С. 253-256.

10. Sopin D., Bogolepov D., Ulyanov D. Real-time SAH BVH construction for ray tracing dynamic scenes // Proc. of the 21th International Conference on Computer Graphics and Vision «GraphiCon'2011». - Moscow, 2011. - Pp. 74-78.

11. Сопин Д.П., Боголепов Д.К., Ульянов Д.Я., Турлапов В.Е. Построение SAH BVH деревьев для трассировки лучей на GPU в реальном времени // Материалы XI Всеросс. конференции «Высокопроизводительные параллельные вычисления на кластерных системах». - Нижний Новгород: Изд-во ННГУ, 2011, - С. 298-303.

12. Боголепов Д., Бугаев И., Сопин Д., Ульянов Д., Турлапов В. Высококачественная объемная визуализации в реальном времени // Труды 22-ой международной конференции по компьютерной графике и зрению (GraphiCon'2012). - M.: МАКС Пресс, 2012. - С. 169-174.

13. Боголепов Д., Сопин Д., Ульянов Д., Турлапов В. Система интерактивного расчета глобального освещения для гибридных сцен // Труды 22-ой международной конференции по компьютерной графике и зрению (GraphiCon'2012). - M.: МАКС Пресс, 2012. - С. 227-233.

Личный вклад автора. Степень личного участия соискателя в публикациях (№ -печ. листов): 1 - 0.6 пл.; 2 - 0.6; 3 - 0.17; 4-0.51; 5 - 0.7; 6 - 0.35; 7 - 0.23; 8 - 0.35; 9 - 0.3; 10 - 0.3; 11 - 0.36; 12 - 0.36; 13 - 0.4. Все научные результаты, выносимые на защиту, получены Д. К. Боголеповым лично. В коллективных работах выполнял роль руководителя группы, прототипирование всех алгоритмов и системных решений.

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

Подписано в печать 20.03.2013. Формат 60 х 84 '/16. Бумага офсетная. _Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 234.

Нижегородский государственный технический университет им. P.E. Алексеева.

Типография НГТУ. 603950, ГСП-41, г. Нижний Новгород, ул. Минина, 24.

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Нижегородский государственный университет им. Н.И. Лобачевс'коп

I I! III Ш|Ч >

' (вд—"

I.1!

1Р1

На правах рукок

БОГОЛЕПОВ Денис Константинович

I

Методы глобального освещения для интерактивного синтеза

ч

изображений сложных сцен на графических процессе

Шифр и наименование специальности 05.13.17 - «Теоретические основы информатики» (технические науки)

ч !

Диссертация на соискание ученой степени кандидата технических наук

ч!

7]Г!

! Р

Научный руководитель| д.т.н. Турлапов Вадим Евгеньевич

Нижний Новгород - 2013

■ .да; < 111

и

Содержание

® Введение.............................................................................................................................................4

Глава 1. Обзор публикаций и программного обеспечения по теме исследования...................10

• 1.1. Трассировка лучей и глобальное освещение................................................................10

1.2. Интерактивная трассировка лучей................................................................................13

1.3. Интерактивное глобальное освещение.........................................................................53

ф 1.4. Выводы к главе 1.............................................................................................................59

Глава 2. Система моделей для алгоритмизации и конвейерной реализации лучевых методов синтеза изображений на массивно-параллельных ф вычислительных архитектурах......................................................................................................61

2.1. Элементы энергетического подхода к физически достоверному моделированию глобального освещения.............................................................................61

2.2. Моделирование рассеяния света на поверхностях материалов..................................67

2.3. Исследование специализированных форм уравнения визуализации, подлежащих реализации в методах глобального освещения............................................70

2.4. Уравнение измерения как основа физически достоверного синтеза изображений...........................................................................................................................73

•

2.5. Моделирование пространства путей для решения уравнения

измерения методом Монте-Карло........................................................................................74

2.6. Компоненты генерации случайных путей для класса методов

глобального освещения.........................................................................................................76

2.7. Покомпонентное представление метода стохастической трассировки

путей в системе моделей глобального освещения..............................................................81

2.8. Реализация и модификация двунаправленной трассировки путей на

основе системы моделей глобального освещения..............................................................89

^ 2.9. Выводы к главе 2.............................................................................................................95

Глава 3. Универсальный конвейер трассировки лучей для интерактивного синтеза изображений методами глобального освещения на графических процессорах........................96

3.1. Построение на графическом процессоре эффективной ускоряющей

структуры для лучевых методов синтеза изображений.....................................................97

3.2. Метод представления и сериализации иерархической

объектно-ориентированной модели сложной сцены........................................................111

3.3. Компоненты универсальной системы синтеза изображений

методами глобального освещения......................................................................................123

3.4. Выводы к главе 3...........................................................................................................146

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

освещения и его экспериментальное исследование...................................................................148

4.2. Состав и структура программного комплекса интерактивного синтеза изображений методами глобального освещения.............................................................148

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

4.4. Исследование алгоритма «усеченной» двунаправленной трассировки

путей в различных условиях переноса световой энергии................................................155

4.5. Исследование производительности программного комплекса................................163

4.6. Выводы к главе 4...........................................................................................................170

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

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

Введение

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

Традиционный способ визуализации динамических 3D сцен в реальном времени основан на алгоритме растеризации, который аппаратно ускоряется графическими процессорами и доступен через интерфейсы (API) OpenGL и Direct3D. Данный подход не позволяет обрабатывать вторичное освещение и физически достоверные модели материалов и источников света. К настоящему моменту предложены различные подходы для имитации тех или иных эффектов глобального освещения, среди которых следует отметить методы внешней преграды (ambient occlusion), отражающих теневых карт (reflective shadow maps), мгновенной излу-чательности (instant radiosity), а также методы фотонных карт в пространстве изображения (image space photon mapping). Перечисленные подходы позволяют добиться высокой производительности за счет аппаратной растеризации, однако воспроизводят только часть необходимых эффектов. Интерфейсы 3D графики не поддерживают трассировку лучей, на основе которой реализуются многие методы глобального освещения.

В последние годы появились и активно развиваются универсальные инструменты программирования (NVIDIA CUDA, OpenCL, Compute Shaders), которые позволяют задействовать вычислительные возможности графических ускорителей для широкого класса задач. Современный графический процессор NVIDIA GeForce GTX 680 имеет пиковую производительность свыше 3 Терафлопс, что позволяет говорить об эпохе персональных супервычислений. Основным препятствием на пути к использованию таких ресурсов является высокая сложность разработки для массивно-параллельных графических архитектур, связанная с необходимостью глубокой переработки традиционных алгоритмов.

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

пределами. Подтверждением этому является значительное число публикаций, среди которых следует отметить работы I.Wald, J. Gunther, S. Popov, H.-P. Seidel, S. Boulos, T. Ize, W. Hunt, С. Benthin, M. Wagner, V. Havran, C. Wächter, A. Keller, С. Lauterbach, T. Purcell, I. Buck, T. Foley, J. Sugerman, D. Horn, N. Thrane, L. Simonsen, W. Mark, M. Houston, P. Hanrahan, H. Jensen, S. Parker, P. Shirley, P. Slusallek, S. Woop, J. Schmittler, D. Hall, T. Aila, S. Laine, K. Zhou, R.Wang, a также Ю. Баяковского, В. Галактионова, А. Волобоя, Б. Барладяна, J1. Шапиро, К. Гаранжи, К. Вострякова, А. Игнатенко, А. Адинца, В. Фролова и др. Публикации последних лет показывают устойчивую тенденцию к возрастанию роли графического процессора в расчете глобального освещения. Вместе с тем, остаются актуальными как достижение интерактивности в синтезе изображений 3D сцен (с учетом глобального освещения), так и разработка системного решения для графических процессоров. Поиску данного решения и посвящено настоящее исследование.

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

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

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

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

о Расширяемую подсистему моделей материалов и источников света, которая обеспечивает Монте-Карло-ориентированное описание оптических свойств поверхностей (BSDF) и излучающих свойств источников.

о Механизм описания 3D сцены, который позволяет сочетать в одной модели полигональные и нетесселированные объекты (фрагменты сплошных сред, неявно за-

данные и сплайновые поверхности, поверхности второго порядка, фрактальные множества).

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

о Ускоряющую структуру, которая обеспечивает эффективное параллельное построение на графических процессорах и высокую скорость визуализации.

• Разработать программный комплекс, реализующий предложенные решения с использованием инструментов параллельного программирования графических архитектур (NVIDIA CUDA, OpenCL, OpenGL).

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

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

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

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

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

1) Эффективная для статических и динамических сцен ускоряющая структура, на базе иерархии ограничивающих объемов, отличающаяся реализацией алгоритма построе-

ния полностью на графическом процессоре (до 5-ти раз быстрее лучшей известной реализации на момент публикации результатов).

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

3) Программный конвейер трассировки лучей, который реализует типовые блоки (операции) лучевых алгоритмов визуализации и отличается универсальностью на классе методов глобального освещения и ориентированностью на массивно-параллельные вычислительные архитектуры. На базе блоков данного конвейера построены методы: испускание лучей (ray casting), трассировка лучей Уиттеда (Whitted ray tracing), стохастическая трассировка путей в прямом и обратном направлении (light tracing и path tracing), двунаправленная трассировка путей (bidirectional path tracing), а также предлагаемый в настоящем исследовании ее «усеченный» вариант.

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

5) Метод «усеченной» двунаправленной трассировки путей, который строится на типовых операциях конвейера трассировки лучей и отличается фиксированным объемом потребляемой памяти при обработке путей любой длины, эффективной реализацией многократной выборки по значимости, полным исключением фазы соединения путей.

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

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

• Программная библиотека графа сцены, которая отличается от аналогов (таких как OpenSceneGraph и OpenSG) поддержкой эффективной сериализации данных и гибридных сцен (сочетающих полигональные и нетесселированные объекты).

• Встраиваемый модуль визуализации («плагин») для системы 3D моделирования Blender, который базируется на разработанной библиотеке расчета глобального освещения

(аналогичные модули могут быть разработаны для систем Autodesk 3D Studio Мах и Maya, Maxon Cinema 4D, DAZ Studio, Smith Micro Poser).

• Автономная система синтеза изображений методами глобального освещения в интерактивном режиме с поддержкой основных (более 20) форматов хранения геометрии и описания материалов. Система может служить методическим пособием к вузовским курсам по компьютерной графике и физической оптике.

Таким образом, получен ряд практических результатов, востребованных в различных областях компьютерной графики. Программная библиотека лучевых методов синтеза изображений внедрена в комплекс научной визуализации ScView РФЯЦ-ВНИИЭФ. Лабораторные работы по лучевым методам, разработанные в процессе подготовки диссертации, внедрены в учебный процесс ННГУ.

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

Апробация работы. Основные результаты доложены и обсуждены на:

• 19-й международной конференции по компьютерной графике и зрению «GraphiCon-2009», Москва;

• 20-й международной конференции по компьютерной графике и зрению «GraphiCon-2010», Санкт-Петербург;

• 21-й международной конференции по компьютерной графике и зрению «GraphiCon-2011», Москва;

• 22-й международной конференции по компьютерной графике и зрению «GraphiCon-2012», Москва;

• Международной научной конференции «Параллельные Вычислительные Технологии», Нижний Новгород, 2009;

• Всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах», Нижний Новгород, 2011;

• Семинарах кафедры МО ЭВМ факультета ВМК ННГУ.

Лабораторные комплексы по трассировке лучей, глобальному освещению и вычислениям на GPU внедрены в курсы «Компьютерная графика» и «Современная компьютерная графика» на факультете ВМК ННГУ; использованы в образовательных проектах Intel Winter School

2008 и Intel Studio Graphics 2008; цикле Интернет-лекций и мастер-классов по компьютерной графике по гранту ФЦП СПбУ ИТМО (20 часов, ноябрь 2009); всероссийской научной школе для молодежи «Компьютерное зрение, 3D моделирование и компьютерная графика» 2010 (госконтракт №02.741.12.2170). Работа прошла конкурсный отбор для участия в программе У.М.Н.И.К (госконтракт №8753р/13130).

Публикации. Основные результаты исследования опубликованы в 13 работах, из них 4 -публикации в изданиях, рекомендованных ВАК.

Основные положения, выносимые на защиту:

1) Эффективная ускоряющая структура на базе иерархии объемов, отличающаяся наличием высокопроизводительного алгоритма ее параллельного построения на графическом процессоре.

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

3) Новый метод «усеченной» двунаправленной трассировки путей, реализуемый на типовых операциях кон�