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

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

Ои^"--

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

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

изображений

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 2 [-.'СЯ

Москва - 2009

003482883

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

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

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

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

профессор

Клименко Станислав Владимирович

кандидат физико-математических наук Игнатенко Алексей Викторович

Ведущая организация: Нижегородский государственный уни-

верситет имени Н.И. Лобачевского

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

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

Автореферат разослан 30 октября 2009 г.

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

с£с

Т.А. Полилова ——_

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

Актуальность работы

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

а) Кабина самолета б) Освещение стадиона в) Автомобильная краска

Рис. 1. Моделирование распространения света в виртуальных сценах

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

Технология расчета освещения и синтеза реалистичных изображений

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

Источник Источник Источник

Камера Экрану (*) Экрану /~) Камера экра„ ЛЛ

невые

ект

,ы Объекъ^ ггоричные лучи - сцены^^

а) Первичное освещение 6) Вторичное освещение в) Когерентная трассировка Рис. 2. Основная идея метода синтеза изображений трассировкой лучей

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

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

Синтез реалистичных изображений. Проблемы и аппаратные средства

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

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

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

Цель диссертационной работы

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

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

Основные задачи работы:

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

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

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

Научная новизна

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

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

Практическая значимость

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

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

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

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

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

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

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

Публикации

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

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

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

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

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

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

Для программирования SSE можно использовать как ассемблер, так и инт-

. х -2 -1

2

^m 1 О

О ' Oxf. f Oxf..f

дг > 0 X=x+1

2дг, * < О

у2=2х ; -4 • - -2 , 2 4 * -V , . . ▼ -4 -2 -2 3

-1 О 2 3

Рис. 3. Пример ОКМД реализации вычисления функ- Рис- 4- Бинарное дерево ции }>(*), которая зависит от входных данных

ринсики (intrinsics). Синтаксически интринсики — это функции языка С, которые воспринимаются компилятором специальным образом. Большинство инт-ринсиков транслируются в одну команду ассемблера. Функции принимают 128 битные переменные. Компилятор сам распределяет какие переменные поместить на регистры, а какие в памяти. На интринсиках программировать намного проще, чем на ассемблере. Операция сложения четырех чисел с плавающей точкой будет выглядеть следующим образом:

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

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

.ml28 _mm_add_ps(_ml28 а, _ш128 Ъ);

Ортогональность секущих плоскостей дерева значительно упрощает проверку пересечения луча и секущей плоскости. Листовым узлам дерева приписаны геометрические примитивы (треугольники), которые описывают поверхности объектов. Далее в разделе рассмотрены принципы построения и обхода 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). Алгоритм определяет вид разрыва: горизонтальный или вертикальный. Горизонтальный означает, что существует высокий градиент между точками А и В или точками С и D. Если разрыв определяется неоднозначно, то алгоритм просто выбирает горизонтальный разрыв. Такое решение не скажется на корректности, а скажется лишь на производительности. Если

Камера

Пиксели экрана

А,

zO

•в в.

IF

z4

z2

•Н

z3 z2

z1

zO

Рис. 7. Начальная 4-лучевая трассировка через углы пикселей

•О А*-------------

Рис. 8. Второй уровень адаптации, г0-г4 -зоны третьего уровня

^В _ ,Р

Рис. 9. Три четверки сравнений (ЬО-ЬЗ, сОО-сОЗ, с10-с13) для определения зон третьего уровня

Рис. 10. Зигзаги (четверки) лучей 3-го уровня. Каждый обстреливает одну из зон

алгоритм обнаружил вертикальный разрыв, то точки ABCD поворачиваются на 90 градусов против часовой стрелки (рис. 8). Этот поворот обеспечивает дальнейшую линейность алгоритма независимо от вида разрыва. Если разрыв не обнаружен, то цвет данного пикселя определяется как среднее его угловых значений, иначе алгоритм переходит ко второму уровню адаптации для данного пикселя.

Четверка лучей трассируется через точки Е, F, G, Н как показано на рис. 8. Для определения разрывов между точками первого и второго уровней используем 3 четверки сравнений: ЬО-ЬЗ, сОО-сОЗ, с10-с13, показанных на рис. 9. Каждая четверка сравнений выполняется с помощью SSE команд над г, g, b компонентами цвета. Каждое SSE сравнение дает четырехбитную маску, которая используется как индекс в таблице определения разрывов. Значениями этой таблицы являются флаги, которые определяют зоны разрывов: zO, zl, z2, z3, z4 (рис. 8). Полученные флаги показывают зоны разрывов, где необходимо дополнительно трассировать лучи.

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

а) Один луч на пиксел. б) Классическая реализация устранения ступенчатости.

в) Новый адаптивный когерентный алгоритм.

Рис. 11. Сложный синтетический тест. Линии сходятся в точку

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

предложенного адаптивного метода (рис. 11в) сопоставимо с качеством при трассировке 25 случайных лучей на пиксел (рис. 116). Тесты показали, что в типичных сценах, при использовании предложенного адаптивного алгоритма и среднем количестве лучей на пиксел 1.5-2, может быть достигнуто качество, сравнимое с 25 лучами на пиксел регулярной выборки.

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

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

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

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

Ро Р2 Ро

*<7 "<С/

Рз ........ р^ ....... ^3....

„■> А в А в „\ А в а) б) в)

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

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

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

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

репроецируются одновременно, используя SSE. При репроекции учитывается перекрытие и затенение. Репроекция осуществляется слой за слоем, начиная от ближнего слоя и заканчивая самым дальним. При этом полноценного Z-буфера не нужно, можно обойтись лишь маской заполнения. Кроме того, для каждого п-элемента создается битовая маска неизвестности (тени). Она запрещает заполнение более дальних слоев в области неизвестности. Маски заполнения и неизвестности являются битовыми матрицами 128 X 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] Б.Х. Барладян, А.Г. Волобой, К. А. Востряков, В.А. Галактионов, JI.3. Шапиро. Применение когерентной трассировки лучей в задачах физически аккуратной визуализации // Программирование. — 2008. — № 5. — С. 67-80.

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

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

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

[5] К.А. Востряков, А.Г. Волобой. Алгоритм устранения лестничного эффекта для 4-лучевой SSE трассировки лучей // 17-ая международная кон-

ференция по компьютерной графике и зрению / МГУ.— 2007.-23-27 июня.-С. 269-272.

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

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

[8] К.А. Востряков. Глобальное освещение стохастической трассировкой лучей // Всероссийская конференция студентов и молодых ученых «Наука. Технологии. Инновации» / НГТУ. — Новосибирск: 2004. — С. 17-18.

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

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

Подписано в печать 27 октября 2009 года.

Формат 60x90/18. Заказ 858. Тираж 100 экз.

Печать офсетная. Бумага для множительных аппаратов.

Отпечатано в ООО "ФЭД+", Москва, ул. Кедрова, д. 15, тел. 774-26-96

Введение.

Глава 1. Синтез изображений методом когерентной трассировки лучей.

1.1. Существующие технологии ускорения трассировки лучей

1.2. ОКМД инструкции SSE. Программная реализация

1.3. Трассировка луча.

1.4. Четырехлучевая SSE трассировка.

Актуальность работы

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

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

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

Для архитектурных сцен, например, стадиона (рис. 1в) важно оценить соответствие освещенности стандартам, равномерность освещенности поля осветительными приборами, просматриваемость поля со всех трибун, насколько хорошо будет виден мяч при игре.

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

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

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

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

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

Технология расчета освещения и синтеза реалистичных изображений

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

Источник

Обьект

Объект сцены а) Первичное освещение, отражения и б) Вторичное освещение преломления

Рис. 2. Основная идея метода синтеза изображений трассировкой лучей тов лучи могут отражаться и преломляться. Таким образом формируется изображение видимое виртуальной камерой.

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

Синтез реалистичных изображений. Проблемы

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

Какое количество ресурсов необходимо для синтеза реалистичного изображения? Оценим на простом примере. Возьмем разрешение экрана Np = 1000 х 1000 пикселей, N[ = 10 источников света, и глубину зеркальных отражений Nj = 3. При этом необходимо NpNiNj = 30М лучей, что эквивалентно порядка 1 секунде расчета на современном мощном персональном компьютере. Если использовать не точечные, а площадные источники (умножим на х10 -г 100 для интегрирования освещения несколькими лучами), и учесть вторичное освещение (умножим на хЮО 1000 для интегрирования освещения со всех направлений), то необходимо уже несколько миллиардов лучей — несколько часов расчета. На примере видно, как переход от простой модели освещения к более сложной с площадными источниками света и вторичным освещением кардинально меняет требуемое расчетное время с 1 секунды до нескольких часов.

Как сказал сотрудник студии Pixar, одного из лидеров индустрии синтеза изображений [1]: «Я начал работать в этой области более 15 лет назад. И я не понимаю почему, несмотря на то, что компьютеры становятся быстрее, нужно все больше времени чем раньше для того, чтобы получить изображение»1. Поэтому любая возможность ускорить расчеты используется.

I have started to work in this field more than 15 years ago. I do not understand why, while computers get faster, it takes us more time than before to make an image. - jc kalache, dp, pixar

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

Аппаратные средства

Какие возможности для ускорения нам может предложить массовый процессор? Рост тактовой частоты замедлился. Производительность наращивается в основном за счет распараллеливания. Современные процессоры х86 для массового рынка поддерживают параллельное выполнение нескольких типов: конвейер, многоядерность, ОКМД инструкции.

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

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

ОКМД (одна команда — много данных). Другими словами, над несколькими потоками данных выполняются одни команды. Теоретиче

Таблица 1. Развитие ширины векторных инструкций в архитектуре 1Ах86

Инструкции Ширина в битах Год выхода

ММХ 64 1996

SSE 128 1999

AVX 256 2010

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

Существует устойчивая тенденция роста ширины ОКМД инструкций от 64 битных в 1996 году до 256 и 512 битных, которые появятся в следующем году (табл. 1). Основные и уже широко распространенные ОКМД инструкции — это SSE. Они есть практически во всех массовых процессорах, которые выпущены за последние 10 лет. То есть речь идет об инструкциях в массовых процессорах.

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

Источник I

Тень

Рис. 3. Когерентная трассировка лучей

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

Цель диссертационной работы

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

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

Основные задачи работы:

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

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

Научная новизна

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

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

Практическая значимость

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

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

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

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

• 16-й международной конференции по компьютерной графике и машинному зрению «Graphicon-2006», Россия, Новосибирск, 2006;

• 17-й международной конференции по компьютерной графике и машинному зрению «Graphicon-2007», Россия, Москва, 2007;

• 18-й международной конференции по компьютерной графике и машинному зрению «Graphicon-2008», Россия, Москва, 2008;

• 19-й международной конференции по компьютерной графике и машинному зрению «Graphicon-2009», Россия, Москва, 2009;

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

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

Публикации

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

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Диссертация изложена на 115 страницах, содержит 34 иллюстрации и 10 таблиц. Список литературы содержит 95 наименований.

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

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

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

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

Заключение

Примеры практического использования

Когерентные алгоритмы синтеза реалистичных изображений существенным образом реализуют преимущество ОКМД инструкций массовых процессоров. Разработанные программные средства были включены как программная компонента в индустриальный программный комплекс реалистичной визуализации Inspirer [95]. Некоторые примеры их практического использования для расчета освещения и синтеза реалистичных изображений моделей самолетов и автомобилей, предоставленных компаниями-заказчиками, приведены в таблице 4.4. Как видно из таблицы, удалось достичь сокращения общего времени расчетов от 2.3 до 3.2 раза, что существенным образом повышает производительность труда при работе с системой.

1. Fabio Pellacini. 1.teractive cinematic lighting // SIGGRAPH '08: ACM SIGGRAPH 2008 classes.- New York, NY, USA: ACM, 2008.-Pp. 1-47.

2. Б.Х. Барладян, А.Г. Волобой, К.А. Востряков, В.А. Галактионов, JI.3. Шапиро. Применение когерентной трассировки лучей в задачах физически аккуратной визуализации // Программирование.— 2008.— № 5.- С. 67-80.

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

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

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

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

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

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

9. К.А. Востряков. Глобальное освещение стохастической трассировкой лучей // Всероссийская конференция студентов и молодых ученых «Наука. Технологии. Инновации» / НГТУ. — Новосибирск: 2004.- С. 17-18.

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

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

12. Sven Woop, Jorg Schmittler, Pliilipp Slusallek. RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing 11 Proceedings of ACM SIGGRAPH 2005 (to appear).— 2005. —July, http://www.saarcor. de/.

13. Jorg Schmittler, Sven Woop, Daniel Wagner, Wolfgang J. Paul, Philipp Slusallek. Realtime Ray Tracing of Dynamic Scenes on an FPGA Chip // Proceedings of Graphics Hardware. — 2004. — Pp. 95-106.

14. Daniel Reiter Horn, Jeremy Sugerman, Mike Houston, Pat Hanrahan. Interactive k-d tree GPU raytracing // I3D '07: Proceedings of the 2007 symposium on Interactive 3D graphics and games.— New York, NY, USA: ACM, 2007. Pp. 167-174.

15. Johannes Gtinther, Stefan Popov, Hans-Peter Seidel, Philipp Slusallek. Realtime Ray Tracing on GPU with BVH-based Packet Traversal // Proceedings of the IEEE/Eurographics Symposium on Interactive Ray Tracing 2007. 2007. - Sept. - Pp. 113-118.

16. Timo Aila, Samuli Laine. Understanding the Efficiency of Ray Traversal on GPUs // Proceedings of High-Performance Graphics 2009, — 2009.

17. John A. Tsakok. Faster incoherent rays: Multi-BVH ray stream tracing // HPG '09: Proceedings of the Conference on High Performance Graphics 2009.- New York, NY, USA: ACM, 2009,- Pp. 151-158.

18. Ingo Wald. Realtime Ray Tracing and Interactive Global Illumination: Ph.D. thesis. 2004.

19. Carsten Benthin. Realtime Ray Tracing on Current CPU Architectures: Ph.D. thesis. -2006.

20. In go Wald, Solomon Boulos, Peter Shirley. Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies // ACM Transactions on Graphics. — 2007,— Vol. 26, no. 1.

21. C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, D. Manocha. Fast BVH Construction on GPUs // Computer Graphics Forum.— Vol. 28, no. 2,— Pp. 375-384. http://dx.doi.Org/10.llll/j.1467-8659. 2009.01377.x.

22. Ingo Wald, Thiago Ize, Andrew Kensler, Aaron Knoll, Steven G Parker. Ray Tracing Animated Scenes using Coherent Grid Traversal // ACM Transactions on Graphics.— 2006.— Pp. 485-493.— (Proceedings of ACM SIGGRAPH 2006).

23. John Amanatides, Andrew Woo. A Fast Voxel Traversal Algorithm for Ray Tracing // In Eurographics '87.- 1987.- Pp. 3-10.

24. Carsten Wachter, Alexander Keller. Instant Ray Tracing: The Bounding Interval Hierarchy // Proceedings of the 17th EuroGraphics Symposium on Rendering. 2006. - Pp. 139-149.

25. Ingo Wald, Carsten Benthin, Philipp Slusallek. OpenRT A Flexible and Scalable Rendering Engine for Interactive 3D Graphics: Tech. rep.: 2002. — submitted for publication, meanwhile available as a Technical Report, TR-2002-01, Saarland University.

26. James Bigler, Abe Stephens, Steven G. Parker. Design for Parallel Interactive Ray Tracing Systems // in: Proceedings of IEEE Symposium on Interactive Ray Tracing. — 2006. Pp. 187-196.

27. SIGGRAPH conference. 2009. - 3-7 August, http: //www. siggraph. org/ s2009/.

28. Bui Tuong Phong. Illumination for computer generated pictures // Com-mun. ACM. 1975.-Vol. 18, no. 6.-Pp. 311-317.

29. James F. Blinn. Models of light reflection for computer synthesized pictures // SIGGRAPH Comput. Graph.- 1911.- Vol. 11, no. 2,-Pp. 192-198.

30. A.A. Letunov, B.H. Barladian, E.Yu. Zueva, V.P Veshnevetc, S.A. Solda-tov. CCD-based device for BDF measurements in computer graphics // The 9-th International Conference on Computer Graphics and Vision. — Moscow, Russia: 1999.

31. Vladimir Volevich, Andrei Khodulev, Edward Kopylov, Olga Karpenko. An Approach to Cloth Synthesis and Visualization // The 7-th International Conference on Computer Graphics and Visualization. — Moscow, Russia: 1997.

32. Eric P. F. Lafortune, Sing choong Foo, Kenneth E. Torrance, Donald P. Greenberg. Non-Linear Approximation of Reflectance Functions.- 1997.

33. Peter S. Oder. Spherical Wavelets: Efficiently Representing Functions on the Sphere.— 1995. http://citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.16.340.

34. Jason Lawrence, Szymon Rusinkiewicz, Ravi Ramamoorthi. Efficient BRDF Importance Sampling Using a Factored Representation // ACM Transactions on Graphics (Proc. SIGGRAPH). — 2004.— August.

35. Aydin Ozturk, Murat Kurt, Ahmet Bilgili, Cengiz Gungor. Technical Section: Linear approximation of Bidirectional Reflectance Distribution Functions // Comput. Graph. 2008.- Vol. 32, no. 2,- Pp. 149-158.

36. Leonard Mcmillan, Arthur C. Smith, Wojciech Matusik, Wojciech Ma-tusik. A Data-Driven Reflectance Model // in Proc. of SIGGRAPH. — 2003.

37. Alexander Reshetov, Alexei Soupikov, Jim Hurley. Multi-level ray tracing algorithm // ACM Transactions on Graphics. — 2005. — Vol. 24, no. 3. — Pp. 1176-1185.

38. IA-32 Intel Architecture Optimization Reference Manual, p. 440. ftp: //download.intel.com/design/Pentium4/manuals/24896611.pdf.

39. Справочник по математике для научных работников и инженеров. Определения, теоремы, формулы, Под ред. И. Араманович.— М.: «Наука», 1978.

40. Agner Fog. How to optimize for the Pentium family of microprocessors: Ph.D. thesis. 2004.

41. Franklin C. Crow. The aliasing problem in computer-generated shaded images // Commun. ACM. 1977.- Vol. 20, no. 11.- Pp. 799-805.

42. M. Unser. Sampling-50 years after Shannon // Proceedings of the IEEE.— 2000.— Vol. 88, no. 4. {http://ieeexplore.ieee.org/ xpls/absall.jsp?arnumber=843002}.

43. Paul S. Heckbert, С Fl Paul S. Heckbert. Fundamentals of Texture Mapping and Image Warping: Tech. rep.: 1989.

44. Turner Whitted. An improved illumination model for shaded display // Commun. ACM. 1980.- Vol. 23, no. 6,- Pp. 343-349.

45. David Kirk, James Arvo. Unbiased sampling techniques for image synthesis // SIGGRAPH '91: Proceedings of the 18th annual conference on Computer graphics and interactive techniques. — New York, NY, USA: ACM, 1991.-Pp. 153-156.

46. Don P. Mitchell. Generating antialiased images at low sampling densities // SIGGRAPH '87: Proceedings of the 14th annual conference on Computer graphics and interactive techniques. — New York, NY, USA: ACM, 1987,-Pp. 65-72.

47. Б.Х. Барладян, А.Г. Волобой, B.A. Галактионов, Э.А. Копылов. Эффективный оператор сжатия динамического диапазона яркостей // Программирование. — 2004. — № 5. — С. 35-42.

48. Solomon Boulos, Dave Edwards, J. Dylan Lacewell, Joe Kniss et al. Interactive Distribution Ray Tracing: Tech. rep.: 2006.

49. Ryan Overbeck, Ravi Ramamoorthi, William R. Mark. A Real-time Beam Tracer with Application to Exact Soft Shadows // Eurographics Symposium on Rendering. — 2007. — Jun.

50. James T. Kajiya. The rendering equation // SIGGRAPH '86: Proceedings of the 13th annual conference on Computer graphics and interactive techniques. New York, NY, USA: ACM, 1986,- Pp. 143-150.

51. James Arvo. Stratified sampling of spherical triangles // SIGGRAPH '95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques. — New York, NY, USA: ACM, 1995.— Pp. 437-438.

52. Per H. Christensen, Per H. Henrik Wann Jensen, Toskiaki Kato, Frank Suykens. A Practical Guide to Global Illumination Using Photon Mapping // SIGGRAPH 2002 Course Notes / Association for Computing Machinery. ACM SIGGRAPH, 2002. - August. - Course 43.

53. Pat Hanrahan, David Salzman, Larry Aupperle. A rapid hierarchical ra-diosity algorithm // SIGGRAPH '91: Proceedings of the 18th annual conference on Computer graphics and interactive techniques. — New York, NY, USA: ACM, 1991,- Pp. 197-206.

54. Abhijeet Ghosh, Wolfgang Heidrich. Correlated visibility sampling for direct illumination 11 Vis. Comput. — 2006. — Vol. 22, no. 9. — Pp. 693-701.

55. Petrik Clarberg, Tomas Akenine-Moller. Exploiting Visibility Correlation in Direct Illumination // Computer Graphics Forum (Proceedings of EGSR 2008). — 2008. — Vol. 27, no. 4.-Pp. 1125-1136.

56. Vincent Pegoraro, Carson Brownlee, Peter S. Shirley, Steven G. Parker. Towards Interactive Global Illumination Effects via Sequential Monte Carlo Adaptation // Proceedings of the 3rd IEEE Symposium on Interactive Ray Tracing. 2008. - Pp. 107-114.

57. Toshiya Hachisuka, Wojciech Jarosz, Richard Peter Weistroffer, Kevin Dale et al. Multidimensional Adaptive Sampling and Reconstruction for

58. Ray Tracing I I ACM Transactions on Graphics (Proc. of SIGGRAPH). — 2008.-08/2008.-Vol. 27.

59. Alexander Keller. Instant radiosity // SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniques. — New York, NY, USA: ACM Press/Addison-Wesley Publishing Co., 1997.-Pp. 49-56.

60. Ingo Wald, Carsten Benthin, Philipp Slusallek. Interactive Global Illumination Using Fast Ray Tracing // Rendering Techniques 2002 (Proceedings of the Thirteenth Eurographics Workshop on Rendering). — 2002. — June.

61. Carsten Benthin, Ingo Wald, Philipp Slusallek. A Scalable Approach to Interactive Global Illumination // Computer Graphics Forum. — 2003.— September. Vol. 22, no. 3. — Pp. 621-630.

62. Franklin C. Crow. Shadow Algorithms for Computer Graphics // Computer Graphics. 1977.-July. - Vol. 11, no. 2.- Pp. 242-248.

63. Ulf Assarsson, Tomas Akenine-Moller. A geometry-based soft shadow volume algorithm using graphics hardware // ACM Trans. Graph. — 2003.-Vol. 22, no. 3.-Pp. 511-520.

64. Samuli Laine, Timo Aila, Ulf Assarsson, Jaakko Lehtinen, Tomas Akenine-Moller. Soft Shadow Volumes for Ray Tracing // ACM Transactions on Graphics. — 2005. — Vol. 24, no. 3. — Pp. 1156-1165.

65. Jaakko Lehtinen, Samuli Laine, Timo Aila. An Improved Physically-Based Soft Shadow Volume Algorithm // Computer Graphics Forum. 2006. - Vol. 25, no. 3. - Pp. 303-312.

66. Lance Williams. Casting Curved Shadows on Curved Surfaces // Computer Graphics. — 1978.— August. — Vol. 12, no. 3. — Pp. 270-274.

67. Gael Guennebaud, Loic Barthe, Mathias Paulin. Real-time soft shadow mapping by backprojection I I Eurographics Symposium on Rendering (EGSR), Nicosia, Cyprus, 26/06/2006-28/06/2006. http://www.eg.org/: Eurographics, 2006. — Pp. 227-234.

68. Michael Schwarz, Marc Stamminger. Bitmask Soft Shadows // Comput. Graph. Forum. — 2007. — Vol. 26, no. 3.- Pp. 515-524.

69. Per H. Christensen, Dana Batali. An Irradiance Atlas for Global Illumination in Complex Production Scenes // Proceedings of Eurographics Symposium on Rendering 2004 / Ed. by A. Keller, H. W. Jensen. — 2004.-June.-Pp. 133-141.

70. Henrik Wann Jensen. A Practical Guide to Global Illumination Using Photon Mapping // SIGGRAPH 2001 Course Notes / Association for Computing Machinery. — ACM SIGGRAPH, 2001. — August. — Course 38.

71. Hayden Landis. Production-ready global illumination // SIGGRAPH 2002 Course Note 16 RenderMan in Production. — 2002. — Pp. 87-102.

72. Martin Mittring. Finding next gen: CryEngine 2 // SIGGRAPH '07: ACM SIGGRAPH 2007 courses. New York, NY, USA: ACM, 2007. -Pp. 97-121.

73. P.P. Sloan, J. Kautz, J. Snyder. Precomputed radiance transfer for realtime rendering in dynamic, low-frequency lighting environments II ACM Transaction on Graphics. — 2002. — Vol. 21, no. 3.— Pp. 527-536.

74. J. Kautz, P. Sloan, J. Snyder. Fast, arbitrary BRDF shading for low-frequency lighting using spherical harmonics. — 2002. citeseer. ist. psu. edu/kautz02fast.html.

75. R. Ng, R. Ramamoorthi, P. Hanrahan. Triple product wavelet integrals for all-frequency relighting // ACM Transactions on Graphics (TOG).— 2004. Vol. 23, no. 3. - Pp. 477^187.

76. P. Green, J. Kautz, W. Matusik, F. Durand. View-dependent precomputed light transport using nonlinear Gaussian function approximations // Symposium on Interactive 3D Graphics and Games. — 2006. — Pp. 7-14.

77. Кип Xu, Yun-Tao Jia, Hongbo Fu, Shimin Ни, Chiew-Lan Tai. Spherical Piecewise Constant Basis Functions for All-Frequency Precomputed Radiance Transfer // IEEE Transactions on Visualization and Computer Graphics. — 2007.

78. Bruce Walter, George Drettakis, Steven G. Parker. Interactive Rendering using the Render Cache // Rendering Techniques / Ed. by D. Lischinski, G. W. Larson. Springer, 1999.- Pp. 19-30.

79. Bruce Walter, George Drettakis, Donald P. Greenberg. Enhancing and Optimizing the Render Cache // Eurographics Workshop on Rendering / Ed. by P. Debevec, S. Gibson. — Springer-Verlag, 2002.

80. Gregory J. Ward, Paul Heckbert. Irradiance Gradients. — 1992. — May. — Pp. 85-98.

81. Eric Tabellion, Arnauld Lamorlette. An approximate global illumination system for computer generated films // ACM Trans. Graph. — 2004.— Vol. 23, no. 3. Pp. 469-476.

82. Jaroslav Krivanek. Radiance Caching for Global Illumination Computation on Glossy Surfaces: Ph.d. thesis / Universite de Rennes 1 and Czech Technical University in Prague. — 2005.— December, http: //www.egg.cvut.cz/~havran/dissertation/index.htm.

83. Jaroslav Krivanek, Pascal Gautron, Kadi Bouatouch, Sumanta Pattanaik. Improved radiance gradient computation // SCCG '05: Proceedings of the 21st spring conference on Computer graphics. — New York, NY, USA: ACM Press, 2005.- Pp. 155-159.

84. Ravi Ramamoorthi, Dhruv Mahajan, Peter Belhumeur. A First Order Analysis of Lighting, Shading, and Shadows // ACM Transactions on Graphics. — 2007. — Jan. — Vol. 26, no. 1.

85. Okan Arikan, David Forsyth, James F. O'Brien. Fast and Detailed Approximate Global Illumination by Irradiancc Decomposition // ACM SIGGRAPH 2005 Full Conference DVD-ROM.- 2005.-August.

86. Jonathan T. Moon, Stephen R. Marschner. Simulating multiple scattering in hair using a photon mapping approach // ACM Trans. Graph. — 2006.-Vol. 25, no. 3.-Pp. 1067-1074.

87. Wojciech Jarosz, Craig Donner, Matthias Zwicker, Henrik Wann Jensen. Radiance caching for participating media II ACM Transactions on Graphics. 2008. - March. - Vol. 27, no. 1. - Pp. 1-11.

88. Peter Shirley, Kenneth Chiu. A Low Distortion Map Between Disk and Square // journal of graphics tools. — 1997. — Vol. 2, no. 3. — Pp. 45-52.

89. Larry Seiler, Doug Carmean, Eric Sprangle, Tom Forsyth et al. Larrabee: a many-core x86 architecture for visual computing // ACM Transactions on Graphics. — 2008. — August. — Vol. 27, no. 3.- Pp. 18:1-18:??95. www.integra.jp/en/inpirer/index.html.У