Гуров Алексей Владимирович
Факультет компьютерных наук и технологий
Специальность «Программное обеспечение автоматизированных систем»
Научный руководитель: доц., к.т.н. Зори Сергей Анатольевич
Реалистичная стерео-визуализация трехмерных сцен методом трассировки лучей на специализированных параллельных вычислительных системах
Алгоритм обратной трассировки лучей
Обзор существующих методов оптимизации алгоритма обратной трассировки лучей
Обзор исследований по теме в ДонНТУ
Обзор исследований по теме в мире
Введение
Развитие современной техники позволяет рассматривать на сегодняшний день построение стереоизображений как одно из наиболее перспективных направлений компьютерной графики. Возможность стереопредставления изображений порождает новые направления прикладных исследований – создание программно-аппаратных комплексов виртуальной реальности, обучающих комплексов, построение с помощью стереоизображений различных презентаций и анимаций.
Существует несколько методов генерации реалистичных изображений, таких как прямая трассировка лучей (трассировка фотонов), обратная трассировка лучей и другие.
Методы трассировки лучей на сегодняшний день считаются наиболее мощными и универсальными методами создания реалистичных изображений. Известно много примеров реализации алгоритмов трассировки для качественного отображения самых сложных трехмерных сцен. Можно отметить, что универсальность методов трассировки в значительной степени обусловлена тем, что в их основе лежат простые и ясные понятия, отражающие наш опыт восприятия окружающего мира [1].
Окружающие нас объекты обладают по отношению к свету такими свойствами:
– излучают;
– отражают и поглощают;
– пропускают сквозь себя.
Каждое из этих свойств можно описать некоторым набором характеристик.
Излучение можно охарактеризовать интенсивностью и спектром.
Свойство отражения (поглощения) можно описать характеристиками диффузного рассеивания и зеркального отражения. Прозрачность можно описать ослаблением интенсивности и преломлением.
Из точек поверхности (объема) излучающих объектов исходят лучи света. Можно назвать такие лучи первичными – они освещают все остальное. От источников излучения исходит по различным направлениям бесчисленное множество первичных лучей. Некоторые лучи уходят в свободное пространство, а некоторые попадают на другие объекты. Если луч попадает в прозрачный объект, то, преломляясь, он идет дальше, при этом некоторая часть световой энергии поглощается.
В результате действия на объекты первичных лучей возникают вторичные лучи. Некоторые из них попадают на другие объекты. Так, многократно отражаясь и преломляясь, отдельные световые лучи приходят в точку наблюдения. Таким образом, изображение сцены формируется некоторым множеством световых лучей.
Цвет отдельных точек изображения определяется спектром и интенсивностью первичных лучей источников излучения, а также поглощением световой энергии в объектах, встретившихся на пути соответствующих лучей.
Непосредственная реализация данной лучевой модели формирования изображения представляется затруднительной. Можно попробовать построить алгоритм построения изображения указанным способом. В таком алгоритме необходимо предусмотреть перебор всех первичных лучей и определить те из них, которые попадают в объекты и в камеру. Затем выполнить перебор всех вторичных лучей, и также учесть только те, которые попадают в объекты и в камеру. И так далее. Такой алгоритм называется прямой трассировкой лучей. Главный недостаток этого метода – много лишних операций, связанных с расчетом лучей, которые затем не используются.
Актуальность темы
Построение стереоизображений является достаточно актуальной задачей на сегодняшний день, так как возникает вопрос максимальной правдоподобности и реалистичности компьютерных изображений. Метод трассировки лучей строит достаточно реалистичные изображения, но человек имеет объемное зрение. Следовательно, стерео–визуализация даст более правдоподобное изображение.
На сегодняшний день реализация трассировки в реальном времени представляется затруднительной. Известны попытки создания 3D–ускорителей с аппаратной поддержкой алгоритма обратной трассировки, однако широкого распространения они не получили из–за относительно высокой цены и недостаточного быстродействия (удовлетворительная скорость построения изображения была только для изображения с разрешением 640x480).
Однако вычислительные мощности персональных компьютеров растут каждый день. В скором времени должны появиться машины, на которых алгоритм трассировки будет работать в реальном времени. Трассировка должна вытеснить другие алгоритмы ввиду явного превосходства в качестве изображения и универсальности метода. но для этого необходимо предусмотреть ускорение алгоритма и его расспаралеливание.
Практическое приминение
1) Трассировка лучей в кино:
Трассировка лучей в киноиндустрии применяется уже очень давно и стала фактически стандартным методом визуализации в этой области. Разумеется для задач кино необходим фотореалистичный рендеринг. Скорость в принципе не так важна. Бывает, что отдельные последовательности кадров рассчитываются неделями, и на обработку кадра уходит больше 1 часа (при 24 кадра/сек получается, что 1 секунда будет рендериться 24 часа).
2) Трассировка лучей в играх:
В компьютерных играх у трассировки лучей двоякое применение.
Рассчет карт освещения или лайтмапов. Обычно это делается с помощью фотонных карт, хотя есть и исключения в виде метода излучательности. Практически любая современная 3D игра использует карты освещенности. Лайтмап – это текстура, на которой освещение нарисовано. Она накладывается поверх сцены и получается, что сцена освещена.
Второе применение трассировки лучей в играх – непосредственная визуализация, попиксельный рассчет изображения каждый кадр. Примеров таких игр можно привести немного главным образом, потому что количество пикселей довольно большое и протрассировать миллион лучей 25 раз в секунду это довольно непростая задача. Уже сейчас появляются 8–ядерные машины в качестве ПК, вычислительных мощностей которых в принципе хватает для визуализации средней сцены методом обратной трассировки лучей.
3) Трассировка лучей в торговом бизнесе:
В основном речь идет о фотореалистичной визуализации. Часто некоторый товар, например, мебель имеется в нескольких вариантах. У офисных кресел может быть разная обивка, колеса или другие детали, из которых по–сути можно собрать нужное покупателю кресло. Однако заниматься этим на месте не всегда удобно. Чаще намного дешевле/проще смоделировать тот товар, который покупатель хочет видеть. С помощью метода трассировки лучей можно получить практически неотличимую от реальности картинку – то есть можно сделать фотографию товара, которого еще нет [2].
Алгоритм обратной трассировки лучей
Метод обратной трассировки лучей позволяет значительно сократить перебор световых лучей. Метод разработан в 80–х годах, основополагающими считаются работы Уиттеда и Кэя. Согласно этому методу отслеживание лучей производится не от источников света, а в обратном направлении – от точки наблюдения. Так учитываются только те лучи, которые вносят вклад в формирование изображения.
Плоскость проецирования разбита на множество пикселов. Выберем центральную проекцию с центром схода на некотором расстоянии от плоскости проецирования. Проведем прямую линию из центра схода через середину пиксела плоскости проецирования. Это будет первичный луч обратной трассировки. Если этот луч попадет в один или несколько объектов сцены, то выбираем ближайшую точку пересечения. Для определения цвета пиксела изображения нужно учитывать свойства объекта, а также то, какое световое излучение приходится на соответствующую точку объекта.
Если объект зеркальный (хотя бы частично), то строим вторичный луч – луч падения, считая лучом отражения предыдущий, первичный трассируемый луч. Для идеального зеркала достаточно затем проследить лишь очередную точку пересечения вторичного луча с некоторым объектом. У идеального зеркала идеально ровная отполированная поверхность, поэтому одному отраженному лучу соответствует только один падающий луч. Зеркало может быть затемненным, то есть поглощать часть световой энергии, но все равно остается правило: один луч падает – один отражается.
Если объект прозрачный, то необходимо построить новый луч, такой, который при преломлении давал бы предыдущий трассируемый луч.
Для диффузного отражения интенсивность отраженного света, как известно, пропорциональна косинусу угла между вектором луча от источника света и нормалью. Когда выясняется, что текущий луч обратной трассировки не пересекает какой–либо объект, а уходит в свободное пространство, то на этом трассировка для этого луча заканчивается.
При практической реализации метода обратной трассировки вводят ограничения. Некоторые из них необходимы, чтобы можно было в принципе решить задачу синтеза изображения, а некоторые ограничения позволяют значительно повысить быстродействие трассировки [2].
Алгоритм выглядит следующим образом: из виртуального глаза через каждый пиксел изображения испускается луч и находится точка его пересечения с поверхностью сцены. Лучи, выпущенные из глаза называют первичными. Допустим, первичный луч пересекает некий объект 1 в точке H1 (рис. 1).
Рисунок 1 – Визуализация алгоритма трассировки лучей. Анимация состоит из 6 кадров с задержкой 1 с. Количество циклов воспроизведения ограничено 5
1–изображение, 2–источник света, 3–объект, 4 – луч глаза, 5 – луч тени
Далее необходимо определить для каждого источника освещения, видна ли из него эта точка. Предположим пока, что все источники света точечные. Тогда для каждого точечного источника света, до него испускается теневой луч из точки H1. Это позволяет сказать, освещается ли данная точка конкретным источником. Если теневой луч находит пересечение с другими объектами, расположенными ближе чем источник света, значит, точка H1 находится в тени от этого источника и освещать ее не надо. Иначе, считаем освещение по некоторой локальной модели (Фонг, Кук–Торранс и.т.д.). Освещение со всех видимых (из точки H1) источников света складывается. Далее, если материал объекта 1 имеет отражающие свойства, из точки H1 испускается отраженный луч и для него вся процедура трассировки рекурсивно повторяется. Аналогичные действия должны быть выполнены, если материал имеет преломляющие свойства [2].
Обзор существующих методов оптимизации алгоритма обратной трассировки лучей
Существует множество подходов к оптимизации алгоритма обратной трассировки лучей. Далее представлены некоторые варианты ускорения работы алгоритма.
1 kd–tree
Данный подход к оптимизации метода трассировки лучей рассматриваются в работах [3–6]. Рассмотрим структуру бинарного пространственного разбиения, называемую kd–дерево. Эта структура представляет собой бинарное дерево ограничивающих параллелепипедов, вложенных друг в друга. Каждый параллелепипед в kd–дереве разбивается плоскостью, перпендикулярной одной из осей координат на два дочерних параллелепипеда. Вся сцена целиком содержится внутри корневого параллелепипеда, но, продолжая рекурсивное разбиение параллелепипедов, можно прийти к тому, что в каждом листовом параллелепипеде будет содержаться лишь небольшое число примитивов. Таким образом, kd–дерево позволяет использовать бинарный поиск для нахождения примитива, пересекаемого лучом.
1 Построение kd–дерева Алгоритм построения kd–дерева можно представить следующим образом. Далее по тексту прямоугольный параллелепипед будем называть "бокс" (box).
1) "Добавить" все примитивы в ограничивающий бокс. Т.е построить ограничивающий все примитивы бокс, который будет соответствовать корневому узлу дерева.
2) Если примитивов в узле мало или достигнут предел глубины дерева, завершить построение.
3) Выбрать плоскость разбиения, которая делит данный узел на два дочерних. Будем называть их правым и левым узлами дерева.
4) Добавить примитивы, пересекающиеся с боксом левого узла в левый узел, примитивы, пересекающиеся с боксом правого узла в правый.
5) Для каждого из узлов рекурсивно выполнить данный алгоритм начиная с шага 2.
Самым сложным в построении kd–дерева является 3–ий шаг. От него напрямую зависит эффективность ускоряющей структуры. Существует несколько способов выбора плоскости разбиения, рассмотрим их по порядку:
1. Выбрать плоскость разбиения по центру. Самый простой способ – выбирать плоскость по центру бокса. Сначала выбираем ось (x, y или z), в которой бокс имеет максимальный размер, затем разбиваем бокс по центру(рис 2).
Рисунок 2 – Разбиение по центру
Этот способ имеет плохую адаптивность. Интуитивно можно описать причину плохой скорости на таких деревьях тем, что в каждом узле достаточно много пустого пространства, через которое луч трассируется (проходит через дерево во время поиска) в то время как пустое пространство должно сразу же по–возможности отбрасываться
2. Выбрать плоскость по медиане.
Можно подумать, что было бы неплохо разделять узел на два дочерних каждый раз так, чтобы в правом и левом поддереве количество примитивов было одинаково. Таким образом мы построим сбалансированное дерево, что должно ускорить поиск (рис 3).
Рисунок 3 – Разбиение по медиане
Это не очень удачная идея. Все дело в том, что сбалансированные деревья могут помочь только если искомый элемент каждый раз находится в случайном узле, то есть если распределение лучей по узлам во время поиска будет равномерно. В действительности, это не так. Лучей в среднем пойдет больше в тот узел, который больше по своей площади поверхности, а при медианном разбиении эти площади у узлов могут быть разные.
2. Surface Area Heuristic (SAH)
Каковы же критерии хорошо–построенного kd–дерева? На интуитивном уровне это на самом деле это не очень понятно, хотя выражение "как можно больше пустого пространство должно быть отброшено как можно быстрее" наверное подойдет.
Введем функцию стоимости прослеживания (cost traversal), которая будет отражать, насколько дорого по вычислительным ресурсам прослеживать данный узел случайным набором лучей. Будем вычислять ее по следующей формуле.
Где CostEmpty – стоимость прослеживания пустого узла (некоторая константа), SurfaceArea – площадь поверхности соответствующего узла, а N – число примитивов в нем. Нужно выбирать плоскость разбиениея так, чтобы минимизировать эту функцию. Аргумент функции x является одномерной координатой плоскости разбиения.
Хорошими кандидатами на минимум SAH могут служить границы примитивов. Простой алгоритм построения выглядит следующим образом. Каждый раз при выборе плоскости нужно перебрать всевозможные границы примитивов по трем измерениям, вычислить в них значение функции стоимости и найти минимум среди всех этих значений. Когда мы вычисляем SAH для каждой плоскости, то нам необходимо знать N(left) и N(right) – количества примитивов справа и слева от плоскости. Если вычислять N простым перебором, в итоге получится квадратичный по сложности алгоритм построения [3](рис 4).
Рисунок 4 – Разбиние с учетом SAH
Обзор исследований по теме в ДонНТУ
В ДонНТУ данной тематикой занимались Иванова Екатерина, Сереженко Александр, Винокуров Алексей и Грищенко Александр.
Обзор исследований по теме в мире
Методами оптимизации и ускорения алгоритма трассировки лучей для получения фото реалистических изображений занимаются мировые известные компании, которые специализируются на разработке визуальных эффектов, созданию мультфильмов (PIXAR), компании, которые специализируются на разработке аппаратного обеспечения для ПК (INTEL, nVidia, AMD), компании, которые специализируются на разработке специализированного компьютерного оборудования (Caustic, Splutterfish). Из–за того, что метод трассирования лучей очень требователен к аппаратной составляющей, даже мировой лидер по созданию визуальных мультфильмов PIXAR использует эту технологию не для всех разработок, чтобы не перегрузить существующие вычислительные мощности. Аналогичную ситуацию испытывает компания Lucas Arts [7].
Основные цели
− разработать оптимизированный алгоритм трассировки лучей, с целью уменьшения вычислительной сложности;
− модифицировать разработанный алгоритм для стерео–визуализации;
− исследовать возможность реализации алгоритма на параллельных архитектурах вычислительных систем, включая архитектуры GPU современных видеокарт ПК;
− создать прототип программной системы для синтеза реалистичных стереоизображений с использованием метода трассировки лучей на параллельной архитектуре GPU видеокарт ПК, проанализировать характеристики процесса синтеза в сравнении с «классическим» решением задачи.
Заключение
В ходе проведения исследования проблемы были проанализированы существующие подходы к ускорению реализации метода трассировки лучей, выявлены их сильные и слабые стороны, рассмотрены методы создания стерео–изображений. На сегодняшний день реализация трассировки в реальном времени требует значительных вычеслительных ресурсов.
Однако вычислительные мощности персональных компьютеров и их специализированных подсистем растут каждый день. Трассировка должна вытеснить другие алгоритмы ввиду явного превосходства в качестве изображения и универсальности метода. Следовательно, возможность эффективной по скорости реализации реалистичного синтеза стереоскопических изображений методом трассировки лучей и возможность его реализации на параллельных архитектурах специализированных вычислительных систем является важной задачей.
Литература
- Михайлюк М.В., Хураськин И.А. Синтез стереоизображения для систем виртуальной реальности с использованием оптической трекинговой системы.
- Трассировка лучей, МГУ, 2007 [Электронный ресурс].–Режим доступа: http://www.ray–tracing.ru/
- Shevtsov M., Soupikov A., Kapustin A. Highly Parallel Fast KD–tree Construction for Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the EUROGRAPHICS conference, 2007
- Foley T., Sugerman J. KD–Tree Acceleration Structures for a GPU Raytracer. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, p. 15–22, 2005.
- Horn D., Sugerman J., Houston M., Hanrahan P. Interactive k–D Tree GPU Raytracing. Proceedings of the symposium on Interactive 3D graphics and games on Fast rendering, p. 167–174, 2007.
- Popov S., Gunther J., Seidel H.–P., Slusallek P. Stackless KD–Tree Traversal for High Performance GPU Ray Tracing. In Proceedings of the EUROGRAPHICS conference, 2007.
- Сайт магистра ДонНТУ Сереженко А А – Разработка ускоренного алгоритма трассировки лучей [Электронный ресурс].–Режим доступа: http://masters.donntu.ru/2010/fknt/serezhenko/diss/index.htm
- Интерактивная трассировка лучей с использованием SIMD инструкций, 2008 [Электронный ресурс].– Режим доступа: http://software.intel.com/ru–ru/articles/interactive–ray–tracing/
- Андреев С.В., Бондарев А.Е., Михайлова Т.Н., Рыжова И.Г. Организация стереопредставлений в задачах синтеза фотореалистичных изображений и научной визуализации, Москва, 2010.
- Michael Doneus, Klaus Hanke, ANAGLYPH IMAGES – STILL A GOOD WAY TO LOOK AT 3D–OBJECTS?
Важное замечание
При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2011 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.
