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

Учреждение Российской академии наук Научно-исследовательский институт системных исследований РАН

На правах рукописи 48534»'*'* удк 004.925.3

Мальцев Андрей Валерьевич

МЕТОДЫ И АЛГОРИТМЫ ЭФФЕКТИВНОГО ВЫЧИСЛЕНИЯ ОСВЕЩЕННОСТИ ТРЕХМЕРНЫХ ВИРТУАЛЬНЫХ СЦЕН В РЕАЛЬНОМ РЕЖИМЕ ВРЕМЕНИ

05.13.01 - Системный анализ, управление и обработка информации (по математическим отраслям и информатике)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

2 9 СЕН 2011

Москва 2011

4854944

Работа выполнена в Учреждении Российской академии наук Научно-исследовательском институте системных исследований РАН.

Научный руководитель: доктор физико-математических наук, профессор

Михайлюк Михаил Васильевич

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

Галактионов Владимир Александрович,

доктор физико-математических наук Лазутин Юрий Михайлович

Ведущая организация: Учреждение Российской академии наук

Институт системного анализа РАН (ИСА РАН)

Защита диссертации состоится 12 октября 2011 года в 16 часов на заседании диссертационного совета Д 002.265.01 при НИИСИ РАН по адресу: 117218, Москва, Нахимовский пр., д. 36, корп. 1, конференц-зал.

С диссертацией можно ознакомиться в библиотеке НИИСИ РАН (комн. 13-21а)

Автореферат разослан 9 сентября 2011 г

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

современные компьютерные методы обработки графической информации.

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

Положения, выносимые на защиту.

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

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

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

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

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

Апробация. Результаты работы и материалы исследований докладывались, обсуждались и получили одобрение специалистов на следующих конференциях [10-13]:

1. Международной молодежной научной конференции "XXXVII Гагаринские чтения" (г. Москва, 2011);

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

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

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

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

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

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

Содержание работы

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

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

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

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

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

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

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

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

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

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

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

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

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

• объекты для отображения методом трассировки лучей;

• объекты для отображения методом шейдерной обработки.

Распределение объектов по данным группам может производиться

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

В работе предлагается три критерия разделения: по расстоянию от наблюдателя, по важности объектов и смешанный критерий.

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

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

При написании шейдеров на стандартизированном кроссплатформенном языке низкого уровня ARB_vertex_program и ARB_fragment_program (стандарт компании Architecture Review Board) была выявлена проблема, связанная с отсутствием в данном языке возможности реализации условных операторов. Для решения этой проблемы в работе предлагается метод статической оптимизации шейдерных программ. Суть его состоит во введении специального метаязыка, с помощью которого можно записать условные выражения в шейдерах. Для записи условных операторов предлагается следующий синтаксис:

@JFусловиеi [\\условие 2 [... [|| условие...]]; [

@ELSE; (1)

]

@ENDIF;

Условия записываются в виде поставленных им в соответствие строковых констант, перед которыми могут стоять символы отрицания. Запись N условий подряд эквивалентна по смыслу их дизъюнкции.

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

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

Теорема 2.1. Любое логическое выражение, зависящее от N условий, можно записать в виде структуры типа (1).

Заключительный раздел главы посвящен общему рассмотрению используемой в данной работе технологии визуализации трехмерных сцен путем трассировки лучей на графических процессорах с поддержкой архитектуры СиБА. Также в нем описываются некоторые особенности параллельного программирования с применением С1ША.

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

I = Л(ка1а + (1 -р)- тах(0,£ • М) + р ■ С + (1 - у) ■ *,/, тах(0,Я ■ Я)5)км,

Р=Р*а-У, (2)

где ка, к<|, к, - коэффициенты отражения материалом рассеянной, диффузной и зеркальной компонент освещения, а 1а, и, 15 - параметры интенсивности источника; N - нормаль в точке Р; Ь - вектор из точки Р на источник света; Н = (Ъ-У)/||Ь-У|| - средний вектор между Ь и направлением V из точки Р на наблюдателя; э - резкость бликов; кж - коэффициент ослабления света, зависящий от расстояния между точкой Р и источником света; у - коэффициент наличия тени (0 - нет тени, 1 - в противном случае); рл, С - плотность и цвет тени.

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

я =

1, еспи<р< —

2

а

СОЭ (р — СОЭ— / „

2 I Р а

---—, если а е —,—

Р а 2 2

СОБ--СОЭ —

2 2

где <р - угол между вектором Ь и вектором направления освещения, а - угол раствора конуса, в пределах которого распространяется освещение, ар- угол, определяющий конус, внутри которого освещение от источника максимально.

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

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

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

Под картой теней понимается двумерная текстура в оттенках серого, в пикселах которой в цветовом виде закодированы расстояния от источника света до ближайших к нему объектов сцены по направлениям распространения световых лучей. Для формирования такой текстуры в случае направленного источника света (типа «фара» или «прожектор») предлагается визуализировать сцену из точки расположения этого источника. При этом направление взгляда камеры устанавливается совпадающим с вектором направления освещения. После такой визуализации буфер глубины будет содержать требуемую карту теней. Далее производится визуализация непосредственно из положения наблюдателя. Перед расчетом освещенности каждой точки каждого объекта сцены (путем шейдерной обработки по формуле (2)), вычисляется расстояние от рассматриваемой точки до источника света и сравнивается с соответствующим расстоянием, записанным в карте теней. Если найденное расстояние больше сохраненного в карте, то точка считается находящейся в тени, и коэффициент у=1, в противном случае - точка освещена и у=0.

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

исходящим из него в окружающее пространство. В работе предлагается разделить пространство, окружающее источник света, на два полупространства (Z+ и Z-) и для каждого из них синтезировать собственную текстурную карту теней. Для полупространства Z+ необходимо определить отображение всех направлений (исходящих из начала координат О в полупространство Z+) на О^ двумерную текстурную карту. Такое отображение построено в диссертации с использованием математической функции параболического типа. На рис. 1 точке Р при этом отображении соответствует точка Р" на текстурной карте.

На основании этой теоремы строится текстурная карта, в которой для любого луча (Рх, Ру, Р2) в пикселе рис> 1. (Р"х, Р"у) записывается расстояние до ближайшей точки объектов сцены по этому лучу. Далее, это расстояние используется для вычисления у при расчете освещенности объектов (или их частей) из полупространства Z+. Аналогичные действия выполняются для полупространства Z-.

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

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

В найденной точке Р пересечения луча с объектом луч разделяется на вторичные лучи (теневой с направлением на источник света, отраженный и преломленный). Если теневой луч не сталкивается на своем пути до источника ни с одним объектом, то в точке Р рассчитывается "прямая" освещенность (например, по модели Фонга), в противном случае освещенность от источника в точке Р равна 0. Прослеживание отраженного и преломленного лучей и поиск их пересечения с объектами сцены производится аналогично первичным лучам. Каждый из этих лучей в точке пересечения с объектом (если она существует) снова распадается на вторичные и т.д.

Источник

(камера)

Рис. 2.

Таким образом, получается дерево лучей, узлами которого являются точки пересечений с объектами. Интенсивность освещения I в каждом узле определяется суммой его "прямых" освещенностей от всех источников света О - индекс источника) и освещенностей 1а (отражения), 1т (преломления) в его дочерних узлах. Освещенности дочерних узлов суммируются с учетом коэффициентов, зависящих от свойств отражения и преломления материала (к5, к(), а также коэффициентов затухания энергии лучей (каПд, каи,т) в зависимости от расстояния. Интенсивность корня определяет цвет рассматриваемого пикселя буфера кадра. Глубину дерева пользователь может ограничить конкретным числом или некоторым условием.

Для вычисления освещенности в точках пересечения лучей с виртуальными объектами используется глобальная модель Уиттеда:

I = К^а + XЬ + + км тк,1т,

I

/,. = [ка /„., + шах (0, ■ ТУ)+шах (О, Я, • ЛГ)') *а„,, (3)

где 1а - интенсивность фонового освещения; 1а,ь 1а,ь - параметры интенсивности ¡-го источника; Ь; - вектор из точки Р на ¡-ый источник света; Н = (Ь|-У)/||ЬГУ||; капК, каП,т, ка1(1| - коэффициенты затухания энергии световых лучей. Остальные параметры в этой формуле те же, что в формуле (2).

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

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

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

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

Теорема 4.2. Пусть имеется невырожденный треугольный полигон с вершинами V0, V, и V2 и нормалями в этих вершинах соответственно No, Nj и N2. Пусть далее ei = V|-Vo, е2 = V2-V0. Тогда нормаль N в произвольной точке Ро этого полигона определяется по формуле

N=(l-f(u/,+ur))N0+f(u/lN1 + urN2)>

e2ei " (ei-e2)e2 _ _ е?е2 - (е.-е^е, efe:

гдеf = Po-Vo, и» =

ere,

-(еге2)

- (е,-е2)

И .И и .Л.

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

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

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

/ / .........и........

/1 i:::. у /

ж .... ' Ж'

1 ? i / ~7f ?

Рис. 3.

При использовании заполненной регулярной сетки одной из важных задач является поиск следующей по лучу ячейки, в которую нужно перейти после окончания работы с текущей ячейкой. Данный выбор зависит от точки Р входа в текущую ячейку и от координат направляющего вектора D(x,y,z) луча. В программном коде определение следующей ячейки обычно осуществляется с помощью реализации условных переходов. Однако применение условных конструкций при выполнении программы на GPU с использованием архитектуры параллельных вычислений CUDA вызывает расхождение потоков в исполняемых группах. То есть потоки, соответствующие разным ветвям будут выполняться последовательно, а не параллельно, что снизит эффективность и скорость выполнения трассировки.

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

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

Теорема 4.5. Ячейка (Г, j', к') регулярной сетки, следующая за ячейкой (i, j, к) по лучу R с направляющим вектором D(x, у, z), определяется по формулам:

Г = i + k¡((l - S(|x|fy- |y|fx)) • (1 - S(|x|f2- |z|fx))), j' = j + Ц((1 - S(|y|fx- |x|fy)) • (1 - S(|y|fz- |z[fy))), k' = k + kk((l - S(|z|fy- |y|fz)) • (1 - S(|z|fx- |х|Щ,

где k¡ = 1 -2S(x), kj=l-2S(y), kk=l-2S(z),

fx = 1 - S(x) - k¡kx, fy= 1 - S(y) - kjky, fz= 1 - S(z) - ktk2.

Здесь (kx>ky,kz):=—{P-Bmjn)~{'>j>k), p - точка входа в текущую ячейку, А

- размер ячейки, Bm¡„ - минимальная точка сетки, S(x) - аппаратная функция, возвращающая значение знакового разряда числа.

В пятой главе рассмотрена реализация (в виде программных модулей) и результаты тестирования описанных в предыдущих главах методов и алгоритмов. Разработанные программные модули интегрированы в систему визуализации «GLView» трехмерных виртуальных сцен (созданных в 3D МАХ) в реальном масштабе времени в моно и стерео режимах. Это позволило существенно повысить качество и скорость визуализации, а также реализовать ряд специальных графических эффектов.

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

представлены в виде диаграмм на рис. 4 (статическая сцена Conference room, 280 тысяч полигонов; а) - трассировка только первичных лучей, б) -трассировка первичных и теневых лучей) и рис. 5 (динамические сцены, 170, 280 и 1100 тысяч полигонов; а) - трассировка только первичных лучей, б) -трассировка первичных и теневых лучей).

□ Попов и др.

Первичные лучи

а)

ШЗ Фролов,

Игнатенко В Гюнтер и др.

■ Данная работа

Первичные лучи + тени

б)

Рис. 4.

30

170k 280k 1100k

Первичные лучи

а)

20

10

а

170k 280k 1100k

Первичные лучи + тени

б)

Рис. 5.

I Калоянов и др.

iГантюри и

Нараянан I Данная работа

Созданные программные модули прошли апробацию на тренажерном комплексе в ФГБУ «Научно-исследовательский испытательный центр подготовки космонавтов имени Ю.А. Гагарина» и показали свое соответствие высоким требованиям, предъявляемым в настоящее время к системам визуализации трехмерных виртуальных сцен для имитационно-тренажерных комплексов управления сложными техническими системами. На рис. 6 показан результат визуализации модели Международной космической станции (МКС), состоящей из 1 млн. полигонов, а на рис. 7 - освещение стыковочного узла МКС источником типа «фара».

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

Рис. 6.

В заключении сформулированы основные результаты работы, состоящие

следующем:

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

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

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

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

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

Работы автора по теме диссертации

1. Мальцев A.B. Построение адаптивной регулярной сетки трехмерной сцены в реальном режиме времени // Программные продукты и системы,- 2010.-№4,- сс. 41-45.

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

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

4. Мальцев A.B., Михайлюк M.B. Реализация теней для всенаправленных источников света в реальном режиме времени // Программные продукты и системы,- 2008.- №3.- сс. 35-38.

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

6. Мальцев A.B., Михайлюк М.В. Трассировка лучей в трехмерных сценах с использованием регулярных сеток // Моделирование и визуализация. Многопроцессорные системы. Инструментальные средства разработки ПО. Сборник статей под редакцией академика РАН В.Б. Бетелина- 2010 - сс. 36-47.

7. Мальцев A.B., Михайлюк М.В. Использование цветовых карт для реализации трассировки первичных лучей в трехмерных сценах // Моделирование и визуализация. Многопроцессорные системы. Инструментальные средства разработки ПО. Сборник статей под редакцией академика РАН В.Б. Бетелина.- 2009 - сс. 54-69.

8. Мальцев A.B., Михайлюк М.В. Реализация теней для направленных источников света в 3D в реальном режиме времени // Интеллектуальные и адаптивные роботы,- 2009,- №1-2,- сс. 103-108.

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

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

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

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

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

1S

Подписано в печать: 08.09.2011

Заказ № 5870 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение.

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

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

Методы исследований.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-х международных научных конференциях, а также на научных семинарах Центра визуализации и спутниковых информационных технологий НИИСИ РАН. Созданные в процессе выполнения работы программные модули прошли апробацию на тренажерном комплексе в ФГБУ «Научно-исследовательский испытательный центр подготовки космонавтов имени Ю.А. Гагарина» и показали свое соответствие требованиям, предъявляемым в настоящее время к системам визуализации трехмерных виртуальных сцен для имитационно-тренажерных комплексов.

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.