Введение

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

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

Научная значимость

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

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

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

Различают прямую и обратную трассировку лучей.

Прямая трассировка лучей очень неэффективна из-за того, что начальная точка луча – источник света.

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

Рисунок 1 - Модель алгоритма трасировки лучей (анимация, 7 кадров, 79КБ)

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

Разработка алгоритмов межпиксельной интерполяции для ускорения алгоритма трассирования лучей.
Для оптимизации алгоритма трассировки лучей возможно:

1. ускорить анализ пересечения луча/объекта;
2. разпаралелить часть задач.

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

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

Очевидно, что смежные пиксели трассируемого изображения имеют приблизительно одинаковый цвет. На практике, сцена средней загруженности, имеет около 70% пиксельных сегментов (области пикселей, которые различаются по цвету менее чем на 1 % (Рисунок 2)) и приблизительно только 8% крайних областей (области пикселей, которые различаются по цвету более чем на 25 %). Эти данные приведены для того, чтобы показать – большая часть времени тратится на обработку пикселей с приблизительно одинаковым цветом. Идея и состоит в изменении этой ситуации.

Рисунок 2 - Линейная интерполяция ряда пикселей

Хотя длина сегмента на практике может меняться, чаще всего, она составляет 4-6 пикселей, поэтому применение сложных методов интерполяции не целесообразно, и поэтому в этой работе вычисление цвета внутренних пикселей будет выполняться по формуле 1:

Pinner = (Pleft + Pright )/2 (1)

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

Таким образом, основная идея модификации алгоритма трассирования состоит в следующем:

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

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

Блочная межпиксельная интерполяция
Введем соглашения исходя из структуры аппаратного обеспечения:

1. каждому пикселю изображения назначают свой процессорный элемент (PE) (возможно виртуальный);
2. два смежных PE вычисляют крайние пиксели одного сегмента;
3. у каждого PE есть идентификатор, который меняется в пределах от 0 до Nmax;
4. все процессорные элементы имеют идентичную структуру

Рассмотрим изображение 1024 на 1024 пикселей, и предположим, что каждому пикселю назначался свой процессорный элемент. Выходит огромное число процессоров (1 058 576). Что совсем не приемлемо. Таким образом, применение вышеупомянутого метода, взяв блоки 4 на 4 полностью обосновано.

Самое оптимальное решение интерполировать не строки, а блоки размером 4 на 4 пикселя (рисунок 3).

Рисунок 3 - Пример блоковой интерполяции 4 на 4 пикселя

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

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

Практическая ценность
Увеличение производительности системы происходить за счет аппаратных затрат.

Общее количество процессоров для блочной интерполяции может быть рассчитано как:

PE_блочная_интерполяция = (int [( n-1) / (k+1)] +1) ^ 2

Для картинки 1024 на 1024 пикселя, трассируемой блоками 4 на 4 пикселя:

PE_блочная_интерполяция = ([( 1024-1) / (2+1)]+1 ) 2 = 116 964

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

Сегодня технология трассирования лучей применяется изза трудоемкость только корпорациями, подразделами, которые специализируются на создании спец эффектов для кинофильмов, на создании мультипликационных фильмов. Так же эта технология довольно сильно распространена в сфере работы с трехмерной графикой, где нужно только синтезировать один кадр, одну сцену, технология используется для получения высококачественных изображений в программном обеспечении, таком как Maya, 3D Max, Autodesk.

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

Рисунок 4 - Сравнительная характеристика GPU/CPU

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

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

Рисунок 5 - Програмная реализация алгоритма трассировки лучей (анимация, 5 кадров, 150КБ)

Обзор исследований по теме в ДонНТУ

В ДонНТУ тему ускорения алгоритма трассировки лучей рассматривает Иванова Екатерина Владимировна.

Обзор исследований по теме в Украине

К сожалению, в Украине ни в одном ВУЗе тема ускорения алгоритма трассировки лучей не рассматривалась.

Обзор исследований по теме в мире

Методами оптимизации и ускорения алгоритма трассировки лучей для получения фото реалистических изображений занимаются мировые известные компании, которые специализируются на разработке визуальных эффектов, созданию мультфильмов (PIXAR), компании, которые специализируются на разработке аппаратного обеспечения для ПК (INTEL, nVidia, AMD), компании, которые специализируются на разработке специализированного компьютерного оборудования (Caustic, Splutterfish).

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

INTEL предлагает использование инструкций пакетной обработки данных SSE 1,2,3,4,5+ для ускорения работы с набором(пакетом) данных (векторов).

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

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

nVidia пошла своим путем. Так как корпорация специализируется на выполнении мощных видео чипов, построенных на конвейерной структуре с многочисленным количеством параллельно работающих блоков (высокопроизводительная серия чипов GeForce Quadro/Tesla), которые выполняют операции над отдельными пикселями и треугольниками, то есть фактически входными данными для этих блоков является набор векторов, а формат чисел – QFLOAT (128 бит), был создан движок OptiX Engine. Движок основан на использовании языка HLSL (язык так называемых шейдеров, микропрограмм для вычислительных блоков), технологии CUDA, которая позволяет разпаралеливать вычисления на одном графическом чипе, основываясь на конвейерной структуре с параллельно работающими вычислительными блоками. Для сравнения, если программный метод рэндэринга сцены занимает несколько минут, то аппаратный ( с использованием решений nVidia / CUDA / OptiX) занимает значительно меньшее время.

Аналогичной разработкой может похвастаться и AMD. Их разработка называется AMD Cinema 2.0. Базовой платформой для этой разработки является движок OTOY (продукт сотрудничества AMD, Otoy, Lightscape). «Cinema 2.0» является средством, которое обеспечивают расчет трассировки лучей в реальном времени на графических процессорах Radeon (серии чипов v7x0, v8x0, старшие модели этих чипов имеют вычислительную мощность порядка 1 TFLOP при работе с числами формата QFLOAT) и центральных процессорах AMD Phenom.

Корпорация Caustic предоставила готовый OpenGL и GLSL API, кросплатформенный Openrl SDK, который стал стандартом для разработки комплексных решений с использованием синтеза изображений с помощью технологии трассирования лучей. Также Coustic предоставила первое в мире, узконаправленное аппаратное решение CausticOne, которое позволяет синтезировать изображение с использованием набора библиотек OpenRL до 20 раз быстрее, чем современные GPU и CPU.

Splutterfish разработала свою систему рэндэринга изображения Brazil r/s (Brazil Rendering System). Brazil r/s основной продукт Splutterfish, реализованный как плагин к Autodesk, 3ds Max, Rhinoceros, Autodesk Maya, и как отдельный модуль standalone. На коммерческой основе в настоящее время доступна только версия для 3ds Max, в то время как Rhino 3D доступна в открытом бета тестирования через Mcneel and Associates. Brazil r/s- это рей-трейсерний рендер, в котором присутствуют алгоритмы просчета глобального освещения Global Illumination: QMC и Photon Mapping. Эту систему использовала компания Lucas Arts при создании эффектов к кинофильму «Заряне войны 3».

ВЫВОД

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

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

Как видно из примера расчета КПД алгоритма с применением блочной интерполяции, для изображения размером 1024 на 1024 пикселей нужно приблизительно в семь раз меньше аппаратных блоков, ускорение рэндэринга сцены достигает значения 4-5 раз, которое обусловлено не достаточным быстрым доступом к памяти.

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

Список использованной литературы

1. Malcheva R.V. The problems of modeling and rendering of the realistic complex scenes / R.V. Malcheva, S. Kovalov, U. Korotin // Сборник трудов VII МНТК «Машиностроение и техносфера XXI века. – Донецк: ДонГТУ, 2000. - С.308-310.
2. Malcheva R.V. The problems of modeling and rendering of the realistic complex scenes / R.V. Malcheva // Proceedings of ECCPM 2002. - Portoroz, 2002. - PP.537-538.
3. Серёженко А.А. Оптимизация метода трассировки лучей / А.А. Серёженко // Збірка матеріалів п’ятої міжнародної науково-технічної конференції студентів, аспірантів та молодих науковців. – Донецк: ДонНТУ, Т2, 2009 - с. 71-74.
4. Роджерс Д. Математические основы машинной графики. Пер. с англ. / Д. Роджерс, Дж. Адамс / Под ред. Ю.И.Топчеева.- М.: Машиностроение,1980 234 с.
5. Эгрон Ж. Синтез изображений. Базовые алгоритмы. / Ж. Эгрон. - М.: Радио и связь. - 1993. - 216 с.
6. Корреган Д. Компьютерная графика. Секреты и решения. / Д. Корреган - М., 1995 - 345 с.
7. Шикин Е.В. Начала компьютерной графики. / Е.В.Шикин, А.В.Боресков, А.А.Зайцев. - М.: ДИАЛОГ-МИФИ. - 1993.- 138 с.
8. SplutterFish: Brazil Rendering System for 3ds Max [электронный ресурс] - режим доступа - http://splutterfish.com
9. Caustic Graphics - Reinventing realtime ray tracing with OpenRL SDK built on OpenGL and GLSL APIs [электронный ресурс] http://www.caustic.com/
10. Cinema 2.0: The Next Chapter in the Ultimate Visual Experience - [электронный ресурс] - http://www.amd.com/us-en/Corporate/AboutAMD/0,,51_52_15438_15106,00.html?redir=cin01
11. nVidia OptiX: Application Acceleration Engine - [электронный ресурс] - http://www.nvidia.com/object/optix.html
Куликов А.И., Овчинникова Т.Э. Метод трассировки лучей / Интернет университет информационных технологий intuit.ru - [электронный ресурс] - http://www.intuit.ru/department/graphics/graphalg/6/5.html
12. Codermind team A ray tracer in C++ - [электронный ресурс] - http://www.codermind.com/articles/Raytracer-in-C++-Introduction-What-is-ray-tracing.html
13. Implementation Ray Tracing on GPU - [электронный ресурс] - http://www.clockworkcoders.com/oglsl/rt/gpurt1.htm