Методы и алгоритмы эффективного вычисления освещенности трехмерных виртуальных сцен в реальном режиме времени тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Мальцев, Андрей Валерьевич

• Мальцев, Андрей Валерьевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Мальцев, Андрей Валерьевич

Введение.

Актуальность темы.

Цели и задачи работы.

Методы исследований.1.

Результаты работы, выносимые на защиту.

Практическая ценность работы.

Апробация работы.

Публикации.

Структура работы.

Глава 1. Обзор существующих технологий и методов расчета реалистичной освещенности виртуальных сцен.

1.1. Технологии синтеза изображений трехмерных сцен.

1.2. Вычисление освещенности виртуальных объектов трехмерных сцен с помощью шейдерной обработки.

1.3. Методы расчета высокореалистичной освещенности виртуальных объектов трехмерных сцен.

1.4. Трассировка лучей.

1.4.1. Прямая и обратная трассировка.

1.4.2. Структуры ускорения трассировки и их виды.

1.4.3. Способы реализации трассировки лучей.

1.5. Выводы.

Глава 2. Совмещенная визуализация виртуальных сцен.

2.1. Метод совмещенной визуализации виртуальных сцен.

2.2. Критерии разделения объектов сцены на группы с разными типами визуализации.

2.3. Шейдерная обработка и метод статической оптимизации.

2.3.1. Стандартный графический конвейер визуализации виртуальных сцен.

2.3.2. Шейдерная модель визуализации виртуальных сцен.

2.3.3. Метод статической оптимизации шейдерных программ.

2.4. Трассировка лучей на графическом процессоре.

2.5. Выводы.

Глава 3. Моделирование освещенности на основе шейдерной обработки.

3.1. Модель Фонга-Блина расчета освещенности.

3.2. Расширенная модель расчета освещенности.

3.2.1. Моделирование направленных источников освещения.

3.2.2. Расчет освещенности с учетом теней от объектов.

3.3. Повышение реалистичности изображений с помощью попиксельного расчета освещенности.

3.3.1. Моделирование теней от направленных источников света.

3.3.2. Моделирование теней от всенаправленных источников света.

3.3.3. Микрорельеф поверхностей объектов.

3.3.4. Моделирование отражений от поверхностей объектов.

3.3.5. Моделирование прозрачности объектов.

3.4. Выводы.

Глава 4. Моделирование реалистичной освещенности методом трассировки лучей.

4.1. Модель вычисления освещенности Уиттеда.

4.2. Трассировка первичных лучей с помощью цветовых карт.

4.3. Совмещенная визуализация виртуальных сцен с использованием цветовых карт

4.4. Построение адаптивной регулярной сетки сцены.

4.4.1. Этапы формирования регулярной сетки для трехмерной сцены.

4.4.2. Алгоритм построения и заполнения регулярной сетки сцены.

4.5. Трассировка вторичных лучей с помощью ускоряющей структуры.

4.6. Выводы.

Глава 5. Экспериментальные результаты на основе системы визуализации ОЬУ1еу/.

5.1. Система визуализации

5.2. Интеграция разработанных решений в ОГЛ^елу.

5.3. Тестирование предложенных методов и алгоритмов.

5.3.1. Статические сцены.

5.3.2. Динамические сцены.

5.4. Выводы.

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

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

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

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

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

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

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

В зависимости от целей и задач, для которых визуализируется трехмерная сцена, выделяют различные типы визуализации. По критерию качества синтезируемого изображения, например, можно выделить обычную, высокореалистичную и фотореалистичную визуализации. Под обычной визуализацией можно понимать такую визуализацию трехмерной сцены, при которой виртуальные объекты, моделирующие некоторые реальные, изображаются упрощенно, порой даже схематически. Высокореалистичная визуализация отличается большой степенью схожести с реальностью. Фотореалистичный рендеринг предполагает синтез изображений, эквивалентных тем, что можно получить, например, путем фотографирования тех или иных объектов реального мира. Также визуализацию можно охарактеризовать частотой смены кадров изображения. Обычно она измеряется в FPS (frames per second, кадры в секунду). Если частота смены кадров больше или равна 25 FPS, то такой рендеринг часто называют визуализацией в реальном реэюиме времени. В этом случае перемещение объектов на экране происходит плавно и выглядит реалистично. При частоте 5-10 FPS и выше возможен интерактивный режим, при котором человек может изменять некоторым образом характеристики объектов сцены и взаимодействовать с этими объектами непосредственно в ходе визуализации, за приемлемое время получая на экране результаты внесенных изменений и взаимодействий. При частоте ниже 5 FPS объекты на экране движутся рывками, динамика выглядит неестественно, поэтому такая визуализация используется в более узком кругу задач, в основном, когда результаты рендеринга просматриваются после его завершения, а не в самом его процессе.

Высокореалистичная визуализация высокополигональных динамических трехмерных сцен в реальном режиме времени является одним из наиболее сложных типов рендеринга, поскольку подразумевает выполнение вычислительно сложных алгоритмов анализа и обработки графической информации за короткий промежуток времени (при частоте смены кадров 25 РРЭ он составляет не более 1/25 = 0.04 с). До недавних пор осуществление такой визуализации на персональном компьютере (ПК) не представлялось возможным. Однако с развитием вычислительной техники и совершенствованием ПК это направление стало предметом исследований специалистов в области компьютерной графики и анимации во всем мире. В данной' работе основное внимание также будет уделено рассмотрению методов и алгоритмов-данного типа рендеринга.

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

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

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

В настоящее время мировым научным сообществом активно исследуется вопрос реализации эффективного расчета высокореалистичной освещенности трехмерных виртуальных сцен в реальном режиме времени. Постоянно создаются новые методы и алгоритмы обработки и визуализации графической информации. И в России, и за рубежом одним из молодых и бурно развивающихся направлений является использование технологии параллельных вычислений на графических процессорах (GPU) видеоадаптеров. Это, в первую очередь, связано с тем, что задачи расчета освещенности виртуальных объектов являются достаточно хорошо распараллеливаемыми. Для выполнения таких вычислений на GPU используют шейдеры и программно-аппаратную архитектуру параллельных вычислений CUDA (Compute Unified Device Architecture). Данная архитектура является новейшей разработкой компании NVIDIA и представляет собой прогрессивный метод параллельной обработки информации на персональном компьютере. Она позволяет производить вычисления общего назначения на многоядерных графических процессорах без привязки к структуре графического конвейера, что способствует повышению эффективности выполнения расчетов на GPU (в том числе расчетов высокореалистичной освещенности).

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

Актуальность темы

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

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

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

Цели и задачи работы

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

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

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

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

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

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

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

Методы исследований

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

Достоверность научных положений, сформулированных в диссертации, подтверждается корректным использованием математического аппарата и методов системного анализа, сопоставимостью теоретических и экспериментальных результатов обработки графической информации, а также положительными результатами апробации и тестирования предложенных технологий, методов и алгоритмов в системе визуализации для реального тренажерного комплекса в ФГБУ «Научно-исследовательский испытательный центр подготовки космонавтов имени Ю.А. Гагарина».

Научная новизна работы заключается в следующем:

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

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

Разработан новый метод цветовых карт для ускорения процесса обработки графической информации при выполнении расчета освещенности виртуальных объектов путем трассировки первичных лучей. Установлено, что данный метод ускоряет трассировку первичных лучей в среднем на 52% по сравнению с другими известными методами. Также созданы новые методы и алгоритмы трассировки вторичных лучей, включающие эффективное построение и заполнение регулярной сетки для динамических виртуальных сцен в реальном режиме времени на графическом процессоре (ОРи) и трассировку лучей с использованием данной сетки также на ОРи.

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

Результаты работы, выносимые на защиту

На защиту диссертации выносятся следующие результаты, полученные в ходе выполнения данной работы:

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

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

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

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

Практическая ценность работы

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

Апробация работы

Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на: • □ Международной молодежной научной конференции "XXXVII Гагаринские чтения" (г. Москва, 2011) ;

2-ой международной конференции "Системный анализ и информационные технологии" (г. Обнинск, 2007);

VII международной научно-практической конференции "Пилотируемые полеты в космос" (Звездный городок, 2007);

Научной конференции, посвященной 45-летию выхода человека в космос (Москва, 2006);

Научных семинарах Центра визуализации и спутниковых информационных технологий НИИСИ РАН. ’

Разработанные программные модули прошли апробацию в ФГБУ «Научноисследовательский испытательный центр подготовки космонавтов имени Ю.А. Гагарина» и показали свое соответствие требованиям, предъявляемым в настоящее время к системам визуализации проблемно-ориентированных трехмерных виртуальных сцен.

Публикации

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

Структура работы

Работа состоит из введения, пяти глав, заключения и списка литературы. В работе содержится 76 рисунков и 11 таблиц. Список литературы включает 62 наименования.

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

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

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

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

Для ускорения процесса обработки графической информации при расчете освещенности виртуальных объектов путем трассировки вторичных лучей описываются новые методы и алгоритмы эффективного построения; заполнения и использования структуры ускорения на основе регулярной сетки сцены. Предлагаемые решения ориентированы на применение параллельных вычислений на графических процессорах компании 1ЧУГО1А с поддержкой программно-аппаратной архитектуры •- С1ГОА и позволяют осуществлять построение, заполнение и использование регулярных сеток высокополигональных динамических трехмерных виртуальных сцен в реальном режиме времени.

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Мальцев, Андрей Валерьевич

5.4. Выводы

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

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

В результате проведения эксперимента было установлено (п. 5.3.1), что применение цветовых карт, описанных в п. 4.2, позволяет получить прирост скорости вычисления высокореалистичной освещенности путем трассировки первичных лучей в среднем на 52,1% по сравнению с классическим вариантом трассировки, что обосновывает целесообразность и эффективность использования данного метода. Кроме того, как выяснилось в ходе тестирования, алгоритм построения и заполнения ускоряющей структуры на основе регулярной сетки, предложенный в п. 4.2.2, выполняется в реальном режиме времени даже для высокополигональных динамических сцен с количеством полигонов порядка 106.

Заключение

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

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

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

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

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

CUD А). Предложенный метод повышает скорость и эффективность трассировки первичных лучей в среднем на 52.1%.

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

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

Материалы диссертации были опубликованы в 13 печатных работах [36, 37, 45-55]. Полученные результаты диссертационной работы докладывались, обсуждались и получили одобрение специалистов на 3-х международных научных конференциях, а также на научных семинарах Центра визуализации и спутниковых информационных технологий НИИСИ РАН. Созданные в процессе выполнения работы программные модули прошли апробацию на тренажерном комплексе в ФГБУ «Научно-исследовательский испытательный центр подготовки космонавтов имени Ю.А. Гагарина» и показали свое соответствие требованиям, предъявляемым в настоящее время к системам визуализации трехмерных виртуальных сцен для имитационно-тренажерных комплексов.

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

1. Whitted Т. An Improved Illumination Model for Shaded Display // Comm. ACM. 1980.- June. Vol. 23, no. 6. - Pp. 343-349.

2. Goral С. М., Torrance К. E., Greenberg D. P., Battaile B. Modeling the Interaction of Light Between Diffuse Surfaces // Computer Graphics. — 1984. Vol. 18, no. 3. - Pp. 213-222.

3. Radiosity (3D computer graphics). -http://www.en.wikipedia.org/wiki/Radiosity (3D'computer graphics).

4. Jensen H. W, Christensen N. J. Photon maps in Bidirectional Monte Carlo Ray Tracing of Complex Objects'// Computers & Graphics. 1995. - Vol. 19 (2). - Pp. 215-224.

5. Jensen H. W. Global illumination using photon maps // Rendering Techniques '96, Proceedings of the Seventh Eurographics Workshop on.Rendering. Springer Verlag, 1996.-Pp. 21-30.

6. Christensen N. J., Jensen H.W. A Practical Guide to Global illumination and Photon Maps // SIGGRAPH. 2000. - July 23. - Course notes #8.

7. Goldsmith J., Salmon J. Automatic creation of object hierarchies for ray tracing // IEEE Computer Graphics and Applications. 1987. - May. - Vol. 7, no. 5. - Pp. 14-20.

8. Havran V. Heuristic Ray Shooting Algorithms. Ph.D. dissertation, Czech Technical University, Czech Republic, 2000. — November. -http://dcgi.felk.cvut.cz/home/havran/DISSVH/dissvh.pdf

9. Тотмаков А. С. Оптимизация доступа к пространственным данным // Электронный журнал "Исследовано в России". -2005. С. 1751-1759. -http://zhurnal.gpi.ru/articles/2005/168.pdf

10. Lauterbach С., Garland М., Sengupta S., Luebke D., Manocha D. Fast BVH Construction on GPUs // Computer Graphics Forum. 2009. April. - Vol. 28, no. 2. — Pp. 375-384.

11. Torres R., Martin P.J., Gavilanes A. Ray Casting using a Roped BVH with CUD A // In 25th Spring Conference on Computer Graphics (SCCG 2009). Budmerice, Slovakia,2009.-April.-Pp. 107-114.

12. Yl.Aila Т., Laine S. Understanding the Efficiency of Ray Traversal on GPUs // In Proceedings of High-Performance Graphics. New York, NY, USA: ACM, 2009. - Pp. 145-150.

13. Fujimoto A., Tanaka Т., Iwata K. ARTS: Accelerated ray tracing system // IEEE Computer Graphics and Applications. 1986. — Vol. 6, no. 4. — Pp. 16-26.

14. Турлапов B.E., Боголепов Д. К, Трушанин B.C. Интерактивная трассировка лучей на графическом процессоре // Труды 19 международной конференции по компьютерной графике и ее приложениям (GraphiCon1 2009). — 2009. С. 263-266.

15. Purcell Т. J. Ray Tracing on a Stream Processor. Ph.D. Dissertation, Stanford University, USA, 2004. - March.http://graphics.stanford.edu/papers/tpurcellthesis/tpurcellthesis.pdf

16. Gigante M. Accelerated ray tracing using non-uniform grids // In Proceedings of Ausgraph ’90. 1988. - Pp. 157-163.

17. Havran V, Sixta F. Comparison of hierarchical grids // Ray Tracing News. 1999.1. June.-Vol. 12, no. 1. '

18. Kaplan M. Space-Tracing: A Constant Time Ray-Tracer // In Proceedings of SIGGRAPH ’85.- 1985.-July.-Pp. 149-158.

19. Ize Т., Wald I., Parker S. G. Ray tracing with the BSP tree // 2008 IEEE Symposium on Interactive Ray Tracing. Los Angeles, CA, USA, 2008.

20. Havran V, Bittner J. On improving kd-trees for ray shooting // Journal of WSCG. -2002;-February.-Vol. 10, no. 1,—Pp. 209-216.

21. MacDonald J. D., Booth K. S. Heuristics for Ray Tracing using Space Subdivision // The Visual Computer. 1990. - Vol. 6, no. 3. - Pp. 153-166.

22. Фролов В., Игнатенко А. Интерактивная трассировка лучей и фотонные карты на GPU // Труды конференции ГрафиКон'2009. Москва, Россия, 2009. - С. 255-262.

23. Popov S., Gunther J., Seidel H.-P., Slusallek P. Stackless KD-Tree Traversal for High Performance GPU Ray Tracing // In Proceedings of the EUROGRAPHICS conference. -2007. Vol. 26, no. 3. - Pp. 415-424.

24. Zhou K., Hou Q„ Wang JR., Guo B. Real-time KD-tree construction on graphics hardware // In Proc. of SIGGRAPH Asia '08. New York, NY, USA: ACM, 2008. - Pp. 1-11.

25. Glassner A. S. Space subdivision for fast ray tracing // IEEE Computer Graphics and Applications. 1984.— October.-Vol. 4, no. 10.-Pp. 15-22.

26. Havran V A summary of octree ray traversal algorithms // Ray Tracing News. 1999. -December. - Vol. 12, no. 2. .

27. Romisch K. Sparse Voxel Octree Ray Tracing on the GPU. Master's Thesis, Department of Computer Science Aarhus University, Denmark, 2009. - September. -http://www.daimi.au.dk/~aquak/MasterThesisKristofRoemisch.pdf

28. Benthin C. Realtime Ray Tracing on Current CPU Architectures. PhD Thesis, Saarland University, Germany, 2006. - January. - http://deposit.ddb.de/cgi-bin/dokserv?idn=982160763&dokvar=dl &dokext=pdf&filename=982160763 .pdf

29. Govindaraju V, Djeu P., Sankaralingam K, Vernon М., Mark W. R. Toward a Multicore Architecture for Real-time Ray-tracing // In- Proceedings of the- 41st IEEE/ACM International Symposium on.Microarchitecture. — 2009. Pp. 176-187.

30. Adinetz A., Berezin S. Implementing Classical Ray Tracing on GPU a Case. Study* of GPU Programming // Proceedings.of Graphicon. - 2006.

31. Челноков Ф. Персональный суперкомпьютер. //Компьютерра. — 2006. -№13.

32. Михайлюк М.В. Основы компьютерной графики. Учебное пособие. М.: МИРЭА, 2002. . .

33. Framebuffer Object или скажем "нет" оконным контекстам. — http://www.gamedev.ru/community/opengl/articles/framebufferobject

34. Мальцев А.В., Михайлюк М.В. Моделирование отражений окружающей среды для виртуальных объектов в реальном режиме времени // Программные продукты и системы. 2007. -№ 3. - С. 31-35.

35. De Greve В. Reflections and Refractions in Ray Tracing. - 'http://www.bramz.net/data/writings/reflectiontransmission.pdf

36. Buss S. R. 3D Computer Graphics. A Mathematical Introduction with OpenGL. -Cambridge, UK: Cambridge University Press, 2003.

37. NVIDIA CUDA Programming Guide. Version 3.2. -http://developer.download.nvidia.com/compute/cuda/32/toolkit/docs/CUDACProgra mmingGuide.pdf

38. Prefix sum. http://en.wikipedia.org/wiki/Prefixsum

39. CUDA Data Parallel Primitives Library. General-Purpose Computation on Graphics Hardware. http://gpgpu.org/developer/cudpp

40. Radix sort. http://en.wikipedia.org/wiki/Radixsort

41. Дональд Кнут. Искусство программирования. 2-е издание. М.: «Вильямс», 2007. -т. 3.

42. Мальцев А.В., Омельченко Д.В., Торгашев М.А., Хураськин И.А. Методы формирования визуальных свойств поверхностей // Сб. научных трудов ИМВС РАН «Высокопроизводительные вычислительные системы и микропроцессоры». -М.: ИМВС РАН, 2006. №9. - С. 91-97.

43. Мальцев А.В., Михайлюк М.В. Технология рельефного текстурирования в системах визуализации // Сборник докладов научной конференции, посвященной 45-летию выхода человека в космос. М., 2006. - С. 59-75.

44. Мальцев А.В., Михайлюк М.В., Решетников В.Н. Моделирование карт отражения окружающей среды в реальном режиме времени // Труды 2-й Международной конференции «Системный анализ и информационные технологии». Обнинск, 2007.-т. 2.-С. 236-238.

45. Мальцев А.В., Михайлюк М.В. Рельефное текстурированике в системах визуализации тренажерных комплексов // Сб. тезисов 7-й Международной научнопрактической конференции «Пилотируемые полеты в космос». Звездный городок, 2007.-С. 139-141.

46. Мальцев А.В., Михайлюк М.В., Решетников В.Н. Реализация карт отражения окружающей среды в реальном режиме времени // Информационные технологии и вычислительные системы. 2008. -№ 2. - С. 35-42.

47. Мальцев А.В., Михайлюк М.В. Моделирование теней в виртуальных сценах с направленными источниками освещения // Информационные технологии и вычислительные системы. — 2010. -№ 2. С. 68-74.

48. Мальцев А.В. Построение адаптивной регулярной сетки трехмерной сцены в реальном режиме времени // Программные продукты и системы. 2010. — № 4. - С. 41-45.

49. Мальцев А.В. Методы высокореалистичной визуализации для космических тренажерных комплексов // XXXVII Гагаринские чтения. Научные труды Международной молодежной научной конференции. М., 2011. - С. 84-86.

50. Gunther J., Popov S., Seidel H.-P., Slusallek P. Realtime Ray Tracing On GPU With BVH-Based Packet Traversal // In Proceedings of the IEEE/Eurographics Symposium on Interactive Ray Tracing. 2007. - September. - Pp. 113-118.

51. Guntury S., Narayanan P. J. Ray Tracing Dynamic Scenes with Shadows on the GPU // In Proceedings of the Eurographics Symposium on Parallel Graphics and Visualization. —2010.-May.

52. Kalojanov J., Billeter М., Slusallek P. Two-Level Grids for Ray Tracing on GPUs // In Proceedings of Eurographics 2011. — 2011. Vol. 30, no. 2. — Pp. 307-314.

53. Reichl M., Dunger R., Schiewe A., Klemmer T., Hartleb M., Lux C., Frohlich B. GPU-based Ray Tracing of Dynamic Scenes // In Journal of Virtual Reality and Broadcasting. -2010.-Vol. 7, no. 1.