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

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

НОВИКОВ Илья Евгеньевич

РАЗРАБОТКА АЛГОРИТМОВ УСКОРЕНИЯ РАСЧЕТА ИЗОБРАЖЕНИЙ ТРЕХМЕРНЫХ СЦЕН ПО МЕТОДУ СВЕТОВЫХ

СЕТОК

05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2009

003475891

Работа выполнена в Учреждении Российской академии наук институте вычислительной математики и математической геофизики Сибирского отделения РАН.

Научный руководитель: доктор технических наук

Дебелов Виктор Алексеевич

Официальные оппоненты: доктор физико-математических наук

Лаврентьев Михаил Михайлович

доктор физико-математических наук Клименко Станислав Владимирович

Ведущая организация: Институт прикладной математики РАН

им. М.В. Келдыша

Защита состоится " 29 " сентября 2009 года в 15 часов на заседании диссертационного совета Д 003.061.02 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6.

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

Автореферат разослан "с?6 " аМ^сЫ 2009 г.

Ученый секретарь

диссертационного совета Д 003.061.02 при ИВМиМГ СО РАН, д.ф.-м.н.

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

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

Существуют разные математические модели освещенности сцены, на основе которых строится изображение трехмерной сцены. Выбор конкретной модели для применения на практике зависит от цели, для которой создается изображение. Например, для компьютерных игр высокая скорость расчета изображения приоритетнее высокого качества изображения, недостаток качества часто компенсируется высокой динамикой видеоряда. В этой области применяется локальная модель освещенности, которая используется в алгоритме сканирующей строки (OpenGL и DirectX). Если высокое качество изображения и физическая корректность приоритетнее скорости расчета, подходящей моделью является глобальная модель освещенности, которая используется в таких вычислительно трудоемких алгоритмах, как излучательность и методы Монте-Карло. Но в подавляющем большинстве случаев на практике требуется решение задачи реалистической визуализации, сбалансированное по скорости расчета и качеству изображения. На современном этапе этому критерию наиболее полно отвечает модель освещенности Виттеда, используемая в алгоритме обратной рекурсивной лучевой трассировки (OPJIT), известном как light-backwards recursive ray tracing, который был введен Витгедом еще в 1980 г. и до сих пор, в основном, применяется на практике.

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

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

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

На практике часто требуется быстрый расчет изображения, пусть даже с некоторым нарушением реалистичности, т.е. точности геометрии теней. Например, при получении предварительных изображений при создании мультфильма. В таком случае дерево лучей, как правило, не строится, т.е. ОРЛТ заменяется нерекурсивной обратной лучевой трассировкой (OJIT или ray casting), а модель освещенности называется локальной моделью освещенности с тенями. При этом достаточно имитировать мягкие тени, создавая иллюзию реалистичности. Например, мультфильм Shrek: тени в изображениях мягкие, и зрителю не важно, насколько точно они рассчитаны. Важно, чтобы зрительные ощущения удовлетворяли общим представлениям о реализме: граница тени должна быть размытой (отсутствие фантомов), большие источники освещения дают более размытую тень, небольшие объекты дают малозаметные тени и т.д. Часто бывает достаточно схематично обозначить тени, чтобы добиться нужного эффекта. Большинство алгоритмов генерации (имитации) мягких теней основано на алгоритме теневых карт (АТК), предложенном Вильямсом в 1978 г., и алгоритме теневых объемов (ATO), введенном Кроу в 1977 г. Как правило, эти алгоритмы, обеспечивающие быстрый расчет изображений, подходят только для получения предварительных/черновых изображений. Генерация мягких теней в рамках рекурсивного ОРЛТ остается практически не исследованной на предмет ускорения расчетов, которое позволило бы получать качественное изображение за приемлемое время. На практике для создания конечного изображения используется подход аналогичный "Area shadows" в Autodesk 3ds Мах, который назовем интегральным.

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

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

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

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

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

1. Анализ существующих алгоритмов генерации мягких теней с точки зрения их практического применения в рамках модели освещенности Виттеда.

2. Анализ скоростных и качественных характеристик алгоритмов генерации мягких теней, основанных на алгоритме теневых карт и на алгоритме теневых объемов, в сравнении с методом световых сеток.

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

Основные научные положения, разработанные соискателем, и их новизна:

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

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

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

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

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

На защиту выносятся следующие основные результаты:

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

2. Алгоритмы ускорения метода световых сеток, разработанные с учетом специфики расчетов по методу световых сеток.

3. Алгоритмы ускорения метода световых сеток за счет комплексирования метода световых сеток с алгоритмами теневых карт и теневых объемов.

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

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

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

Апробация работы. Результаты работы докладывались на XLIII международной научной студенческой конференции (Новосибирск, 2005), конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2005, 2008; Томск 2009), XV, XVII и XVIII международных конференциях по компьютерной графике и ее приложениям "Графикон" (Новосибирск, 2005; Москва, 2007, 2008), конференции молодых ученых ИВМиМГ (Новосибирск, 2006), IX всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2008). Работа выполнялась при финансовой поддержке РФФИ по грантам 06-07-89216_а "Разработка алгоритмов физически корректной визуализации сцен с кристаллами", 08-07-12094_офи "Разработка и создание прототипа программного продукта реалистической визуализации пространственных сцен, основанного на методе световых сеток".

Публикации. По теме диссертации опубликовано 10 работ, из них 1 по перечню ВАК Минобрнауки России.

Структура и объем работы. Диссертация общим объемом 126 страниц состоит из введения, 4 глав, заключения и списка литературы. В работе содержится 64 рисунка и 6 таблиц. Список литературы включает 84 наименования.

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

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

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

рации мягких теней: интегрального подхода к генерации мягких теней и многочисленных модификаций алгоритмов АТК и ATO.

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

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

• Для поверхности определена операция пересечения с лучом.

• В каждой точке поверхности Р определена нормаль й(Р).

• Все объекты сцены заданы в декартовой мировой системе координат. Сцена освещается nL точечными источниками освещения L¡, специфицированными интенсивностями излучения / и позициями в пространстве LP, i = \,...,nL. Камера - это набор параметров, характеризующих наблюдателя: позиция и ориентация в пространстве, высота и ширина экрана.

Алгоритм OPJIT заключается в попиксельном расчете изображения. Через каждый пиксель выпускается луч из камеры в сцену. Отыскивается ближайшая точка пересечения луча с объектами сцены, и значение интенсивности пикселя рассчитывается, исходя из свойств материала поверхности сцены в точке и источников освещения, из которых она видна. Пусть луч из камеры имеет ближайшее пересечение с поверхностью сцены в точке Р. Базовую формулу расчета значения интенсивности в точке Р по ОРЛТ можно кратко записать как

I„{F) = Amb + jír V{LP„F) Q(¿,, P) + k,I, + k,I, = Amb + URT{P) + k,Ir + k,I„ (1)

M

здесь Amb - интенсивность рассеянного света, fl(L,P) характеризует конкретную локальную модель освещенности, 1г — интенсивность, пришедшая с направления отраженного вектора; /, - интенсивность, пришедшая через поверхность из-за прозрачности. V(LP,P) - булева функция видимости /-го точечного источника из точки Р. Эта функция говорит о том находится тестируемая точка в тени /'-го источника (значение 0), пли освещена им (значение 1). Изложение предполагает, что задача реалистического рендеринга решается в рамках локальной модели освещенности с тенями, а сцена состоит из непрозрачных объектов. Случаи рассмотрения задачи глобальной освещенности (рекурсия, полупрозрачные объекты) будут специально оговариваться. Параграф 1.2 посвящен классической модели камеры. Определяются ее параметры, вводятся понятия: непрерывного изображения и дискретного изображения (буфера кадра), непрерывной карты глубины и дискретной карты глубины (буфера глубины).

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

В параграфе 1.4 дается формальное описание алгоритма ATO. ATO для определения видимости изображаемой точки использует дополнительные геометрические построения, называемые теневыми объемами. Теневые объемы - это полубесконечные поверхности, получаемые вытягиванием геометрии силуэтов объектов от источника на бесконечность. Если изображаемая объектная точка попадает внутрь хотя бы одного теневого объема, источник не виден - точка в тени источника. ATO использует особенности графических акселераторов, реализация этого алгоритма на центральном процессоре лишена практического смысла. Детально рассмотрен ATO и обоснованы его основные характеристики: это быстрый алгоритм генерации четких теней; применяется только для полигональных сцен; страдает от артефактов в изображениях, вызванных полигональным представлением объектов; не применяется в рекурсивной постановке расчета изображения; не работает для полупрозрачных объектов. В параграфе 1.5 рассматривается гибридный алгоритм генерации четких теней на базе алгоритмов АТК и ATO. Данный алгоритм позволяет получать изображения с меньшим количеством артефактов, чем АТК, но требует больше времени на расчет изображений, он наследует артефакты ATO и применим только для полигональных сцен.

Параграф 1.6. В пункте 1.6.1 данного параграфа рассматривается интегральный подход к генерации мягких теней в рамках алгоритма OPJIT (типа "Area shadows" в Autodesk 3ds Мах). Этот подход заключается в том, что точечный источник, дающий четкую тень, заменяется множеством точечных источников, приближающих объемный источник и дающих мягкую тень. Основные характеристики данного подхода: свободен от, артефактов; правильно работает в рекурсивной постановке; правильно работает в случае наличия в сцене полупрозрачных поверхностей; скорость расчета изображений во много раз медленнее, чем у базового OPJ1T с одним точечным источником.

Остальная (большая) часть параграфа посвящена исследованию 20 алгоритмов генерации мягких теней, разработанных в 1994 - 2007 годах. В параграфе 1.7 дается заключение по главе.

Во второй главе вводится метод световых сеток, выполняется сравнение скоростных характеристик ОРЛТ и МСС, рассматривается интеграция МСС в существующие программы рендеринга, дается сравнение МСС с алгоритмами генерации мягких теней на базе АТК и ATO.

Параграф 2.1. Световая сетка LM = [xk - это равномерная сетка с шагом h и размером NlM = х NLyM х Nf в пространстве сцены, каждая точка световой сетки хк (световая точка) хранит шкалу видимости для каждого источника.

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

Ош(Р,г) = {х:хе Ш\\Р-х\\ < r,(f¡(P),x-P) > 0, V(P,x) = l}.

Аналогично формуле (1) базовую формулу расчета значения интенсивности в точке Р по МСС представим как

1

1ш(Р) = АтЬ + £

^V(LP,xk)X(PyL) Q(L„P) тТГх 1

+kI+kJ

' r ' ' (2)

= Amb + ULU (P) + kjr+ k,I,,

\\,{п{Р),{1Р-Р))>0 здесь — \ - функция, которая говорит о том, осве-

[0, иначе

щает источник объектную точку спереди (значение 1) или сзади (значение 0). т - число световых точек в интерполяционном множестве. Если т = 0, тогда значение интенсивности в точке Р по МСС рассчитывается по формуле (1), т.е. в этом случае 111М {Р) = ирТ (Р).

В параграфе 2.2 строятся оценки вычислительных затрат для ОРЛТ и МСС. В формуле (1) критической является операция вычисления взаимной видимости источника и объектной точки У(ЬРпР). Для выполнения этой операции необходимо отыскание пересечения отрезка [Р,ЬР:] со сценой. Длина такого отрезка сравнима с габаритами сцены, поэтому тест видимости источника объектной точкой можно охарактеризовать как длинный тест. Пусть СОЗТ^ - среднее

время выполнения длинного теста, тогда затраты СОЭТ^ на использование формулы (1) можно оценить как

СОБТкт * Ыа,т х МСат х п1 х СОБТ^. (3)

В формуле (2) определяется взаимная видимость источника и световой точки УЦРпхк), поэтому длинный тест является базовой операцией и для МСС. Кроме того, в МСС есть вторая базовая операция: проверка локальной видимости У(Р, хк), т.е. пересечение отрезка [Р,х4] со сценой. Длина этого отрезка ограничена радиусом интерполяционного множества г, который мал в сравнении с

габаритами сцены, поэтому такой тест можно охарактеризовать как короткий тест. Пусть COSTShar1 - среднее время выполнения короткого теста, ULM -число использованных в расчете световых точек, mHSp - число световых точек в полусфере радиуса г, тогда затраты COSTLM на использование формулы (2) можно оценить как

COSTLM COSTUng + NCam х МСат хт^ х COST№ort. (4)

В случае применения наиболее очевидного алгоритма пересечения отрезка, который заключается в последовательной проверке пересечения отрезка с каждым объектом сцены, COSTShort = COST^, следовательно

COSTLU » {иш + COSTbmg. (5)

Сравним формулы (3) и (5). Заметим, что Um и mHSp не зависят от числа источников и разрешения изображения. Возьмем nL и ЫСит х МСат настолько большие, что mHSp <пЫ 2, a ULM < (NCam х МСат) / 2. В таком случае

COSTLM <NamixMCamxnLxCOST. «COSTRT. (6)

Рис. 1. Сравнение времени расчета изображения по OPJIT и МСС Следовательно, при росте числа источников и разрешения изображения наступает момент (для каждой сцены свой), когда МСС начинает выигрывать по времени у OPJIT. Данный результат подтвержден экспериментально: на рис. 1,а график зависимости времени расчета от разрешения изображения для одной из тестовых сцен. Сцена состоит из 27000 треугольников, освещена двумя точечными источниками, габариты сцены по трем координатным осям: 400x200x350. Параметры расчета по МСС: шаг световой сетки h = 1, радиус интерполяционной сферы г = 3.1. Видно, что существует разрешение, начиная с которого расчет сцены по МСС быстрее расчета по OPJIT. На рис. 1,6 график зависимости времени расчета от числа источников для той же сцены. Разрешение изображения 1024x1024 пикселей, для МСС использованы параметры: шаг световой сетки h = 2, радиус интерполяционной сферы г = 6.2. На графике видно, что, начиная с некоторого числа источников, МСС выигрывает у OPJIT по скорости расчета изображения.

В параграфе 2.3 показано, как МСС может быть интегрирован в существующие программы рендеринга, на примере программы Autodesk 3ds Max. В параграфе 2.4 дается сравнение МСС с алгоритмами генерации мягких теней, описанными в первой главе диссертации:

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

2. Изображения, полученные с помощью алгоритмов на базе АТК и ATO, страдают от артефактов: алиасинг, протечки света/тени, некорректное самозатенение, неправильное размытие границы тени и т.д. МСС позволяет получать изображения, свободные от артефактов, сравнимые по качеству с эталонным интегральным подходом к генерации мягких теней.

3. Ни один из алгоритмов на базе АТК и ATO не применим на практике в случае рекурсивной лучевой модели из-за наличия артефактов, на которые было указано выше. МСС как модификация OPJIT позволяет получать изображения, свободные от артефактов и в рекурсивном случае.

4. Для сцен, содержащих полупрозрачные поверхности, алгоритмы на базе АТК и ATO не применимы вообще, т.е. эти алгоритмы конструктивно не предполагают наличие полупрозрачных объектов в сцене. Для МСС было выполнено специальное исследование (Васильева Л.Ф. и др., 2008), показывающее применимость МСС для расчета изображений сцен, содержащих полупрозрачные объекты.

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

• МСС работает в рекурсивной лучевой трассировке.

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

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

• Поскольку МСС использует длинный тест не в каждой объектной точке как OPJ1T, а только в световых точках, МСС асимптотически выигрывает у OPJIT по скорости расчета изображения.

• Как следствие предыдущего, МСС значительно выигрывает по скорости у интегрального подхода расчета мягких теней и, следовательно, вполне может заменить его в ряде приложений.

• МСС может быть встроен в любое приложение, осуществляющее расчет изображения на основе OPJIT.

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

В параграфе 3.1 представлен алгоритм, использующий файлы-шаблоны для быстрого построения интерполяционного множества. При построении интерполяционного множества для объектной точки Р строится сфера радиуса г. Чтобы отобрать световые точки, которые находятся внутри этой сферы, для всех световых точек, попадающих в воображаемый куб, включающий в себя интерполяционную сферу, проверяется условие ||jct - Pfl < г. Учитывая, что число точек в кубе больше числа точек, которые попадут в сферу после проверки этого условия, данная проверка требует существенных вычислительных затрат. Кроме того, для обхода световых точек из воображаемого куба используется тройной цикл, к тому же для каждой световой точки требуется вычислить ее координаты в пространстве сцены. Идея данного алгоритма состоит в том, что можно заранее совершить обход световых точек, кандидатов на попадание в интерполяционное множество, вычислить для каждой световой точки расстояние до изображаемой объектной точки и отобрать световые точки, удовлетворяющие условию ||xt - Р|| < г. Для этого в кубе со стороной, равной шагу световой сетки А, вводится более частая подсетка с шагом h/ns, где ns - некоторое натуральное число (в наших экспериментах as = 10). Для каждой точки подсетей выполняется проверка расстояния до световых точек, как если бы эта точка была изображаемой объектной точкой. Смещения индексов световых точек, прошедших проверку, относительно точки подсетей записываются в файл-шаблон. Если выполнить описанные действия для набора соотношений r/h (например, r/h = 1.1,1.2,...,4.1), мы получим библиотеку файлов-шаблонов. При расчете изображения в библиотеке отыскивается нужный файл-шаблон, определяется ближайшая к изображаемой точке точка подсетей и извлекаются смещения индексов для световых точек, образующих интерполяционное множество.

В параграфе 3.2 рассматривается алгоритм оптимизации проверок локальной видимости V(P,xk) по "граничным" и "внутренним" точкам. Рассмотрим пример на рис. 2,а. Вблизи объектной точки Р кроме примитива, которому принадлежит точка Р, находится множество других примитивов. Эта ситуация соответствует, например, сцене, изображающей листву деревьев. Заметим, что все световые точки интерполяционного множества видны точкой Р. Идея состоит в том, что тест видимости первоначально проводится для точек b,,...,b6, являющихся "граничными" для множества точек интерполяционной сферы. Если, например, точки Z>, и Ь2 видны точкой Р, то видна и "внутренняя" точка г,. Если все граничные точки видны точкой Р, то видны и все внутренние. В итоге для примера, изображенного на рис. 2,а, вместо 12 тестов видимости необходимы только 6.

Возможна и ошибка при определении локальной видимости для внутренних точек с использованием данной оптимизации. На рис. 2,6 видно, что хотя точки 6, и Ьг видны точкой Р, точка гх скрыта от точки Р стыком примитивов. Аналогично точки Ь5 и Ь6 видны точкой Р, но точка г4 скрыта от точки Р небольшим примитивом. Однако для большинства сцен, встречаемых на практике, подобные ситуации не проявляются. Действительно, объекты в трехмерных сценах, как правило, обладают телесностью, т.е. для них не характерны ситуации, изображенные на рис. 2,6. Кроме того, для получения реалистичных мягких теней по МСС шаг световой сетки выбирается много меньшим, чем размеры примитивов. Чтобы гарантированно исключить ошибку, шаг световой сетки можно задавать, например, как половину размера наименьшего из объектов сцены. В параграфе 3.3 излагается еще один алгоритм ускорения расчетов по МСС. Дополним описание пространственной сцены требованием телесности (solid) всех объектов. Заметим, что в реальном мире это требование выполняется всегда, в том числе и в большинстве модельных трехмерных сцен. Предположим, что наиболее часто протечки света проявляются, когда в интерполяционную сферу попадают световые точки, находящиеся внутри какого-либо объекта сцены. Эти световые точки не видны объектной точкой независимо от ее положения в сцене. Тест локальной видимости используется, чтобы отбраковать такие точки. Но попадание световой точки внутрь объекта достаточно определить один раз, причем независимо от числа источников в сцене. Точка находится внутри какого-либо объекта сцены, если луч, выпущенный из этой точки, пересечет сцену нечетное число раз. В противном случае - четное. Таким образом, для определения попадания точки внутрь объекта сцены необходимо решить один длинный тест. В случае определения локальной видимости объектная точка, относительно которой выполняется проверка, гарантированно не лежит внутри ни одного из объектов. Поэтому длинный тест можно заменить коротким тестом (из объектной точки в световую точку), что дает дополнительную экономию вычислительных затрат.

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

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

Таблица 1. Времена расчета (с)

МС<т X МСа„ А г/к ОРЛТ МСС 3.1 3.2 3.3

1024 2.0 2.1 39.4 36.3 35.0 22.5

3.1 30.4 97.2 90.5 83.2 32.3

1024 1.0 2.1 53.1 49.7 48.1 44.1

3.1 116.0 109.3 100.7 75.9

2048 2.0 2.1 130.1 118.3 112.9 53.4

3.1 121.6 342.2 316.0 286.6 68.1

2048 1.0 2.1 137.4 125.1 119.1 80.2

3.1 326.9 301.9 267.7 118.9

В параграфе 3.5 приводятся результаты численных экспериментов. В табл. 1 представлены времена расчета для тестовой сцены, описанной в § 2.2. В ходе расчетов варьировались: разрешение изображения х МСап, шаг световой сетки И и радиус интерполяционной сферы (приведен в шагах световой сетки г /Л). Обозначения столбцов: "ОРЛТ" - время расчета изображения по ОРЛТ, "МСС" - время расчета изображения по МСС без ускорений, "3.1" - время расчета изображения по МСС с ускорением § 3.1, "3.2" - время расчета изображения по МСС с ускорениями § 3.1 - 3.2, "3.3" - время расчета изображения по МСС с ускорениями § 3.1 - 3.3.

Для данной сцены ускорение 3.1 позволяет сократить время расчета в среднем на 8%, ускорение 3.2 - на 7%, ускорение 3.3 - на 43%. С применением всех ускорений время расчета изображения составляет в среднем 0.5 от времени расчета с использованием базового МСС без ускорений.

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

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

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

В четвертой главе ставится и решается задача ускорения МСС за счет применения графического акселератора с использованием подходов алгоритмов АТК и ATO. Базовым МСС будем называть реализацию МСС без ускорений. Параграф 4.1. В § 2.2 была выполнена оценка вычислительных затрат на генерацию теней по МСС, выраженная в формуле (4). В этом выражении величина первого слагаемого ULU xnLx COST'Ung определяется временем выполнения длинного теста COSTUmg. Для того, чтобы уменьшить COST'Lo„¡, рассматриваются два подхода: 1) комплексирование МСС с АТК; 2) комплексирование МСС с ATO.

Основная идея: МСС работает независимо от того, каким способом вычисляется видимость источника для световой точки. Если заимствовать положительное качество АТК и ATO - быстрый тест видимости источника, т.е. комплексиро-вать МСС с АТК или ATO, мы получим гибридный алгоритм генерации мягких теней, часть которого предназначена для исполнения на центральном процессоре, а другая часть - на графическом акселераторе. Очевидно, что такая аппарат-но ускоренная модификация МСС позволит рассчитывать изображения быстрее. COST'Long, т.е. затраты на определение видимости источника на графическом акселераторе в сумме составляют меньше секунды даже для сцен, состоящих из порядка миллиона треугольников, поэтому ими можно пренебречь. Отметим, что первое слагаемое формулы (4) является определяющим в оценке вычислительных затрат МСС, особенно для сложных сцен, содержащих большое число источников освещения, поэтому уменьшение COSI'Ung очень значительно для расчета изображений по МСС.

В параграфе 4.2 детально описан расчет изображения при помощи гибридного алгоритма МСС+АТК по шагам.

Таблица 2. Сравнение времен расчета для гибридных алгоритмов (с)

No,n, х Мо,т h г/А МСС МСС+АТК МСС+АТО

1024 2.0 2.1 13.2 И.О 12.3

3.1 20.5 16.7 18.0

1024 1.0 2.1 18.4 11.6 19.8

3.1 28.9 17.7 25.9

2048 2.0 2.1 45.4 41.9 43.9

3.1 69.9 63.9 65.5

2048 1.0 2.1 51.1 43.0 51.6

3.1 79.1 66.1 74.3

В параграфе 4.3 детально описан расчет изображения при помощи гибридного алгоритма МСС+АТО по шагам.

В параграфе 4.4 приводятся результаты численных экспериментов. В табл. 2 представлены времена расчета для тестовой сцены, описанной в § 2.2. В ходе расчетов варьировались: разрешение изображения NCMm х МСат, шаг световой сетки h и радиус интерполяционной сферы (приведен в шагах световой сетки г! И). Все три алгоритма содержат ускорения, описанные в § 3.1 - 3.3. МСС+АТК позволяет сократить время расчета в среднем на 21%, т.е. время расчета изображения составляет в среднем 0.4 от времени расчета базовым МСС. Для этой же сцены МСС+АТО позволяет сократить время расчета в среднем на 11%, т.е. время расчета изображения гибридом МСС+АТО составляет в среднем 0.45 от времени расчета базового МСС.

В параграфе 4.5 исследуется качество изображений, получаемых при помощи гибридных алгоритмов МСС+АТК и МСС+АТО. Установлено, что погрешность, вносимая АТК в расчет по МСС, составляет в среднем 3%, а для ATO -менее 1%, не приводит к появлению артефактов в изображениях. Параграф 4.6 - заключение по главе. Гибридные алгоритмы ускорения МСС позволяют распределить вычисления между центральным процессором и графическим акселератором. В зависимости от типа сцены расчет изображения при помощи гибрида МСС+АТК занимает в среднем 0.33 - 0.4 от времени расчета с использованием МСС без ускорений. Гибрид МСС+АТО в сравнении с гибридом МСС+АТК требует больше времени на расчет изображения, но дает более точное решение.

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

Основные результаты

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

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

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

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

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

Публикации по теме диссертации

В рецензируемых журналах из списка ВАК

1. Дебелов В.А., Новиков И.Е. Генерация мягких теней при использовании алгоритма трассировки лучей // Вестник НГУ. Серия: Информационные Технологии. - 2009. - Т. 7, № 2. - С. 18-41.

В других изданиях

2. Дебелов В.А., Васильева Л.Ф., Новиков И.Е. Развитие метода световых сеток для алгоритма лучевой трассировки: аппроксимация решения, реализация на графическом акселераторе // Тр. 15-й междунар. конфер. по компьютерной графике и ее приложениям Графикон'2005. - Новосибирск, 2005. - С. 355— 359.

3. Новиков И.Е. Обзор алгоритмов аппаратного ускорения метода лучевой трассировки // Proc. of 6th International Workshop on Virtual Environment on PC Cluster, VEonPC-2006, Protvino-Altai. - Протвино: Изд. ИФТИ, 2006. - С. 22-30.

4. Дебелов В.А., Новиков И.Е. Некоторые подходы к ускорению метода световых сеток // Тр. 17-й междунар. конфер. по компьютерной графике и ее приложениям Графикон'2007. - М., 2007. - С. 277-284.

5. Новиков И.Е. Ускорение метода световых сеток за счет комплексирования с алгоритмом теневых карт и алгоритмом теневых объемов - Новосибирск, 2009. - 22 с. - (Препр. / РАН. Сиб. отд-е ИВМиМГ; № 1167).

6. Новиков И.Е. Сравнение двух алгоритмов генерации мягких теней // Программа и тез. докл. IX Всероссийской конф. молодых ученых по математическому моделированию и информационным технологиям. - Кемерово, 2830 октября 2008 года. - Новосибирск: Изд. ИВТ СО РАН, 2008. - С. 87-88. Эл. версия полного текста: http://www.nsc.ru/ws/YM2008/14366/Novikov.Ddf.

7. Новиков И.Е. Использование современного графического ускорителя для реализации метода световых сеток // Матер, конференции-конкурса "Технологии Microsoñ в теории и практике программирования". - Новосибирск: Изд. НГУ, 2005. - С. 57-59.

8. Новиков И.Е. Использование современного графического ускорителя для реализации метода световых сеток // Тр. XLIII Международной научной студенческой конференции "Студент и научно-технический прогресс". - Новосибирск: Изд. НГУ, 2005. - С. 47-48.

9. Новиков И.Е., Кочергин H.A. Сравнение качественных и скоростных характеристик метода теневых карт и метода световых сеток // Матер, конференции-конкурса "Технологии Microsoft в теории и практике программирования". - Новосибирск: Изд. НГУ, 2008. - С. 44-15.

Ю.Новиков И.Е. Ускорение расчета изображений трехмерных сцен по методу световых сеток с использованием графического акселератора // Матер. VI Всероссийской научно-практической конференции студентов, аспирантов и молодых ученых. - Томск: Изд. ТПУ, 2009. - С. 323-325.

Автореферат:

Формат 60x84 1/6, i п. л. Тираж 100 экз. Заказ № 466. 30.07. 2009

Отпечатано ЗАО РИЦ «Прайс-курьер» ул. Кутателадзе, 4г, т. 330-7202

Введение.

1. Обзор.

1.1. Обратная рекурсивная лучевая трассировка.

1.2. Камера, буфер глубины, изображение.

1.3. Теория метода теневых карт.

1.3.1. Непрерывный случай.

1.3.2. Дискретный случай.

1.3.3. Примеры артефактов на изображениях.

1.4. Теория метода теневых объемов.

1.4.1. Непрерывный случай.

1.4.2. Дискретный случай.

1.4.3. Общие замечания.

1.5. Комбинированные алгоритмы генерации теней.

1.6. Мягкие тени в ОРЛТ.

1.6.1. Интегральный подход.

1.6.2. Метод теневых карт и мягкие тени.

1.6.3. Метод теневых объемов и мягкие тени.

1.6.4. Краткая характеристика алгоритмов генерации мягких теней.

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

Существуют разные математические модели освещенности сцены, на основе которых строится изображение трехмерной сцены. Выбор конкретной модели для применения на практике зависит от цели, для которой создается изображение. Например, для компьютерных игр высокая скорость расчета изображения приоритетнее высокого качества изображения, недостаток качества часто компенсируется высокой динамикой видеоряда. В этой области применяется локальная модель освещенности, которая используется в алгоритме сканирующей строки [78, 79] (OpenGL и DirectX). Если высокое качество изображения и физическая корректность приоритетнее скорости расчета, подходящей моделью является глобальная модель освещенности, которая используется в таких вычислительно трудоемких алгоритмах, как излучательность [37, 43] и методы Монте-Карло [43]. Но в подавляющем большинстве случаев на практике требуется решение задачи реалистической визуализации, сбалансированное по скорости расчета и качеству изображения. На современном этапе этому критерию наиболее полно отвечает модель освещенности Виттеда, используемая в алгоритме обратной рекурсивной лучевой трассировки [72]

OP JIT), известном как light-backwards recursive ray tracing. OP JIT был введен Виттедом еще в 1980 г. и до сих пор в основном применяется на практике.

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

Анализ трехмерных сцен, используемых на практике, показывает, что они содержат лишь небольшое число полупрозрачных объектов, либо вовсе не содержат их. В этом несложно убедиться, если взять в качестве примера популярную компьютерную игру Quake [80] или анимационный фильм Shrek [81]. Это заставляет сосредоточить внимание на ускорении расчетов для сцен с непрозрачными объектами, и, как мы увидим, разработчики алгоритмов основное внимание уделяют обработке непрозрачных объектов. Тем не менее, стоит заметить, что алгоритмы, ориентированные на сцены, состоящие только из непрозрачных поверхностей, существенно ограничивают возможности пользователя.

В реалистической визуализации особое место занимает задача генерации теней в изображении трехмерной сцены. Почему исследователи уделяют ей так много внимания, (см. обзоры, посвященные теням, [48] и [74])? Исследования [48] подтверждают важность теней в восприятии трехмерной сцены: тени несут информацию об относительном положении объектов сцены и динамике его изменения, деталях геометрии затеняемого объекта и затеняющего объекта.

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

Мягкие тени можно получить в рамках модели Виттеда, если заменить объемный источник множеством точечных источников. Этот подход к генерации мягких теней назовем интегральным (например, он реализован как "Area shadows" в Autodesk 3ds Max), т.е. модель Виттеда не изменяется (источник остается точечным), но изменяется освещение в сцене (множество точечных источников вместо одного). Интегральный подход позволяет рассчитывать тени, корректные с точки зрения используемой модели освещения, но при этом требует очень больших вычислительных затрат: сотни и тысячи точечных источников, чтобы получить качественное изображение.

На практике часто требуется быстрый расчет изображения, пусть даже с некоторым нарушением реалистичности, т.е. точности геометрии теней. Это, прежде всего, относится к получению предварительных изображений при создании, например, трехмерного мультфильма. В таком случае дерево лучей, как правило, не строится, т.е. OPJIT заменяется нерекурсивной обратной лучевой трассировкой (OJIT), также этот алгоритм расчета часто называется ray casting, а модель освещенности называется локальной моделью освещенности с тенями. При этом достаточно имитировать мягкие тени, создавая иллюзию реалистичности, например, мультфильм Shrek [81]: тени в изображениях мягкие, и зрителю не важно, насколько точно они рассчитаны. Важно, чтобы зрительные ощущения удовлетворяли общим 5 представлениям о реализме: граница тени должна быть размытой, большие источники освещения дают более размытую тень, небольшие объекты дают малозаметные тени и т.д. Часто бывает достаточно лишь схематично обозначить тени, чтобы добиться нужного эффекта. Например, классический мультфильм Маугли студии Disney [82]: тени - это только темные пятна под каждым персонажем мультфильма, но для зрителя изображение достаточно правдоподобно.

Большинство алгоритмов генерации (имитации) мягких теней основано на алгоритме теневых карт (АТК) [73], предложенном Вильямсом в 1978 г., и алгоритме теневых объемов (АТО) [38], введенном Кроу в 1977 г. Насчитывается около 30 модификаций АТК и АТО, что подтверждает значимость этой задачи [16]. Анализ этих алгоритмов показал, что их область применения ограничена: они не работают с полупрозрачными поверхностями, не предназначены для рекурсивной лучевой трассировки, страдают от графических артефактов.

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

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

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

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

Достижение поставленной цели осуществляется за счет решения следующих задач:

1. Анализ существующих алгоритмов генерации мягких теней с точки зрения их практического применения в рамках модели освещенности Виттеда.

2. Анализ скоростных и качественных характеристик алгоритмов генерации мягких теней, основанных на алгоритме теневых карт и на алгоритме теневых объемов, в сравнении с методом световых сеток.

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

Основные научные положения, разработанные соискателем, и их новизна:

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

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

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

4. Впервые на основании исследования специфики расчета изображений по методу световых сеток разработаны три алгоритма его ускорения, с которыми расчет изображений занимает в среднем 0,35 — 0,5 от времени расчета по методу световых сеток без ускорений.

5. Разработаны алгоритмы ускорения расчета изображений по методу световых сеток за счет комплексирования метода световых сеток с алгоритмом теневых карт и алгоритмом теневых объемов. В зависимости от типа сцены расчет изображения при помощи гибрида метода световых сеток и алгоритма теневых карт занимает в среднем 0,28 - 0,4 от времени расчета с использованием метода световых сеток без ускорений. Гибрид метода световых сеток и алгоритма теневых объемов требует больше времени на расчет изображения: 0,3 — 0,45 от времени расчета с использованием неускоренного метода световых сеток в зависимости от типа сцены, но дает более точное решение.

На защиту выносятся следующие основные результаты:

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

2. Алгоритмы ускорения метода световых сеток, разработанные с учетом специфики расчетов по методу световых сеток.

3. Алгоритмы ускорения метода световых сеток за счет комплексирования метода световых сеток с алгоритмом теневых карт и алгоритмом теневых объемов.

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

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

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

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

Апробация работы. Результаты работы докладывались на XLIII международной научной студенческой конференции (Новосибирск, 2005), конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, 2005, 2008; Томск 2009), XV, XVII и XVIII международных конференциях по компьютерной графике и ее приложениям "Графикон" (Новосибирск, 2005; Москва, 2007, 2008), конференции молодых ученых ИВМиМГ (Новосибирск, 2006), IX всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2008).

Работа поддерживалась грантами РФФИ 06-07-89216а "Разработка алгоритмов физически корректной визуализации сцен с кристаллами", 08-07-12094офи "Разработка и создание прототипа программного продукта реалистической визуализации пространственных сцен, основанного на методе световых сеток".

Публикации. По теме диссертации опубликовано 10 работ, из них 1 по перечню ВАК Минобрнауки России.

Структура и объем работы. Диссертация общим объемом 126 страниц состоит из введения, 4 глав, заключения и списка литературы. В работе содержится 64 рисунка и 6 таблиц. Список литературы включает 84 наименования.

Основные результаты диссертационной работы:

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

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

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

4. Впервые на основании исследования специфики расчета изображений по методу световых сеток разработаны три алгоритма его ускорения, с которыми расчет изображений занимает в среднем 0,35 — 0,5 от времени расчета по методу световых сеток без ускорений.

5. Разработаны алгоритмы ускорения расчета изображений по методу световых сеток за счет комплексирования метода световых сеток с алгоритмом теневых карт и алгоритмом теневых объемов. В зависимости от типа сцены расчет изображения при помощи гибрида метода световых сеток и алгоритма теневых карт занимает в среднем 0,28 - 0,4 от времени расчета с использованием метода световых сеток без ускорений. Гибрид метода световых сеток и алгоритма теневых объемов требует больше времени на расчет изображения: 0,3 — 0,45 от времени расчета с использованием неускоренного метода световых сеток в зависимости от типа сцены, но дает более точное решение.

Благодарности

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

Заключение

Генерация мягких теней — актуальная задача, которой посвящено множество исследований. Чтобы определить текущее состояние этой области исследований, автором было изучено около 30 алгоритмов генерации мягких теней. Установлено, что большинство алгоритмов генерации теней основаны на двух известных алгоритмах: алгоритме теневых карт и алгоритме теневых объемов. Этот факт оказался очень полезен в исследовании многообразия алгоритмов генерации теней, поскольку все производные от АТК и АТО алгоритмы в большей или меньшей степени наследуют как преимущества, так и недостатки базовых методов. К преимуществам рассмотренных алгоритмов можно отнести то, что большинство из них было разработано для реализации на графическом ускорителе, который позволяет быстро рассчитывать изображения трехмерных сцен. С другой стороны, выявлено, что область применения большинства алгоритмов генерации мягких теней ограничена: они не работают с полупрозрачными поверхностями, не предназначены для рекурсивной лучевой трассировки, страдают от графических артефактов. Эти недостатки были теоретически обоснованы, экспериментально зафиксированы и проиллюстрированы как для базовых АТК и АТО, так и для производных от них алгоритмов генерации мягких теней. Поэтому можно заключить, что наилучшее применение для этих алгоритмов — быстрый предварительный расчет изображений, за которым следует расчет конечного изображения высокого качества с помощью более продвинутых алгоритмов.

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

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

1. Васильева Л.Ф., Дебелов В.А., Смирнова Г.Г. Расширение метода световых сеток для пространственных сцен с полупрозрачными поверхностями // Программирование - 2008. - Том 34, № 5. - С. 1-10.

2. Веселков С.Н. Разработка для 3D Studio модуля рендеринга сцен методом световых сеток // Выпускная квалификационная работа бакалавра НГУ, ФИТ Новосибирск, 2006.

3. Дебелов В.А., Севастьянов И.М. Оригинальный подход к имитации мягких теней и учету диффузных переотражений в лучевой трассировке // Тр. 11-й междунар. конфер. по компьютерной графике и машинному зрению Графикон'2001. — Нижний Новгород, 2001. С. 18— 24.

4. Дебелов В.А., Саттаров М.А. Проблемы реалистической визуализации кристаллов // Тр. 13-й междунар. конфер. по компьютерной графике и зрению Графикон'2003. -Москва, 2003. С. 221-227.

5. Дебелов В.А., Васильева Л.Ф., Смирнова Г.Г. Метод световых сеток для случая полупрозрачных поверхностей // Тр. 16-й междунар. конф. по компьютерной графике и машинному зрению Графикон'2006. — Новосибирск, 2006. С. 298-302.

6. Дебелов В.А., Новиков И.Е. Некоторые подходы к ускорению метода световых сеток // Тр. 17-й междунар. конфер. по компьютерной графике и ее приложениям Графикон'2007. — Москва, 2007. — С. 277— 284.

7. Дебелов В.А., Новиков И.Е. Генерация мягких теней при использовании алгоритма трассировки лучей // Вестник НГУ. Серия: Информационные Технологии. 2009. - Т. 7, № 2. - С. 18-41.

8. Ю.Елагин В.А. Экономия памяти при расчете изображений методом световых сеток // Матер, конференции-конкурса "Технологии Microsoft в теории и практике программирования". — Новосибирск, НГУ — 2008. С. 37-39.

9. И.Елагин В.А. Адаптация метода световых сеток для генерации мягких теней в 3ds Мах // Выпускная квалификационная работа бакалавра НГУ, ФИТ Новосибирск, 2008.

10. Новиков И.Е. Использование современного графического ускорителя для реализации метода световых сеток // Матер, конференции-конкурса "Технологии Microsoft в теории и практике программирования". — Новосибирск, НГУ 2005. - С. 57-59.

11. Новиков И.Е. Использование современного графического ускорителя для реализации метода световых сеток // Тр. XLIII Международной научной студенческой конференции "Студент и научно-технический прогресс". Новосибирск, НГУ - 2005. - С. 47-48.

12. И.Новиков И.Е. Обзор алгоритмов аппаратного ускорения метода лучевой трассировки // Proc. of 6th International Workshop on Virtual Environment on PC Cluster, VEonPC-2006, Protvino-Altai. Изд-во ИФТИ, Протвино. - 2006. - С. 22-30.

13. Новиков И.Е., Кочергин Н.А. Сравнение качественных и скоростных характеристик метода теневых карт и метода световых сеток // Матер, конференции-конкурса "Технологии Microsoft в теории и практике программирования". Новосибирск, НГУ - 2008. - С. 44-45.

14. Новиков И.Е. Сравнение двух алгоритмов генерации мягких теней // Программа и тез. докл. IX Всероссийской конф. молодых ученых по математическому моделированию и информационным технологиям. — Кемерово, 2008. Новосибирск, ИВТ СО РАН - 2008. - С. 87-88.

15. Эл. версия: http://www.nsc.ru/ws/YM2008/14366/Novikov.pdf.

16. Новиков И.Е. Ускорение метода световых сеток за счет комплексирования с алгоритмом теневых карт и алгоритмом теневых объемов — Новосибирск, 2009. 18 с. - (Препр. / РАН. Сиб. отд-е ИВМиМГ; № 1167).

17. Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир. — 1989.

18. Смирнова Г.Г. Развитие метода световых сеток для сцен с полупрозрачными поверхностями с учётом преломления теневых лучей // Матер, конференции-конкурса "Технологии Microsoft в теории и практике программирования". Новосибирск, НГУ - 2008. — С. 50-51.

19. Adinetz A.V., Berezin S.B. Implementing Classical Ray Tracing on GPU — a Case Study of GPU Programming // Тр. 16-й междунар. конфер. по компьютерной графике и ее приложениям ГрафиКон'2006. — Новосибирск, 2006. С. 1-7.

20. Adinetz A., Barladian В., Galaktionov V., Kopylov Е., Shapiro L., Voloboy A. Physically Accurate Rendering with Coherent Ray Tracing // Тр. 16-й междунар. конфер. по компьютерной графике и ее приложениям ГрафиКон'2006. Новосибирск, 2006. - С. 8-15.

21. AgrawaIa M., Ramamoorthi R., Heirich A., Moll L. Efficient image-based methods for rendering soft shadows. // Proc. of SIGGRAPH'OO. 2000. -P. 375-384.

22. Amanatides J., Woo A. A Fast Voxel Traversal Algorithm for Ray Tracing // Proc. of Eurographics'87. 1987. - P. 3-10.

23. Appel A. Some techniques for shading machine renderings of solids. // Proc. of the Spring Joint Computer Conference. — 1968. — P. 37-45.

24. Arvo J., Westerholm J. Hardware Accelerated Soft Shadows using Penumbra Quads // Proc. of WSCG'04. Plzen, Czech Republic. - 2004. -Vol. 12, № l.P. 11-18.

25. Atty L., Holzschuch N., Lapierre M., Hasenfratz J.-M., Hansen C., Sillion F. Soft shadow maps: Efficient sampling of light source visibility. // Computer Graphics Forum. 2006. - Vol. 25, №4-P. 725-741.

26. Assarsson U., Akenine-Moller T. A geometry-based soft shadow volume algorithm using graphics hardware. // ACM Transactions on Graphics. -2003. Vol. 22, № 3. - P. 511-520.

27. Blinn J.F. Models of Light Reflection for Computer Synthesized Pictures. // Computer Graphics. SIGGRAPH, ACM - 1977. - P. 192-198.

28. ВгаЬес S., Seidel H.-P. Hardware-accelerated Rendering of Antialiased Shadows with Shadow Maps // Proc. of CGI'01. Hong Kong, China. -2001.-P. 209-214.

29. Brabec S., Annen Т., Seidel H.-P. Shadow Mapping for Hemispherical and Omnidirectional Light Sources // Proc. of CGI'02. Bradford, UK. - 2002. -P. 397—408.

30. Brabec S., Seidel H.-P. Single Sample Soft Shadows Using Depth Maps // Proc. Graphics Interface. Calgary, Alberta, 2002. - P. 219-228.

31. Brabec S., Seidel H.-P. Shadow Volumes on Programmable Graphics Hardware // Proc. of Eurographics'03. 2003. - Vol. 22, № 3. - P. 433-440.

32. Brabec S. Shadow Techniques for Interactive and Real-Time Applications. PhD thesis, Max-Planck-Institut fur Informatik Saarbriicken, 2003.

33. Chan E., Durand F. Rendering fake soft shadows with smoothies // Proc. 14th Eurographics Symposium on Rendering. — 2003. P. 208-218.

34. Chan E., Durand F. An efficient hybrid shadow rendering algorithm // Proc. 15th Eurographics Workshop on Rendering (Rendering Techniques'04). — 2004.-P. 185-196.

35. Cohen M.F., Wallace J.R. Radiosity and Realistic Image Synthesis / Academic Press. — New York. 1993.

36. Crow F. Shadow Algorithms for Computer Graphics // Computer Graphics. 1977. - Vol. 11, № 2. - P. 242-247.

37. Debelov V.A., Sevastyanov I.M. Light Meshes Original Approach to Produce Soft Shadows in Ray Tracing // Lecture Notes in Computer Science. - Springer-Verlag. - 2002. - Vol. 2330. - P. 13-21.

38. Debelov V.A., Sevastyanov I.M. Soft shadows as interpolation of visibility // Future Generation Computer Systems. 2004. - Vol. 20, № 8. - P. 12991315.

39. Drettakis G., Fiume E. A fast shadow algorithm for area light sources using backprojection. // Computer Graphics. SIGGRAPH, ACM - 1994. -P. 223-230.

40. Glassner A.S. Space Subdivision For Fast Ray Tracing / IEEE Computer Graphics & Applications. 1984. - Vol. 4, № 10. - P. 15-22.

41. Guennebaud G., Barthe L., Paulin M. Real-time soft shadow mapping by backprojection. // Proc. of Eurographics Symposium on Rendering. 2006. -P. 227-234.

42. Guennebaud G., Barthe L., Paulin M. High-Quality Adaptive Soft Shadow Mapping. // Computer graphics forum. 2007. - Vol. 26, № 3. - P. 525-533.

43. Haines E. Soft Planar Shadows Using Plateaus // J. of Graphics' Tools. -2001.-Vol. 6,№ l.-p. 19-27.

44. Hasenfratz J.-M., Lapierre M., Holzschuch N., Sillion F. A survey of realtime soft shadows algorithms // Eurographics'03 State-of-The-Art Reports. — 2003.-P. 1-20.

45. Havran V., Herzog R., Seidel H.-P. On the Fast Construction of Spatial Hierarchies for Ray Tracing // Proc.,of IEEE Symposium on Interactive Ray Tracing. 2006. - P. 71-80.

46. Heckbert P.S., Herf M. Simulating soft shadows with graphics hardware. Technical Report CMU-CS-97-104, Carnegie Mellon University, 1997.

47. Heidrich W., Brabec S., Seidel H.-P. Soft Shadow Maps for Linear Lights // 11th Eurographics Workshop on Rendering. 2000. - P. 269-280.

48. Herf M. Efficient generation of soft shadow textures. Technical Report CMU-CS-97-138, Carnegie Mellon University, 1997.

49. Keating В., Max N.' Shadow penumbras for complex objects by depth-dependent filtering of multilayer depth images. // 10th Eurographics Workshop on Rendering. Springer-Verlag, 1999. - P. 205-220.

50. Kirsch F., Doellner J. Real-time soft shadows using a single light sample. // WSCG'03. -2003. Vol. 11, № 2. -P.J 255-262.

51. Laine S., Aila Т., Assarsson U., Lehtinen J., Akenine-Moller T. Soft Shadow Volumes for Ray Tracing. // SIGGRAPH, ACM. 2005 - Vol. 24, № 3. -P.1156-1165.

52. Loscos C., Drettakis G. Interactive high-quality soft shadows in scenes with moving objects. // Computer Graphics Forum, Eurographics. 1997. -Vol. 16, №3.-P. 219-230.

53. Pharr M., Kolb С., Gershbein R., Hanrahan P. Rendering complex scenes with memory-coherent ray tracing. // Computer/ Graphics (Proc. of SIGGRAPH). 1997. - Vol. 31. - P. 101-108.

54. Purcell' T.J., Donner G„ Cammarano M., Wann Jensen H.,. Hanrahan P. Photon mapping on programmable graphics hardware. // Proc. of the ACM SIGGRAPH/EUROGRAPHICS 2003. - P. 41-50.

55. Purcell T.J. Ray Tracing- om a- Stream Processor. PhD thesis, Stanford University, 2004.64lSchmittler JC, Wald Ii, Slusallek P. Saar-C0R A Hardware v^rchitecture for• Ray Tracing.//Proc: ofGraphics Hardware.-2002.-P. 27-36.

56. Schmittler J., Leidinger A., Slusallek P. A Virtual Memory Architecture for Real-Time Ray Tracing Hardware. // Computer & Graphics. — 2003. — Vol. 27.-P: 693-699: ;

57. Schmittler J., Woop S., Wagner D., Paul W. J., Slusallek P. Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip. // Proc. of Graphics Hardware. 2004. - P. 95-106.

58. Schwarz M., Stamminger M. Bitmask Soft Shadows // Proc. of Eurographics Symposium on Rendering. ,- 2007. — Vol. 26, № 3; P; 515-524.

59. Soler C., Sillion F.X. Fast calculation of soft shadow textures using convolution.//SIGGIIAPHI ACMi -1998;-P: 321-33Z

60. St-Amour J.-F., Paquette E., Poulin P. Soft Shadows from Extended Light Sources with Penumbra Deep Shadow Maps. // Proc. of Graphics Interface. -2005.-P. 105-112.

61. Wald I., Benthin C., Wagner M., Slusallek P. Interactive rendering with coherent ray tracing. // Proc. of Eurographics. — 2001. — Vol. 20, № 3. — P. 153-165.

62. Wald I., Slusallek P. State-of-the-Art in Interactive Ray Tracing // Proc. of Eurographics. 2001. - P. 21-42.

63. Whitted T. An Improved Illumination Model for Shaded Display / Commun. ACM. 1980. - Vol. 23, № 6. - P. 343-349.73 .Williams L., Casting curved shadows on curved surfaces // Computer Graphics. 1978. - Vol. 10, № 2. - P. 270-274.

64. Woo A., Poulin P., Fournier A. A survey of shadow algorithms // IEEE Computer Graphics and Applications. 1990. - Vol. 10, № 6. - P. 13-32.

65. Woop S., Schmittler J., Slusallek P. RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing // SIGGRAPH, ACM. 2005. - P. 434-444.

66. Wyman C., Hansen C. Penumbra maps: Approximate soft shadows in realtime // Proc. of 14th Eurographics Symposium on Rendering. 2003. -P. 202-207.

67. Ying Z., Tang M., and Dong J. Soft shadow maps for area light by area approximation. // Proc. of 10th Pacific Conference on Computer Graphics and Applications. 2002. - P. 442-443.78.0penGL — http://www.sgi.com/products/software/opengl/.

68. Microsoft DirectX http://msdn.microsoft.com/en-us/directx/default.aspx.80.id Software: Quake http://www.idsoftware.com/games/quake/.81 .DreamWorks Animation: Shrek http://shrek.com.

69. Walt Disney Studios: The jungle book — http://disney.go.com/disneyvideos/ anim ate dfi lms/i un gleb ook/.

70. VRML-97 The Virtual Reality Modeling Language -http://www.web3d.org/x3d/specifications/vrml/lSO-IEC-14772-VRML97/.

71. Autodesk 3ds Max — http://www.autodesk.com/3dsmax.