авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

Когерентные алгоритмы синтеза реалистичных изображений

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

Востряков Константин Анатольевич

Когерентные алгоритмы синтеза реалистичных

изображений

Специальность 05.13.11 — математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

Москва – 2009

Работа выполнена в Учреждении Российской академии наук Институте прикладной математики имени М.В. Келдыша РАН.

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

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

Ведущая организация: Нижегородский государственный уни верситет имени Н.И. Лобачевского

Защита состоится « » 2009 г. в часов на заседании дис сертационного совета Д 002.024.01 при Учреждении Российской академии на ук Институте прикладной математики имени М.В. Келдыша РАН, располо женном по адресу: 125047, Москва, Миусская пл.,

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разослан « » 2009 г.

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

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

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

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

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

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

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

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

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



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

Основные задачи

работы:

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

разработка когерентных версий базовых алгоритмов синтеза реалистич ных изображений: алгоритмов устранения ступенчатости изображения и расчета вторичного освещения;

создание программного комплекса синтеза изображений с использова нием ОКМД инструкций.

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

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

Практическая значимость Когерентные алгоритмы синтеза изображений эффективно реализуют пре имущество ОКМД инструкций массовых процессоров. Для большинства сцен, используемых в промышленной и архитектурной визуализации, удалось до стичь сокращения общего времени расчетов от 2.3 до 3.2 раз, отдельные этапы расчета освещения были ускорены более чем 4 раза. Такое ускорение расче та существенным образом повышает производительность труда при работе с системой визуализации.

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

Апробация работы Результаты работы докладывались и обсуждались на:

16-й, 17-й, 18-й и 19-й международных конференциях по компьютерной графике и машинному зрению «Graphicon»;

семинаре по компьютерной графике и мультимедиа под руководством Ю.М. Баяковского (ф-т ВМиК МГУ), Россия, Москва, 2009;

семинаре отделения «Программирование» ИПМ им. М.В. Келдыша РАН, Россия, Москва, 2009.





Публикации По результатам работы имеются десять публикаций, включая одну ста тью в рецензируемом научном журнале из списка ВАК [1], 6 статей в трудах международных научных конференций [2–7] и 3 статьи в сборниках трудов всероссийских научных конференций [8] и научно-практических семинаров [9, 10].

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

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

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

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

В втором разделе рассказывается об особенностях программной реализа ции с использованием ОКМД инструкций SSE (Streaming SIMD Extensions, потоковые ОКМД расширения). ОКМД инструкции SSE позволяют задейство вать восемь 128-битных регистров, в каждом из которых помещается четыре числа с плавающей точкой. Над всеми числами в регистре, как правило, вы полняются одинаковые операции. Если алгоритм содержит условные пере ходы, то обе ветви алгоритма обрабатываются последовательно. С помощью битовой маски результат склеивается. Проиллюстрируем это на простом при мере (рис. 3). Алгоритм вычисления функции y от x зависит от знака x, то есть зависит от входных данных. Для вычисления функции необходимо создать би товую маску с 0, где x 0 и 1, где x 0. Для четырех аргументов вычисляется x + 1, и для четырех аргументов 2x. С помощью маски результат совмещается.

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

Для программирования SSE можно использовать как ассемблер, так и инт x + 1, x y= x 2x, Рис. 4. Бинарное дерево Рис. 3. Пример ОКМД реализации вычисления функ ции y(x), которая зависит от входных данных ринсики (intrinsics). Синтаксически интринсики — это функции языка С, кото рые воспринимаются компилятором специальным образом. Большинство инт ринсиков транслируются в одну команду ассемблера. Функции принимают 128 битные переменные. Компилятор сам распределяет какие переменные по местить на регистры, а какие в памяти. На интринсиках программировать намного проще, чем на ассемблере. Операция сложения четырех чисел с пла вающей точкой будет выглядеть следующим образом:

_m128 _mm_add_ps(_m128 a, _m128 b);

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

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

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

В четвертом разделе рассказывается о когерентной (четырехлучевой) SSE трассировке лучей. Четыре луча трассируются одновременно, используя SSE команды. Однако они могут проходить различные ветви дерева, поэтому необ ходима временная блокировка нескольких лучей из четверки. Для этого ис пользуется маска активных лучей. При достижении листового узла дерева выполняется пересечение четырех лучей с треугольниками. Часть лучей из четверки может пересечь треугольник, а часть нет. Здесь снова пользуемся приемом маскирования.

Используя когерентную трассировку лучей, на различных сценах удалось достичь ускорения трассировки лучей от 2.6 до 3.5 раз. Ускорение было до стигнуто за счет использования SSE инструкций, которые могут дать ускоре ние до 4 раз в случае полной когерентности, тщательного подбора алгоритмов и структур данных. Достигнутая скорость визуализации не является интерак тивной, но уже приближается к ней.

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

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

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

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

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

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

В зависимости от размерности сетки ДФО когерентный бинарный поиск в среднем дает ускорение около 2.2 раза, что меньше 4, поскольку алгоритм содержит множество ветвлений, снижающих эффективность ОКМД команд.

Для получения окончательного результата необходимо произвести линейную интерполяцию табличных значений. Удалось достичь ускорения при модели ровании ДФО с использованием SSE инструкций в 3.2–3.5 раз в зависимости от размера сетки по каждому из измерений.

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

Разработанная система поддерживает несколько типов источников света.

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

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

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

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

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

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

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

Вначале для текущего блока выполняется растеризация в графическом про цессоре. Это может избавить от трассировки множества дополнительных лу чей для определения пикселей с геометрическими разрывами. На первом уровне используется регулярная выборка. Лучи трассируются четверками через уг лы пикселей (рис. 7). Алгоритм определяет вид разрыва: горизонтальный или вертикальный. Горизонтальный означает, что существует высокий градиент между точками A и B или точками C и D. Если разрыв определяется неодно значно, то алгоритм просто выбирает горизонтальный разрыв. Такое решение не скажется на корректности, а скажется лишь на производительности. Если Рис. 7. Начальная 4-лучевая трасси- Рис. 8. Второй уровень адаптации, z0–z4 — ровка через углы пикселей зоны третьего уровня Рис. 9. Три четверки сравнений (b0–b3, Рис. 10. Зигзаги (четверки) лучей 3-го уров c00–c03, c10–c13) для определения зон ня. Каждый обстреливает одну из зон третьего уровня алгоритм обнаружил вертикальный разрыв, то точки ABCD поворачиваются на 90 градусов против часовой стрелки (рис. 8). Этот поворот обеспечивает дальнейшую линейность алгоритма независимо от вида разрыва. Если разрыв не обнаружен, то цвет данного пикселя определяется как среднее его угло вых значений, иначе алгоритм переходит ко второму уровню адаптации для данного пикселя.

Четверка лучей трассируется через точки E, F, G, H как показано на рис. 8.

Для определения разрывов между точками первого и второго уровней исполь зуем 3 четверки сравнений: b0–b3, c00–c03, c10–c13, показанных на рис. 9.

Каждая четверка сравнений выполняется с помощью SSE команд над r, g, b компонентами цвета. Каждое SSE сравнение дает четырехбитную маску, ко торая используется как индекс в таблице определения разрывов. Значениями этой таблицы являются флаги, которые определяют зоны разрывов: z0, z1, z2, z3, z4 (рис. 8). Полученные флаги показывают зоны разрывов, где необходимо дополнительно трассировать лучи.

На третьем уровне через каждую разрывную зону трассируется четверка лучей зигзагом (рис. 10). Каждый зигзаг покрывает одну из разрывных зон.

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

а) Один луч на пиксел. б) Классическая реализация в) Новый адаптивный устранения ступенчатости. когерентный алгоритм.

Рис. 11. Сложный синтетический тест. Линии сходятся в точку Особенность устранения ступенчатости изображения состоит в том, что не существует идеального решения, с которым бы можно было сравниться. Так же нет метрики, которая бы достаточно адекватно отражала человеческое вос приятие ступенчатости. Поэтому за образец для сравнения по качеству была выбрана классическая реализация алгоритма устранения ступенчатости изоб ражения. На рис. 11 показан сложный синтетический тест, где линии сходятся в точку. На рис. 11а изображение построено трассировкой 1 луча на пиксел, при этом имеем огромный муар и ступенчатость. За контрольный по качеству алгоритм устранения ступенчатости взята классическая реализация — через каждый пиксел трассируются 25 случайных лучей (рис. 11б). Муар и сту пенчатость значительно уменьшены. Но из-за отсутствия адаптивности, этот алгоритм работает в 25 раз медленнее. Качество устранения ступенчатости предложенного адаптивного метода (рис. 11в) сопоставимо с качеством при трассировке 25 случайных лучей на пиксел (рис. 11б). Тесты показали, что в типичных сценах, при использовании предложенного адаптивного алгоритма и среднем количестве лучей на пиксел 1.5–2, может быть достигнуто качество, сравнимое с 25 лучами на пиксел регулярной выборки.

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

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

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

а) б) в) Рис. 12. Схема работы алгоритма репроекции.

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

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

В точке B (рис. 12б), куда необходимо экстраполировать освещение, вы полняется репроекция вычисленных в точке A и сохраненных в кэше значе ний падающего излучения (показаны пунктиром). Четыре значения излучения репроецируются одновременно, используя SSE. При репроекции учитывает ся перекрытие и затенение. Репроекция осуществляется слой за слоем, начи ная от ближнего слоя и заканчивая самым дальним. При этом полноценного Z-буфера не нужно, можно обойтись лишь маской заполнения. Кроме того, для каждого п-элемента создается битовая маска неизвестности (тени). Она запрещает заполнение более дальних слоев в области неизвестности. Маски заполнения и неизвестности являются битовыми матрицами 128 128 бит.

Любая строка битовой матрицы — это 128 битная SSE переменная. Таким образом, битовые логические операции применяются для 128 битов одновре менно.

Из-за дискретности точек после репроекции остаются бреши (рис. 12в).

Бреши и зона тени заполняются трассировкой лучей. Если бы затенение не учитывалось, то обратная сторона ближнего объекта (красный сектор) была бы учтена неправильно.

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

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

Смещенная версия алгоритма репроекции дает приблизительно ускорение от 3.7 до 21.6 раза. Метод репроекции в своей несмещенной версии дает уско рение в 1.7–6.1 раз. Ускорение было достигнуто как за счет использования SSE инструкций, так и за счет когерентности освещения, то есть экстраполяции. В отличии от предыдущих методов кэширования излучения, новый алгоритм ре проекции точнее контролирует ошибку экстраполяции, что позволяет разбить изображение на независимые блоки и эффективно задействовать несколько потоков. Для 4 потоков удалось добиться ускорения расчета вторичного осве щения в 3.8 раза.

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

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

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

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

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

Список публикаций [1] Б.Х. Барладян, А.Г. Волобой, К.А. Востряков, В.А. Галактионов, Л.З.

Шапиро. Применение когерентной трассировки лучей в задачах физи чески аккуратной визуализации // Программирование. — 2008. — № 5. — С. 67–80.

[2] К.А. Востряков. Моделирование глобального освещения // Международ ная научная студенческая конференция «Студент и научно-технический прогресс» / НГУ. — Новосибирск: 2005. — С. 157–158.

[3] К.А. Востряков. Ускорение финального сбора с помощью октантных текстур // Международная научная студенческая конференция «Сту дент и научно-технический прогресс» / НГУ. — Новосибирск: 2006. — С. 121–127.

[4] К.А. Востряков. Глобальное освещение с помощью октантных текстур // Доклады 16-й Международной конференции по компьютерной графи ке и машинному зрению «Графикон 2006». — Новосибирск: 2006. — С. 473–476.

[5] К.А. Востряков, А.Г. Волобой. Алгоритм устранения лестничного эффек та для 4-лучевой SSE трассировки лучей // 17-ая международная кон ференция по компьютерной графике и зрению / МГУ. — 2007. — 23- июня. — С. 269–272.

[6] К.А. Востряков. Новый иерархический базис для освещения на полусфе ре // Труды 18-ой международной конференции по компьютерной гра фике и зрению / Россия, Московский Государственный Университет. — 2008. — 23–27 июня. — С. 262–269.

[7] К.А. Востряков. Высокочастотный кэш излучения // 19-ая международ ная конференция по компьютерной графике и зрению / МГУ. — 2009. — С. 360–363.

[8] К.А. Востряков. Глобальное освещение стохастической трассировкой лу чей // Всероссийская конференция студентов и молодых ученых «Наука.

Технологии. Инновации» / НГТУ. — Новосибирск: 2004. — С. 17–18.

[9] К.А. Востряков. Расчет освещения от карты окружения, заданной с боль шим динамическим диапазоном // Материалы 11-го научно-практическо го семинара «Новые информационные технологии в автоматизированных системах» / М.:МГИЭМ. — 2008. — С. 24–28.

[10] К.А. Востряков. Нелинейная экстраполяция излучения // Новые ин формационные технологии в автоматизированных системах: материалы двенадцатого научно-практического семинара / М. МГИЭМ. — 2009. — С. 62–73.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.