Содержание

1. Введение
2. Актуальность темы
3. Цель и задачи исследования
4. Обзор исследований и разработок
   1. Обзор международных источников
      1. Теоретические основы алгоритмов трассировки лучей
      2. Алгоритмы трассировки лучей
      3. Отображение алгоритмов трассировки лучей на параллельную архитектуру GPU
      4. Ускоряющие техники
   2. Обзор национальных источников
   3. Обзор локальных источников
5. Выводы
6. Список источников

1. Введение

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

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

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

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

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

3. Цель и задачи исследования

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

В работе решаются следующие задачи:

• Анализ существующих алгоритмов трассировки лучей и их характеристик;
• Анализ существующих техник ускорения трассировки лучей;
• Анализ способов реализации алгоритмов трассировки лучей и ускоряющих техник на SIMD-архитектурах вычислительных систем;
• Модификация алгоритма трассировки лучей и его отображение на архитектуру GPU с поддержкой технологии CUDA

Объект исследования: алгоритмы трассировки лучей.

Предмет исследования: повышение эффективности алгоритмов трассировки лучей и их параллельная реализация на архитектуре GPU-CUDA.

4. Обзор исследований и разработок

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

1. Усовершенствование алгоритмов трассировки лучей;
2. Разработка специализированного аппаратного обеспечения;
3. Повышение производительности аппаратного обеспечения общего назначения

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

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

Актуальной также является классификация [1], предложенная Джеймсом Арво (James Arvo) и Дэвидом Кирком (David Kirk) (рис. 1). Данная классификация может рассматриваться в качестве детализации первого пункта варианта классификации, приведённого выше.

4.1 Обзор международных источников

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

4.1.1 Теоретические основы алгоритмов трассировки лучей

Пусть картинная плоскость является частью визуализируемой сцены и обозначена Μ_s. Интенсивность канала λ_c j-го пикселя синтезируемого изображения, которому в соответствие поставлена некоторая область Μ_j картинной плоскости определяется следующим уравнением [2]:

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

• Μ_j — множество точек картинной плоскости, соответствующих j-му пикселю изображения;
• S² — множество точек, лежащих на поверхности сферы единичного радиуса (каждая точка задаёт направление падающего освещения);
• Λ_c — множество длин волн, соответствующих каналу λ_c изображения, является подмножеством множества длин волн видимого спектра электромагнитного излучения, Λ_c∈Λ

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

• L_i(x ω_i, λ) — энергетическая яркость освещения с длиной волны λ, падающего на точку x∈Μ_j j-го пикселя в направлении -ω_i;
• (x ω_i, λ) — функция отклика j-го пикселя на падающее освещение, масштабирующая значение функции L_i(xω_i, λ);
• θ_i — угол между нормалью картинной плоскости в точке x и вектором ω_i;
• Α(x) — мера площади, заданная на множестве Μ_j;
• σ(ω_i) — мера площади, заданная на множестве S² (так как сфера S² имеет единичный радиус, то данная мера определяет величину телесного угла);
• dλ — дифференциальная мера длины, заданная на множестве Λ_c

В уравнении (1) неизвестной является функция L_i(x ω_i, λ). Для нахождения значения данной функции необходимо решить уравнение, впервые предложенное в работе [3], уравнение визуализации (уравнение светотранспорта), которое в более общем случае имеет следующий вид:

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

• L_o(x ω_o, λ) — энергетическая яркость освещения с длиной волны λ, исходящего из точки x∈Μ в направлении ω_o, где Μ обозначает множество точек всех поверхностей сцены;
• L_e(x ω_o, λ) — энергетическая яркость освещения с длиной волны λ, излучаемой точкой x в направлении ω_o;
• f_s(x, ω_i ω_o, λ) — BSDF (Bidirectional Scattering Distribution Function), определяет часть световой энергии с длиной волны λ, перенесённой в точку x из направления ω_i, которая будет отражена в направлении ω_o;
• r_Μ(x, ω_i) — функция, которая возвращает первую точку пересечения луча, исходящего из точки x в направлении ω_i, с поверхностями Μ визуализируемой сцены

Уравнение (2) является интегральным уравнением второго порядка, так как неизвестная функция L_o(x ω_o, λ) встречается и под знаком интеграла, и вне интегрального оператора. В основе уравнения (2) лежит следующее утверждение: в случае отсутствия препятствий, с которыми фотоны могли бы взаимодействовать, энергетическая яркость на пути от одной поверхности к другой не меняется, то есть L_i(x ω_i, λ)=L_o(r_Μ(x, ω_i). Таким образом, уравнение (2) предполагает, что фотоны могут взаимодействовать только с поверхностями сцены, но не с пространством внутри или вокруг них. Другими словами, поверхности сцены со всех сторон окружены вакуумом.

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

4.1.2 Алгоритмы трассировки лучей

В частном случае, например, когда визуализируемая сцена состоит лишь из источников освещения (в данном случае интегральный оператор в правой части уравнения (2) пропадает полностью) или при расчёте прямого освещения (поверхности, излучающие свет, известны заранее, следовательно L_o(r_Μ(x, ω_i) -ω_i, λ)=L_e(r_Μ(x, ω_i) -ω_i, λ) для всех точек x, лежащих на поверхности источников освещения, для других поверхностей можно принять L_o(r_Μ(x, ω_i) -ω_i, λ)=0 или заменить в области интегрирования S² множеством точек на поверхности источников освещения) уравнение (2) может быть решено аналитически. В общем случае для решения уравнения используются численные методы, которые позволяют найти частичное решение. Различные алгоритмы трассировки лучей предназначены для поиска частичного решения уравнения (2).

Классическим считается алгоритм обратной трассировки лучей, предложенный Уиттедом Тёрнером (Whitted Turner) в работе [5]. Алгоритм заключается в проецировании пикселей конечного изображения на картинную плоскость с последующей трассировкой луча через центр каждого пикселя для определения соответствующего отклика (интенсивности) j-го пикселя. Каждый шаг трассировки луча предполагает нахождение ближайшего пересечения луча со всеми поверхностями сцены с последующим расчётом прямого освещения по локальной модели освещения Фонга и добавлением отражённого и преломлённого компонентов. Таким образом, в каждой точке x пересечения луча с поверхностью расчёт модели глобального освещения по Уиттеду выглядит следующим образом:

Обозначения, использованные в уравнении (3) имеют следующий смысл:

• I — интенсивность освещения;
• k — коэффициент масштабирования интенсивности освещения;
• N — количество источников освещения;
• v(x, ω_i) — функция, принимающая значение 1, если луч (x, ω_i) не пересекает поверхности сцены, и 0 в противном случае

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

• a — имитация непрямого (ambient) освещения в точке;
• d — прямое рассеянное (diffuse) освещения в точке;
• l — источник освещения (light source);
• r — зеркальное отражение (reflection);
• t — зеркальное преломление (transmittance)

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

Ниже приведена анимация, демонстрирующая процесс решения проблемы освещения с помощью алгоритма Уиттеда (рис. 2). На рисунке, в зависимости от используемой модели освещения, объекты отмечены символами D (diffuse, рассеянное) и S (specular, зеркальное), а индексы r и t означают, соответственно, отражения и преломления. Источники освещения обозначены символом L (light). Первичные лучи имеют зелёный цвет, теневые (shadow feelers) — чёрный, отражённые — синий, преломлённые — фиолетовый. На рисунке 2 также отмечены проекции точек пересечения теневых лучей с поверхностями сцены (в трёхмерном пространстве).

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

В работе [3] предложен алгоритм трассировки путей (Path tracing), основу которого составляет идея о том, что наибольший вклад в оценку энергетической яркости вносят первичные и теневые лучи, то есть, лучи, лежащие в начале и в конце пути между источником освещения и сенсором. Так как и классический алгоритм трассировки лучей, и его расширенный стохастический вариант, распределённая трассировка лучей (Distributed/Distribution ray tracing) [6], строят дерево лучей, включающее в себя в основном промежуточные лучи, то вычислительные ресурсы расходуются напрасно (на расчёт освещения, которое, по сравнению с первичным, обычно слабо влияет на итоговый результат).

4.1.3 Отображение алгоритмов трассировки лучей на параллельную архитектуру GPU

В основе архитектуры GPU лежит принцип SIMD-вычислений, который предполагает параллельное исполнение одной инструкции множеством потоковых процессоров, каждый из которых обрабатывает собственный элемент входного потока данных. За счёт высокой степени параллелизма, а также традиционной ориентации на использование в графических приложениях, которые требуют быстрых вычислений с плавающей точкой, суммарная производительность GPU (в частности, при исполнении линейного кода) существенно превосходит CPU. Ниже приведён график [7], отражающий сравнительную динамику изменения производительности разных поколений GPU от Nvidia и архитектур CPU от Intel за последние тринадцать лет (рис. 3). На графике заметен линейный, а затем практически экспоненциальный рост производительности GPU. Даже без учёта других важных факторов, это можно объяснить, сравнив количество вычислительных ядер у GeForce 8800 GTX (575 [8]) и у GeForce GTX 780 Ti (2880 [9]), обозначенных на графике.

Несмотря на то, что GPU традиционно ориентированы на использование в графических приложениях (выполнения растеризации потока треугольников), существует множество техник и технологий применения GPU для решения неграфических задач, которые объединены общим названием GPGPU (General-purpose computing on GPU). Простейшие техники GPGPU могут заключаться, например, в нестандратной интерпретации значений элементов текстур (матриц), обрабатываемых GPU [10]. Однако подобный подход не позволяет выйти за рамки станартного графического конвейера, который налагает множество ограничений на программы, исполняемые на GPU. Например, шейдерные программы (вершинные, пиксельные), исполняемые для каждого элемента потока данных, не могут обмениваться информацией.

Данная магистерская работа предполагает использование программно-аппаратной GPGPU технологии CUDA для ускорения процесса визуализации методами трассировки лучей. Здесь же следует отметить, что в контексте CUDA используется понятие SIMT-вычислений (вообще говоря, модель SIMT-вычислений используется и другими программными платформами для параллельного программирования, например, OpenCL), отличие которых от SIMD на уровне кода заключается в возможности написания кода для отдельных нитей как самостоятельных программ, а не одной программы для параллельной обработки всего вектора данных. Таким образом, пропадает необходимость явно указывать ширину вектора данных в программе и вручную контролировать, какая часть вектора при ветвлении кода будет обрабатываться, а какая нет [7].

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

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

В работе [11] рассмотрены способы повышения степени утилизации варпов для первого из перечисленных варианта расхождения потока выполнения нитей. Автор даёт сравнительную характеристику трёх вариантов реализации алгоритма стохастической трассировки путей.

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

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

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

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

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

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

4.1.4 Ускоряющие техники

Методы ускорения оценки непрямого освещения за счёт фильтрации шумов предложены в работах [13-15]. За счёт фильтрации вторичного освещения с соблюдением контуров объектов (что в указанных работах выполняется разными способами), возможно использование меньшего количества сэмплов вторичного освещения, благодаря чему сокращается общее время, затрачиваемое на синтез визуально приемлемого (различимого) изображения.

В работе [16] предложена организация гибридного графического конвейера, комбинирующего техники визуализации, основанные на принципах растеризации и трассировки лучей (точнее, алгоритма нерекурсивной трассировки, ray casting). Интересно отметить, что доминирующим элементом в конвейере являются именно растеризационные техники, с помощью которых приближённо рассчитывается локальное освещение (без теней, с помощью модели Фонга), тени (с помощью карт теней) и часть непрямого освещения (рассеянное, с помощью Light Propagation Volumes), в то время как трассировка лучей используется исключительно для расчёта зеркальных отражений и преломлений. Преимущество конвейера сравнительно с полной трассировкой изображения заключается в том, что трассировка лучей выполняется только для видимых частей поверхностей, имеющих материал, который обладает отражающими и/или преломляющими свойствами, что позволяет избежать трассировки всех пикселей изображения. С другой стороны, возможны ракурсы обзора сцены, при которых такие поверхности будут занимать всю картинную плоскость, в результате чего придётся выполнять трассировку всего изображения целиком. Кроме того, возникает задача согласования результатов работы каждой техники визуализации (например, алгоритм ray casting не способен рассчитать рассеянное освещение, в то время как на стадии растеризации оно добавляется).

4.2 Обзор национальных источников

В работе Шатовской Т. Б. и Кудлай С. Ю. из харьковского национального университета радиоэлектроники [17] рассмотрены современные GPGPU-технологии, а также представлены сравнительные результаты оценки эффективности реализаций классического алгоритма трассировки лучей на CPU и GPU (с использованием технологии CUDA). Общее время, затраченное на визуализацию сцены в одном потоке на CPU, в 89 раз превысило время трассировки на GPU, подтверждая таким образом эффективность последнего варианта реализации алгоритма.

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

4.3 Обзор локальных источников

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

Иванова Е. В. рассматривает применимость GPU с поддержкой технологии CUDA для ускорения алгоритмов трассировки лучей, а также приводит оценку перспектив развития GPU и CPU [20].

Гуров А. В. приводит анализ метода ускорения поиска пересечений лучей с поверхностями сцены при помощи kd-дерева [21].

В исследовании Каламитры М. В. проанализированы основные алгоритмы трассировки лучей и их модификации [22]. Для синтеза физически точных изображений предложено использовать алгоритмы Distribution ray tracing, Photon mapping, Bidirectional path tracing и Metropolis light transport. В работе также рассмотрены способы отображения алгоритмов трассировки лучей на параллельную архитектуру GPU.

Запорожченко И. А. исследует алгоритм 3DDA обхода регулярной сетки и влияние данной ускоряющей техники на скорость поиска пересечения луча с поверхностями сцены [23]. Множество поверхностей визуализируемой сцены включает сферы и кубы. В работе показано, что при фиксированном количестве сфер, распределение эффективности ускоряющей техники близко к нормальному.

5. Выводы

Выполнен обзор базовых алгоритмов визуализации виртуальных пространственных сцен, использующих принцип трассировки лучей. Классическим считается алгоритм обратной трассировки лучей, предложенный в работе [5]. Для расширения диапазона эффектов, моделируемых классическим алгоритмом, в работе [6] предложен алгоритм Distributed (distribution) ray tracing, а в [3], для повышения скорости синтеза изображения сцены, предложен алгоритм Path tracing.

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

Рассмотрены особенности отображения алгоритмов трассировки лучей на параллельную архитектуру GPU с привязкой к технологии CUDA. В конечном счёте, основной проблемой является недостаток памяти, так как степень параллелизма зависит от количества регистровой и разделяемой памяти, задействованной каждой нитью.

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

• Разработка оптимизированного алгоритма трассировки лучей c улучшенными временными характеристиками;

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

• Оценка эффективности реализации

6. Список источников

1. A survey of ray tracing acceleration techniques / James Arvo, David Kirk // An introduction to ray tracing. — London, UK: Academic Press Ltd., 1989. — С. 201-262.
2. Robust Monte Carlo Methods for Light Transport Simulation : / Veach Eric. — Stanford University, 1998.
3. The Rendering Equation / James T. Kajiya // Proceedings of the 13th Annual Conference on Computer Graphics and Interactive Techniques: SIGGRAPH ’86. — New York, NY, USA: ACM, 1986. — С. 143-150
4. Retro-rendering with vector-valued light: Producing local illumination from the transport equation / Banks D. C., Beason K. M. // Proceedings of SPIE, the International Society for Optical EngineeringSociety of Photo-Optical Instrumentation Engineers, 2006. — С. 60600C.1-60600C.7
5. An improved illumination model for shaded display / T. Whitted // ACM SIGGRAPH Computer Graphics. — 1979. — Т. 13, № 2. — С. 343-349
6. Distributed ray tracing / Cook R. L., T. Porter, L. Carpenter // ACM SIGGRAPH Computer Graphics: Т. 18ACM, 1984. — С. 137-145
7. CUDA C Programming Guide
8. GeForce 8800 GTX Specifications [Электронный ресурс] — Режим доступа: http://www.geforce.com/hardware/desktop-gpus/geforce-8800-gtx/specifications
9. GeForce GTX 780 Ti Specifications [Электронный ресурс] — Режим доступа: http://www.geforce.com/hardware/desktop-gpus/geforce-gtx-780-ti/specifications
10. Основы работы с технологией CUDA / Боресков А. В., Харламов А. А. — ДМК Пресс, 2010. — 232 с.
11. Active Thread Compaction for GPU Path Tracing / I. Wald // Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics: HPG ’11. — New York, NY, USA: ACM, 2011. — С. 51-58
12. Stackless Multi-BVH Traversal for CPU, MIC and GPU Ray Tracing / Áfra A. T., L. Szirmay-Kalos // Computer Graphics Forum. — 2014. — Vol. 33, № 1. — С. 129-140
13. Guided Image Filtering for Interactive High-quality Global Illumination / P. Bauszat, M. Eisemann, M. Magnor // Computer Graphics Forum: Т. 30Wiley Online Library, 2011. — С. 1361-1368
14. Practical Noise Reduction for Progressive Stochastic Ray Tracing with Perceptual Control / K. Schwenk, A. Kuijper, J. Behr, Fellner D. W. // IEEE Computer Graphics and Applications. — 2012. — Т. 32, № 6. — С. 46-55
15. Ускорение расчёта вторичного освещения с помощью фильтрации в пространстве экрана и уточнения на основе информации о близлежащей геометрии / Груздев А. М., Фролов В. А., Игнатенко А. В., 2012. — С. 269-272
16. Combining Rasterization and Ray Tracing Techniques to Approximate Global Illumination in Real-Time / J. Cabeleira
17. Використання технологій загальних обчислень на графічних процесорах для прискорення синтезу тривимірних зображень методом зворотного трасування променів / Кудлай С. Ю., Шатовська Т. Б. // октябрь. — 2012
18. Геометрическое моделирование процесса освещения / Дашкевич А. А., Анисимов К. В. // Вестник Национального Технического Университета Харьковский Политехнический Институт. Серия: Информатика И Моделирование. — 2013. — № 19 (992).
19. Разработка ускоренного алгоритма трассировки лучей [Электронный ресурс] / Серженко А. А. — Режим доступа: http://masters.donntu.ru/2010/fknt/serezhenko/diss/index.htm
20. Анализ, исследование и усовершенствование методов реалистической визуализации трёхмерных моделей объектов и сцен с применением функционального описания [Электронный ресурс] / Иванова Е. В. — Режим доступа: http://masters.donntu.ru/2010/fknt/ivanova/diss/index.htm
21. Реалистичная стерео-визуализация трёхмерных сцен методом трассировки лучей на специализированных параллельных вычислительных системах [Электронный ресурс] / Гуров А. В. — Режим доступа: http://masters.donntu.ru/2011/fknt/gurov/diss/index.htm
22. Средства фотореалистичной визуализации и их реализация на параллельных компьютерных системах [Электронный ресурс] / Каламитра М. В. — Режим доступа: http://masters.donntu.ru/2013/fknt/kalamitra/diss/index.htm
23. Анализ алгоритмов трассировки лучей для реалистичной визуализации трёхмерных сцен и способов уменьшения их вычислительной сложности / Запорожченко И. А., Григорьев М. А., Зори С. А. // ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ И ИЗОБРАЖЕНИЙ. — 2013. — С. 352-357