Введение к работе
Актуальность работы. Область практического применения реалистической компьютерной графики в наши дни необычайно широка, она включает в себя киноиндустрию, рекламу, дизайн, компьютерные игры, системы виртуальной реальности, научную визуализацию и т.д. Заметим, что в каждой из перечисленных областей свои требования к степени реализма. Стремительное увеличение числа продуктов компьютерной графики и вовлечение их в повседневную жизнь вызывает ответную реакцию потребителя, заключающуюся в непрерывном повышении требований к этим продуктам. И хотя рост вычислительных мощностей позволяет решать все более сложные задачи визуализации трехмерных сцен (число объектов, источников освещения, разрешение изображения), рост сложности самих задач опережает его.
Существуют разные математические модели освещенности сцены, на основе которых строится изображение трехмерной сцены. Выбор конкретной модели для применения на практике зависит от цели, для которой создается изображение. Например, для компьютерных игр высокая скорость расчета изображения приоритетнее высокого качества изображения, недостаток качества часто компенсируется высокой динамикой видеоряда. В этой области применяется локальная модель освещенности, которая используется в алгоритме сканирующей строки (OpenGL и DirectX). Если высокое качество изображения и физическая корректность приоритетнее скорости расчета, подходящей моделью является глобальная модель освещенности, которая используется в таких вычислительно трудоемких алгоритмах, как излучательность и методы Монте-Карло. Но в подавляющем большинстве случаев на практике требуется решение задачи реалистической визуализации, сбалансированное по скорости расчета и качеству изображения. На современном этапе этому критерию наиболее полно отвечает модель освещенности Виттеда, используемая в алгоритме обратной рекурсивной лучевой трассировки (ОРЛТ), известном как light-backwards recursive ray tracing, который был введен Виттедом еще в 1980 г. и до сих пор, в основном, применяется на практике.
Практическое применение ОРЛТ связано с большими вычислительными затратами, иначе говоря, время на расчет изображения по ОРЛТ может быть очень велико. Поэтому любое ускорение расчетов по ОРЛТ является существенным.
Анализ трехмерных сцен, используемых на практике, показывает, что они содержат лишь небольшое число полупрозрачных объектов, либо вовсе не содержат их. Тем не менее, стоит заметить, что алгоритмы, ориентированные на сцены, состоящие только из непрозрачных поверхностей, существенно ограничивают возможности пользователя.
В реалистической визуализации особое место занимает задача генерации теней в изображении трехмерной сцены. Исследования подтверждают важность теней в восприятии трехмерной сцены: тени несут информацию об относительном положении объектов сцены и динамике его изменения, деталях геометрии затеняемого объекта и затеняющего объекта. Четкие тени часто порождают фантомы, т.е. иллюзию того, что тень является отдельным объектом сцены или ри-
сунком на поверхности объекта. Мягкие тени не только повышают реалистичность изображения, но также несут дополнительную информацию: размеры и конфигурация источника, взаимное расположение источника, затеняющего и затеняемого объектов. Заметим, что выражение "генерация теней" обобщает два разных понятия: "расчет теней" и "имитация теней".
На практике часто требуется быстрый расчет изображения, пусть даже с некоторым нарушением реалистичности, т.е. точности геометрии теней. Например, при получении предварительных изображений при создании мультфильма. В таком случае дерево лучей, как правило, не строится, т.е. ОРЛТ заменяется нерекурсивной обратной лучевой трассировкой (ОЛТ или ray casting), а модель освещенности называется локальной моделью освещенности с тенями. При этом достаточно имитировать мягкие тени, создавая иллюзию реалистичности. Например, мультфильм Shrek: тени в изображениях мягкие, и зрителю не важно, насколько точно они рассчитаны. Важно, чтобы зрительные ощущения удовлетворяли общим представлениям о реализме: граница тени должна быть размытой (отсутствие фантомов), большие источники освещения дают более размытую тень, небольшие объекты дают малозаметные тени и т.д. Часто бывает достаточно схематично обозначить тени, чтобы добиться нужного эффекта.
Большинство алгоритмов генерации (имитации) мягких теней основано на алгоритме теневых карт (АТК), предложенном Вильямсом в 1978 г., и алгоритме теневых объемов (АТО), введенном Кроу в 1977 г. Как правило, эти алгоритмы, обеспечивающие быстрый расчет изображений, подходят только для получения предварительных/черновых изображений. Генерация мягких теней в рамках рекурсивного ОРЛТ остается практически не исследованной на предмет ускорения расчетов, которое позволило бы получать качественное изображение за приемлемое время. На практике для создания конечного изображения используется подход аналогичный "Area shadows" в Autodesk 3ds Мах, который назовем интегральным.
Метод световых сеток (МСС), который является модификацией ОРЛТ, впервые предложен в 2001 г. и был разработан, чтобы не только решить задачу создания качественного изображения, содержащего мягкие тени и свободного от артефактов, но, в отличие от других алгоритмов, решить ее в рекурсивной лучевой модели, а также обеспечить решение задачи визуализации для сцен, содержащих полупрозрачные поверхности. Таким образом, исследование МСС, а также разработка алгоритмов ускорения расчета изображения являются современной актуальной задачей.
Объектом исследования данной работы являются алгоритмы реалистической визуализации в рамках модели освещенности Виттеда, позволяющие вместо четких теней генерировать мягкие тени от точечных источников освещения в изображении трехмерной пространственной сцены.
Целью данной работы является изучение алгоритмов генерации мягких теней с точки зрения применимости к модели освещенности Виттеда, исследование их скоростных характеристик и качества получаемых изображений, определение места метода световых сеток среди других алгоритмов схожей функцио-
нальности, разработка алгоритмов ускорения расчета изображений трехмерных сцен по методу световых сеток.
Для достижения поставленной цели необходимо решить следующие задачи:
Анализ существующих алгоритмов генерации мягких теней с точки зрения их практического применения в рамках модели освещенности Виттеда.
Анализ скоростных и качественных характеристик алгоритмов генерации мягких теней, основанных на алгоритме теневых карт и на алгоритме теневых объемов, в сравнении с методом световых сеток.
Исследование и разработка алгоритмов ускорения расчета изображений трехмерных сцен по методу световых сеток.
Основные научные положения, разработанные соискателем, и их новизна:
Впервые проведено сравнение и даны качественные оценки для метода световых сеток и других алгоритмов генерации мягких теней по скорости расчета и качеству получаемого изображения, которые были подтверждены экспериментально.
Определено место метода световых сеток в многообразии алгоритмов генерации мягких теней. Показано, что метод световых сеток имеет более широкую область практического применения в сравнении с другими алгоритмами генерации мягких теней.
Теоретически показано и экспериментально подтверждено, что с увеличением сложности задачи визуализации трехмерных сцен (число объектов, источников освещения, разрешение изображения) время расчета изображения по методу световых сеток растет медленнее, чем для алгоритма Виттеда, и асимптотически метод световых сеток показывает лучшие результаты по скорости расчета.
Впервые на основании исследования специфики расчета изображений по методу световых сеток разработаны три алгоритма его ускорения.
Разработаны алгоритмы ускорения расчета изображений по методу световых сеток за счет комплексирования метода световых сеток с алгоритмом теневых карт и алгоритмом теневых объемов.
На защиту выносятся следующие основные результаты:
Теоретическая оценка вычислительных затрат на расчет изображения в рамках модели освещенности Виттеда при помощи алгоритма обратной рекурсивной лучевой трассировки и метода световых сеток.
Алгоритмы ускорения метода световых сеток, разработанные с учетом специфики расчетов по методу световых сеток.
Алгоритмы ускорения метода световых сеток за счет комплексирования метода световых сеток с алгоритмами теневых карт и теневых объемов.
Научная значимость работы заключается в определении места метода световых сеток среди других алгоритмов схожей функциональности, в алгоритмах ускорения расчета изображений трехмерных сцен по методу световых сеток.
Достоверность научных положений, сформулированных в диссертации, подтверждается численными экспериментами, проведенными для трехмерных сцен различной конфигурации и сложности, а также сравнением результирующих изображений с изображениями, полученными с использованием других алгоритмов генерации теней.
Методы исследований. В работе использовались методы вычислительной геометрии, вычислительной математики и компьютерной графики.
Практическая значимость работы. Разработан программный комплекс, позволяющий рассчитывать изображения при помощи классического алгоритма Виттеда, а также метода световых сеток с возможностью использования любого из разработанных алгоритмов ускорения или их комбинации. В любое программное средство, осуществляющее расчет изображения по какому-либо алгоритму, построенному на базе алгоритма Виттеда, может быть добавлен модуль, разработанный на основе метода световых сеток и включающий в себя предложенные алгоритмы ускорения.
Апробация работы. Результаты работы докладывались на 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 наименования.
