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

• Новиков, Илья Евгеньевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Новиков, Илья Евгеньевич

Введение.

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

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

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

Список литературы диссертационного исследования кандидат технических наук Новиков, Илья Евгеньевич, 2009 год

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.