Метод обратной трассировки

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

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

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

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

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

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

Когда выясняется; что текущий луч обратной трассировки не пересекает какой-либо объект, а уходит в свободное пространство, то на этом трассировка для этого луча заканчивается.

Рис. 14.1 Пример обратной трассировки лучей.

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

Принцип работы метода трассировки лучей:

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

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

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

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

5. Влияние всех лучей, сгенерированных явно или неявно с помощью начального луча, суммируется и результат определяет RGB-значение данной точки.

ВВЕДЕНИЕ

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

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

Окружающие нас объекты обладают по отношению к свету такими свойствами:

излучают;

отражают и поглощают;

пропускают сквозь себя.

Каждое из этих свойств можно описать некоторым набором характеристик.

Излучение можно охарактеризовать интенсивностью и спектром.

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

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

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

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

Непосредственная реализация данной лучевой модели формирования изображения представляется затруднительной. Можно попробовать построить алгоритм построения изображения указанным способом. В таком алгоритме необходимо предусмотреть перебор всех первичных лучей и определить те из них, которые попадают в объекты и в камеру. Затем выполнить перебор всех вторичных лучей, и также учесть только те, которые попадают в объекты и в камеру. И так далее. Такой алгоритм называется прямой трассировкой лучей. Главный недостаток этого метода - много лишних операций, связанных с расчетом лучей, которые затем не используются.

1. ОБРАТНАЯ ТРАССИРОВКА ЛУЧЕЙ

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

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

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

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

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

Если объект прозрачный, то необходимо построить новый луч, такой, который при преломлении давал бы предыдущий трассируемый луч.

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

Когда выясняется, что текущий луч обратной трассировки не пересекает какой-либо объект, а уходит в свободное пространство, то на этом трассировка для этого луча заканчивается.

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

Ограничения при реализации трассировки

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

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

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

При диффузном отражении учитываются только лучи от источников света. Лучи от зеркально отражающих поверхностей ИГНОРИРУЮТСЯ. Если луч, направленный на данный источник света, закрывается другим объектом, значит, данная точка объекта находится в тени. При диффузном отражении цвет освещенной точки поверхности определяется собственным цветом поверхности и цветом источников света.

Для прозрачных (transparent) объектов не учитывается зависимость коэффициента преломления от длины волны. (Иногда прозрачность вообще моделируют без преломления, то есть направление преломленного луча t совпадает с направлением падающего луча.)

Для учета освещенности объектов светом, рассеянным другими объектами, вводится фоновая составляющая (ambient).

Для завершения трассировки вводится ограничение количества итераций (глубины рекурсии).

Выводы по методу обратной трассировки

Достоинства:

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

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

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

Недостатки:

Проблемы с моделированием диффузного отражения и преломления.

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

2. КОНСТРУКТОРСКАЯ ЧАСТЬ

Алгоритмы.

Обратная трассировка лучей.

Рис. 1 - Блок-схема рекуррентного алгоритма обратной трассировки лучей

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

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

Алгоритм:

Для расчета цвета каждого пиксела буфера кадра выполняются следующие действия:

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

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

Запуск функции вычисления интенсивности первичного луча.

Найти пересечения луча со всеми примитивами сцены и выбрать ближайшее.

Если пересечение не найдено, значит, луч ушел в свободное пространство.

Для расчета цвета принимаем полную интенсивность равной фоновой интенсивности. Перейти на шаг 12. Если пересечение найдено, перейти на шаг 6.

Рассчитываем «локальную» интенсивность цвета объекта, которому принадлежит точка пересечения. Под «локальной» интенсивностью понимается интенсивность с учетом интенсивности диффузно отраженного света и интенсивность бликов.

Если материал отражает свет только диффузно, то считаем интенсивности отраженного и преломленного света нулевыми. Перейти на шаг 12. Иначе перейти на шаг 8.

Если достигнута максимальная глубина рекурсии, то принять интенсивности отраженного и преломленного света нулевыми. Перейти на шаг 12. Иначе перейти на шаг 9.

Вычислить вектор отраженного луча. Запуск рекурсии для нахождения интенсивности отраженного луча.

Вычислить вектор преломленного луча. Запуск рекурсии для нахождения интенсивности преломленного луча.

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

Возврат в точку вызова функции вычисления интенсивности луча.

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

Построение теней.

Сплошные тени.

Для построения сплошных теней в алгоритме трассировки на этапе вычисления «локальной» интенсивности цвета в точке объекта проверяется «видимость» каждого источника света из этой точки.

Принцип работы алгоритма.

Из проверяемой точки строится луч, направленный на источник света.

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

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

проверяемый источник.

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

Математические и физические предпосылки алгоритма обратной трассировки лучей.

Освещение.

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

Интенсивность фоновой подсветки (IA) задается некоторой константой.

Интенсивность диффузно отраженного света (ID) вычисляется по классическому «закону косинуса».

ID = IL cos α,(2.2.1.6)

где IL - интенсивность источника света, α - угол между нормалью к поверхности и направлением на источник.

В случае освещения сцены несколькими источниками Id вычисляется для каждого из них и затем суммируются.

IDi =Σ ILi cos αi.(2.2.1.7)

Интенсивность блика от источника (IS) вычисляется в соответствии с моделью Фонга.

IS = IL cosp β,(2.2.1.8)

где IL - интенсивность источника света (0<=IL<=1), β - угол между отраженным лучом от источника света и направлением на точку, в которой расположена камера (центр проекции), p - некоторая степень от 1 до 200 -влияет на размытость блика. При

маленьких значениях p блик более размытый.

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

ISi =Σ ILi cosp β i.(2.2.1.9)

Интенсивности зеркально отраженного (IR) и преломленного (IT) света рассчитываются для отраженного и преломленного лучей на следующем шаге рекурсии. Если достигнут предел глубины рекурсии, то эти интенсивности берутся нулевыми. От интенсивности IR берется r процентов, а от IT - t = 1 - r (см. предыдущий раздел).

Кроме того, вводятся следующие коэффициенты: KD - коэффициент диффузного отражения поверхности, KS - коэффициент блика.- этот коэффициент является характеристикой неровности отражающей поверхности. Чем больше неровность поверхности, тем меньше света отражается от неё зеркально и меньше света она пропускает, и соответственно больше света она отражает диффузно. 0 <= KD <= 1.

При KD = 0 - весь свет, падающий на поверхность, отражается и преломляется. KD = 1 - весь свет отражается диффузно. На этот коэффициент умножаются интенсивность диффузно отраженного света и интенсивность фоновой подсветки. Интенсивности зеркально отраженного и преломленного света умножаются на (1 - KD).- этот коэффициент отвечает за яркость блика от источника. 0<=KS<=1.

При KS = 0 - блик не виден, при KS = 1 - яркость блика максимальна.

Таким образом, окончательная формула для расчета интенсивности объекта в какой-либо точке будет выглядеть следующим образом:

I = IAKD + Σ(ILiKDcos αi + ILiKScosp β i) + (1 - KD)(IRr + IT(1 - r)).(2.2.1.10)

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

Для получения цветного изображения необходимо провести расчеты отдельно для красной, зеленой и синей компоненты света. Цвет пиксела изображения будет вычисляться путем умножения каждой компоненты интенсивности на число, определяющее максимальное количество градаций интенсивности изображения. Для 32-битного изображения оно равно 255 на каждый из цветов(R,G,B).

255*IR,= 255*IG,= 255*IB.

Здесь IR (не путать с интенсивностью зеркально отраженного света), IG, IB - интенсивности трех компонент света в точке, полученная по формуле, указанной выше.

Коэффициенты KD, KS, p - это индивидуальные характеристики объекта, отражающие его свойства. Кроме этого имеется еще один коэффициент - абсолютный показатель преломления n. n = c / v, где c - скорость света в вакууме, v - скорость света в среде (внутри объекта). Для абсолютно непрозрачных тел этот коэффициент равен ∞ (т.к. скорость света внутри тела нулевая). В программе для задания абсолютно непрозрачного тела необходимо поставить этот коэффициент >> 1 (порядка 10 000). При этом доля зеркально отраженного света r будет стремиться к единице, а преломленного, соответственно, к нулю.

Вычисление нормалей.

В алгоритме трассировки нормали к объектам необходимы для вычисления отраженного и преломленного лучей, а также для определения освещенности согласно модели Фонга.

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

Вычисление нормали к полигону (треугольнику).

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

XA, YA, ZA, XB, YB, ZB, XC, YC, ZC.

Вычислим координаты двух векторов, например AB и AC:

XB - XA,= XB - XA,

ZAB = XB - XA,(2.2.2.1)= XC - XA,= XC - XA,= XC - XA.

Координаты вектора нормали будут вычисляться по формулам:

YABZAC - YACZAB,= XABZAC - XACZAB,(2.2.2.2)= XABYAC - XACYAB.

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

Вычисление нормали к поверхности второго порядка.

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

Q(x,y,z) = a1x2 + a2y2 + a3z2 + b1yz + b2xz + b3xy + c1x +c2y +c3z + d =0.

Но мы будем использовать другую форму записи. Так уравнение эллипсоида будет выглядеть следующим образом:

(x-x0)2/A2 + (y-y0)2/B2 + (z-z0)2 /C2 = 1,(2.2.2.3)

где x0, y0, z0 - координаты центра эллипсоида, A, B, C - длины полуосей эллипсоида.

Уравнение параболоида:

(x-x0)2/A2 + (y-y0)2/B2 - (z-z0)2 /C2 = 1,(2.2.2.4)

где x0, y0, z0 - координаты центра параболоида, A, B, C - длины полуосей параболоида. Ось параболоида расположена вдоль оси Oz мировой системы координат. Для вычисления координат вектора нормали необходимо вычислить частные производные по x, y, z.

Координаты вектора нормали эллипсоида:

Yn = 2(y-y0)/B2,= 2(z-z0)/С2.

Направление вектора не изменится, если все его координаты разделить на 2:

Xn = (x-x0)/A2,= (y-y0)/B2,(2.2.2.5)

Zn = (z-z0)/С2.

Координаты вектора нормали параболоида вычисляются аналогично:

Xn = (x-x0)/A2,= (y-y0)/B2,(2.2.2.6)

Zn = - (z-z0)/С2.

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

Вычисление отраженного луча.

Пусть задан вектор падающего луча S, а также известен вектор нормали N. Требуется найти вектор отраженного луча R.

Рассмотрим единичные векторы R1, S1и N1. Поскольку векторы нормали, падающего луча и отраженного луча находятся в одной плоскости, то можно записать R1 + S1 = N`, где N` - это вектор, соответствующий диагонали ромба и совпадающий по направлению с нормалью. Длина вектора N` равна 2cosθ. Так как вектор N` по направлению совпадает с N1, то

N` = N`2cosθ.

Отсюда найдем единичный вектор отраженного луча:

R1 = N1 2cosθ - S1 = N/|N| 2cosθ - S/|S|.

Найдем cosθ. Это можно сделать, используя скалярное произведение векторов N и S:

Полагая, что искомый вектор отраженного луча будет иметь такую же длину, что и вектор падающего луча, то есть R = |S| R1, получим

N 2NS/|N|2 - S.

Это решение в векторной форме. Запишем координаты вектора:

2xN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) - xS,= 2yN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) - yS,(2.2.3.1)= 2zN(xNxS+yNyS+zNzS)/(xN2+yN2+zN2) - zS.

Вычисление преломленного луча.

Пусть даны два единичных вектора: S1 - вектор падающего луча, и N1 - вектор нормали к границе раздела двух сред. Также должны быть известны два коэффициента преломления для данных сред - n1 и n2 (или их отношение).

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

Искомый вектор T1 равен сумме двух векторов:

Найдем вначале вектор NT. Он противоположен по направлению вектору нормали, а его длина равна |T1| cos α2 = cos α2 (поскольку T1 - единичный). Таким образом, NT = -N1 cos α2. Необходимо определить cos α2. Запишем закон преломления n1 sin α1 = n2 sin α2 в виде:

sin α2 = n sin α1,

где n = n1 / n2.

Воспользуемся тождеством cos2α + sin2α = 1. Тогда

cos α2 = √ 1 - sin2α2 = √ 1 - n2 sin2α1

cos α2 = √ (1 + n2 (cos2α1 - 1)

Значение cos α1 можно выразить через скалярное произведение единичных векторов S1 и N1, то есть cos α1 = S1N1. Тогда мы можем записать такое выражение для вектора NT:

N1√1+n2((S1N1)2 - 1).

Осталось найти выражение для вектора B. Он располагается на одной прямой с вектором A, причем A = S1 - NS. Учитывая, что NS равен N1 cos α1, то A = S1 - N1 cos α1. Так как cos α1 = S1N1, то A = S1 - N1 (S1N1).

Поскольку длина вектора A равна sin α1, а длина вектора B равна sin α2, то

|B|/|A| = sin α2/ sin α1 = n2/n1 = n,

откуда |B| = n |A|. Учитывая взаимное расположение векторов A и B, получим

NA =n(N1(S1N1) - S1).

Теперь мы можем записать искомое выражение для единичного вектора луча преломления T1:

T1 = nN1 (S1N1) - nS1 - N1√1 + n2 ((S1N1)2 - 1).(2.2.4.1)

Вычисление точки пересечения с примитивами.

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

R = A + Vt,(2.2.5.1)

где R - радиус вектор произвольной точки, принадлежащей лучу, A - радиус- вектор начальной точки луча, V - направляющий вектор луча, t - параметр.

Если направляющий вектор V нормализовать, то параметр t будет численно равен расстоянию от начальной точки луча A до точки R.

Можно записать это уравнение в координатном виде:

x = x1 + at,= y1 + bt,(2.2.5.2)= z1 + ct.

Здесь x1, y1, z1 - координаты начальной точки луча в прямоугольной декартовой мировой системе координат, a,b,c - координаты направляющего вектора луча.

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

Для нахождения точки пересечения луча, заданного уравнениями (2) с поверхностью второго порядка, заданной уравнениями (2.2.2.3) или (2.2.2.4):

(x-x0)2/A2 + (y-y0)2/B2 + (z-z0)2 /C2 = 1 (эллипсоид)

(x-x0)2/A2 + (y-y0)2/B2 - (z-z0)2 /C2 = 1 (параболоид),

нужно подставить в уравнение поверхности второго порядка вместо x, y и z соответствующие уравнения луча. В результате этого после раскрытия всех скобок и приведения подобных мы получим квадратное уравнение относительно параметра t. Если дискриминант квадратного уравнения меньше нуля, то луч и поверхность второго порядка общих точек пересечения не имеют. В противном случае можно будет вычислить два значения параметра t. Дискриминант может быть равен нулю - это соответствует предельному случаю касания луча поверхности, и мы получим два совпадающих значения параметра t.

Для нахождения координат точек пересечения луча и поверхности достаточно подставить найденные значения параметра t в уравнения луча (2).

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

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

Для этого после нахождения точки пересечения анализируется ее z-координата.

Вычисление точки пересечения луча с полигоном (треугольником).

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

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

Q(x, y, z) = Ax + By + Cz +D = 0.(2.2.5.3)

Здесь коэффициенты A, B, C совпадают с координатами нормали к этой плоскости. Координаты нормали плоскости совпадают с координатами нормали треугольника, которые мы посчитали на этапе загрузки сцены.

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

Ax -By - Cz.(2.2.5.4)

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

Теперь для нахождения точки пересечения подставим уравнения луча (2) в

уравнение плоскости.

(x1 + at) + B (y1 + bt) + C (z1 + ct) + D = 0

Откуда получим

= - (Ax1 + By1 + Cz1 + D) / (Aa + Bb + Cc)(2.2.5.5)

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

Для нахождения координат точки пересечения надо подставить найденное значение параметра t в уравнения луча (2). Назовем точку пересечения D. Мы получим координаты xD, yD, zD.

Теперь необходимо определить, попала ли точка D внутрь треугольника. Найдем координаты векторов AB, BC, CA (A, B, C - вершины треугольника) и координаты векторов AD, BD, CD. Затем найдем три векторных произведения:

nA = AB x AD,= BC x BD,(2.2.5.6)= CA x CD.

Эти вектора будут коллинеарны. Если все три вектора сонаправлены, то точка D лежит внутри треугольника. Сонаправленность определяется равенству знаков соответствующих координат всех трех векторов.

Операцию проверки принадлежности точки D треугольнику ABC можно ускорить. Если ортогонально спроецировать треугольник ABC и точку D на одну из плоскостей xOy, yOz или xOz, то попадание проекции точки в проекцию треугольника будет означить попадание самой точки в треугольник (конечно же, если уже известно, что точка D лежит в плоскости, содержащей треугольник ABC). При этом число операций заметно сокращается. Так для поиска координат всех векторов нужно искать по две координаты на каждый вектор, а при поиске векторных произведений нужно искать только одну координату (остальные равны нулю).

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

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

Остается добавить, что для проецирования лучше выбирать ту из плоскостей, площадь проекции треугольника на которую больше. При таком условии исключается случай проецирования треугольника в отрезок (при условии, что проверяемый треугольник не вырожден в отрезок). Кроме того, при увеличении площади проекции уменьшается вероятность ошибки. Для определения такой плоскости проецирования достаточно проверить три координаты нормали треугольника. Если z-координата нормали больше (по абсолютному значению) x и y, то проецировать надо на плоскость xOy. Если y больше чем x и z, то проецируем на xOz. В оставшемся случае - на yOz.

Описание типов данных. Структура программы.

Описание модулей программы

Список модулей:.h-описание структуры TTex.h-описание структур TPlaneTex и TEllipsoidTex.h-описание структур TPoint2d и TPoint3d.h-описание страктуры TRGBColor.h-описание класса TLamp.h-описание класса TCam.h-описание класса TPrimitive.h-описание класса TFrstSurface.h-описание класса TScndSurface.h-описание класса TTriangle.h-описание класса TEllipsoid.h-описание класса TCylinder.h-описание класса THyperboloidVert.h-описание класса THyperboloidHor.h-описание класса TScene.h-описание класса TTracer

Модули реализующие, интерфейс программы:

Options.h-модуль формы «Опции»

ExtraCamOptions.h-модуль формы «Свойства камеры»

MainUnit.h-модуль главной формы программы

Краткое описание структур и классов программы:TPoint3d - структура, описывающая точку в мировой системе координат,TPoint2d - структура, описывающая точку на плоскости (в текстуре) с целочисленными координатами,TRGBColor - структура, описывающая цвет по трем составляющим (RGB),TTex - структура, описывающая текстуру - содержит адрес массива пикселей и его размеры,TPlaneTex - структура, описывающая привязку текстуры к плоскости.

Содержит три точки, к которым привязывается текстура:TLamp - класс, описывающий источник освещения.

Содержит объект TPoint3d coord с координатами источника и три переменные типа float (Ir, Ig, Ib) для хранения интенсивности трех компонент света.TCam - класс, описывающий камеру.

Содержит два угла (a, b), указывающих направление зрения камеры, точку, на которую направлена камера (viewP) и расстояние от камеры до этой точки (r). TPrimitive - абстрактный класс примитива. От него наследуются поверхности первого и второго порядка.TFrstSurface - абстрактный класс поверхности первого порядка. От него наследуется класс треугольника.TScndSurface - абстрактный класс поверхности второго порядка. От него наследуются классы эллипсоида и параболоида.TTriangle - класс треугольника. Содержит три вершины треугольника и его нормаль.TCylinder - класс цилиндра.THyperboloidVert - класс однополостного гиперболоида, лежащего вдоль оси oZ.THyperboloidHor -класс однополостного гиперболоида, лежащего вдоль оси oX.TEllipsoid - класс эллипсоида.TScene - класс сцены. Содержит информацию о всех примитивах, источниках и камере.TTracer - класс, отвечающий за построения изображения. Содержит буфер (buffer) разметом 400x400 пикселей, в котором формируется изображение сцены. Перед генерацией необходимо вызвать функциюпередав ей в качестве параметра указатель на сцену, которую необходимо сгенерировать. Для генерации вызвать функцию render.

Все классы - потомки TPrimitive предоставляют следующие функции:getT(TPoint3d p0, TPoint3d viewDir) - возвращает расстояние от точки начала(p0) луча viewDir до ближайшей точки пересечения с примитивом.

void getTArr(float* arr, int& n, TPoint3d p0, TPoint3d viewDir) - заполняет массив arr расстояниями от точки начала(p0) луча viewDir до ближайшей всех точек пересечения с примитивом.

void getNormal(TPoint3d& n, const TPoint3d& p) - возвращает координаты вектора нормали к примитиву в точке p.

void getColor(TRGBColor& c, const TPoint3d& p) - возвращает цвет примитива точке p (с учетом текстуры).

3. ТЕХНОЛОГИЧЕСКАЯ ЧАСТЬ

Выбор языка программирования.

При разработке программы был использован язык программирования высокого уровня C++ в составе среды визуального программирования CodeGear RAD Studio for Windows.

Данный язык был выбран благодаря тому, что он предоставляет максимально удобные средства по работе с оперативной памятью, позволяет реализовывать алгоритмы более эффективно, по сравнению с другими высокоуровневыми языками. Программы, написанные на C++, работают быстрее и занимают меньше места на диске.

Кроме того, среда визуального программирования CodeGear RAD Studio for Windows

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

Форма «опции». Вкладка «освещение».

На этой вкладке находятся средства по настройке освещения сцены.

Координаты источника - координаты в мировой системе координат источника света, выбранного в выпадающем списке.

Интенсивность источника - значения трех компонент интенсивности источника света, выбранного в выпадающем списке.

Фоновая интенсивность - значения трех компонент фоновой интенсивности.

Кнопка “+” (рядом с выпадающим списком) - добавление нового источника света.

Кнопка “-” (рядом с выпадающим списком) - удаление источника света, выбранного в выпадающем списке.

Форма «опции». Вкладка «камера».

На этой вкладке находятся средства по настройке опций камеры.

Предосмотр - здесь можно увидеть примерный вид изображения до его генерации.

Навигация - настройки положения камеры.

Дополнительно - при нажатии на эту кнопку появляется форма

Свойства камеры с дополнительными параметрами камеры.

Форма «свойства камеры».

Радиус - расстояние от камеры до точки, на которую она направлена.

Шаг изменения радиуса - приращение радиуса камеры при однократном нажатии кнопки “-” на вкладке “Камера” формы “Опции” (или уменьшение при однократном нажатии кнопки “+”).

Форма «опции». вкладка «материалы».

В данном меню отображаются параметры материала стола, на котором стоит сцена.

Цвет - цвет материала стола.

Коэф. диффузного отражения - коэффициент Kd материала стола (см. раздел 2.2.1).

Текстура - если галочка установлена, то на столе будет отображаться текстура

Выбрать текстуру - выбор файла изображения (*.bmp), который будет использоваться как текстура стола.

Дополнительно - при нажатии на эту кнопку появляется форма Свойства стола с дополнительными параметрами материала стола.

Форма «свойства стола».

Коэффициент блика - коэффициент KS материала стола (см. раздел 2.2.1).

Размытость блика - показатель степени p материала стола.

Повторения текстуры - сколько раз текстура стола будет повторяться вдоль осей OX и OY.

Форма «опции». Вкладка «системные».

На этой вкладке можно настраивать алгоритмы, реализованные в программе.

Глубина рекурсии - этот параметр устанавливает глубину рекурсии в алгоритме трассировки. При бОльших значениях этого параметра качество сгенерированного изображения улучшается.

ВНИМАНИЕ!

Глубина рекурсии СИЛЬНО влияет на скорость генерации изображения. Не рекомендуется ставить значения этого параметра больше 10.

Анитиалиазинг - включение алгоритма сглаживания изображения.

Тип тени - выбор алгоритма построения теней.

4. ИССЛЕДОВАТЕЛЬСКАЯ ЧАСТЬ

Исследования проводились на компьютере со следующей конфигурацией:

CPU - Intel Core 2 Duo T5850- 2048Mb DDR2 - Nvidia GForce 9300M 256Mb- Windows 7

4.1 Зависимость времени генерации от глубины рекурсии

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

4.2 Зависимость времени генерации от количества источников

4.3 Анализ результатов исследований

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Роджерс Д. Алгоритмические основы машинной графики: пер. с англ.- М.: Мир, 1989.- 512 с.

Порев В. Н. Компьютерная графика. - СПб.: БХВ-Петербург, 2002. - 432 с.

Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. - 560 с.

Эйнджел Э. Интерактивная компьютерная графика. - «Вильямс», 2001. - 592 с.: ил. - Парал. Тит. С англ.

Авдеева С.М., Куров А.В. Алгоритмы трехмерной машинной графики: Учебное пособие. - М.: Изд-во МГТУ им. Н.Э. Баумана, 1996. - 60 с.

Министерство образования Российской Федерации

Московский Государственный Институт Электроники и Математики

(Технический Университет)

Кафедра Информационно-коммуникационных

технологий

Курсовая работа на тему:

«Анализ перспективности использования метода трассировки лучей в 3D моделировании»

Выполнили :

Гулиян Борис

Подзоров Иван

Группа С -35

Москва 2010

1. 3D-графика. Введение

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

4. Основные достоинства и недостатки трассировки лучей

5. Применение метода трассировки лучей

6. Эксперимент.

Задача: "Анализ перспективности использования метода трассировки лучей в 3D моделировании"

Постановка задачи

Ознакомиться с методом трассировки лучей и его использованием в области 3D графики, поставить эксперимент с использованием одного из алгоритмов трассировки лучей.

В нашем эксперименте мы рассматриваем:
1)производительность алгоритма трассировки лучей в зависимости от числа полигонов модели(в качестве модели берутся 3 шара: матовый, прозрачный и зеркальный).

2)Анализ полученых изображений с применением трассировки лучей и без нее.

В Качестве среды для проведения эксперимента используется ПО Blender.

3D-графика. Введение.

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

Любое 3D изображение определяется следующими параметрами и объектами:

· Геометрия (построенная медели)

· Материалы (информация о визуальных свойствах модели)

· Источники света (настройки направления, мощности, спектра освещения)

· Виртуальные камеры (выбор точки и угла построения проекции)

· Силы и воздействия (настройки динамических искажений объектов, применяется в основном в анимации)

· Дополнительные эффекты (объекты, имитирующие атмосферные явления: свет в тумане, облака, пламя и пр.)

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

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

Прямая и обратная трассировка лучей

Трассировка лучей - это метод обработки 3D моделей с получением фотореалистичного изображения, в котором учитывается взаимное расположение объектов, а также такие физические свойства объектов как отражающая и преломляющая способность.

Существует 2 метода трассировки лучей: прямой и обратный

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

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

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

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

Рассмотрим принципиальный алгоритм трассировки(Рис. 1). Объектом возьмем сферу.

1. Для каждого пиксела на экране из глаза наблюдателя выпускается луч.

2. После пересечения лучом объекта определяется:

· Прозрачность/непрозрачность объекта. Если объект прозрачный, то из пересечения испускается луч преломления, если непрозрачный - не испускается.

· Освещенность/тень. Из точки пересечения лучом сферы испускаются луч к источнику света (или поочередно для каждого источника света, если их несколько). Если этот луч не пересекает другие непрозрачные объекты или поверхности, значит, источник света непосредственно влияет на освещенность данной точки. Если имеется несколько источников света, то по влиянию всех лучей вычисляется результат, определенный RGB-значением данной точки.

· Отражающая способность. Если объект способен отражать лучи, то из точки пересечения лучом сферы испускается отраженный луч к объектам, которые будут отражены в сфере.

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

· лучи преломления;

· лучи тени/освещения;

· лучи отражения.

Рис. 1 Схема алгоритма трассировки лучей

Все остальные алгоритмы основаны на алгоритме, показанном выше, и призваны оптимизировать вычисления.

kd-дерево

Алгоритм построения kd-дерева можно представить следующим образом (будем называть прямоугольный параллелепипед англоязычным словом "бокс" (box)).

1. "Добавить" все примитивы в ограничивающий бокс. Т. е построить ограничивающий все примитивы бокс, который будет соответствовать корневому узлу дерева.

2. Если примитивов в узле мало или достигнут предел глубины дерева, завершить построение.

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

4. Добавить примитивы, пересекающиеся с боксом левого узла в левый узел, примитивы, пересекающиеся с боксом правого узла в правый.

5. Для каждого из узлов рекурсивно выполнить данный алгоритм начиная с шага 2.

Regular grid

Все 3D пространство разбивается на мелкую регулярную сетку, состоящую из N*N*N кубиков. Идея заключается в том, что можно пробегать только по тем по кубикам, через которые пошел луч.

Метод не используется на практике.

Д остоинства и недостатки

Помимо того, что метод трассировки лучей дает максимально фотореалистичную картинку, он имеет ряд и других достоинств:

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

2. Вычислительная сложность метода слабо зависит от сложности сцены.

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

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

font-size:14.0pt"> Рис. 2 Отражения двух зеркальных шаров друг в друге

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

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

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

3. Отсутствие аппаратной поддержки метода (все GPU специализируются на растеризации).

4. Ещё одна характерная проблема метода трассировки лучей касается сглаживания (AA). Лучи проводятся в виде простой математической абстракции , и реального размера они не учитывают. Проверка на пересечение с треугольником является простой логической функцией, которая даёт ответ "да" или "нет", но не даёт таких деталей, как "луч на 40% пересекает треугольник". Прямым следствием такого эффекта будет появление "лесенок"(Рис.3).

Рис. 3 сглаживание теней

И единственной технологией, которая может дать хорошие результаты, является расчёт большего числа лучей, чем есть пикселей, то есть суперсэмплинг(Oversampling или Anti-Aliasing) (рендеринг при большем разрешении).

Также следует помнить, что скорость рендеринга и его качество методом трассировки лучей сильно зависит от оптимизации кода.

Применение метода трассировки лучей

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

· 3D мультипликация;

· Спецэффекты киноиндустрии;

· Реалистичный рендеринг фотоизображения;

· Cad - системы.

Специальные термины:

Полигональная сетка-совокупность вершин и полигонов, которая определяет форму отображаемого объекта.

Рендеринг (Render) - (англ. rendering - «визуализация») - процесс получения изображения по модели.

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

Рис 4. полигональная сетка

Эксперимент.

В качестве ПО для проведения эксперемента мы выбрали 3D - редактор Blender.

Он достаточно легок в освоении и содержит в себе все не обходимые функции:

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

· Oversampling(anti-aliasing или сглаживание )

Мы замеряли время, необходимое на рендеринг 3-х различных сфер(стеклянной, зеркальной и матовой) на различных Уравных Multeris (каждый уровень повышает число полигонов в 4 раза). При повышении уровня время считали от 0.

0 " style="margin-left:48.35pt;border-collapse:collapse">

Ур. Multeris

Время рендеринга каждого ур. с 0

Без RayT [c]

С RayT [c]

0,53

3,36

0,46

0,54

2,84

0,55

3,02

0,61

3,85

0,96

5,96

10,64

29,12

43,9

Таблица 1.

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

В результате видим, что время на обработку трех сфер с уровнем 4 (по 256 полигонов на каждой сфере) меньше, чем время, потраченное на обработку сфер с уровнем 2 (по 16 полигонов).

Рис 5. полигональные сетки для различных уровней

Итог

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

Анализ полученый изображений:
1)На картинке, полученной без использования трассировки (далее А), видно, что прозрачная сфера не дает эффект линзы (применение альфа-канала), в то время как на картинке, с использованием трассировки лучей (далее Б) прозрачный шар увеличивает объекты за ним(рис. 6).

Рис. 6 прозрачные сферы (слева alpha-канал, справа трассировка лучей)

2)На картинке А нет зеркального шара, т. к получение отражения на нем основано на трассировке лучей(рис. 7).

Рис 7. модель эксперимента (сверху alpha-канал, снизу трассировка лучей).

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

Рис.8 Падения света на впадены в шаре(слева А, справа Б)

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

За последние несколько лет метод трассировки лучей (ray tracing), похоже, стал "мечтой номер один" мира 3D-графики в реальном времени. Интерес к этой технологии рендеринга вырос до максимума, когда молодой исследователь Дэниел Похл (Daniel Pohl) объявил о своём проекте в области этой технологии ещё в 2004 году.

Причина интереса широких масс публики к работе заключалась, по большей мере, в том, что Похл сфокусировался на знаменитых играх id Software Quake III, Quake IV и шутере-франшизе Quake Wars 3D. Исследователь привлёк немало внимания со стороны прессы, а геймеры начали мечтать о светлом будущем, когда их любимые игры будут просчитываться по методу трассировки лучей и избавятся от растеризации.

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

Нажмите на картинку для увеличения.

Основные принципы

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

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

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

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

• лучи тени/освещения;
• лучи отражения;
• лучи преломления.

Классический алгоритм трассировки лучей. Нажмите на картинку для увеличения.

Данный алгоритм трассировки лучей является результатом работы Тёрнера Виттеда (Turner Whitted), исследователя, который изобрёл алгоритм 30 лет назад. До того времени алгоритм трассировки лучей работал только с первичными лучами. И улучшения, внесённые Виттедом, оказались гигантским шагом в сторону реализма рендеринга сцены.

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

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

Оригинальный алгоритм трассировки лучей приводил к большому количеству ненужных расчётов. Нажмите на картинку для увеличения.

Преимущества трассировки лучей

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

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

Отражения - это одна из областей, в которых метод трассировки лучей превосходно показывает себя. Сегодня в 3D-движках современных игр отражения рассчитываются с помощью карт окружений (environment map). Эта технология даёт хорошее приближение к отражениям объектов, расположенных "в бесконечности" или в окружающей среде (как можно видеть по названию), но для близко расположенных объектов подход показывает свои ограничения.

Разработчики игр-гонок, в частности, создали свои трюки для симуляции отражений близких объектов с помощью так называемых динамических кубических карт (dynamic cube maps). Камера располагается на уровне машины геймера, после чего проводится рендеринг в основных направлениях. Затем результаты рендеринга сохраняются в кубических картах, которые и используются для вывода отражений.

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

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

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

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

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

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

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

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

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

Мифы о трассировке лучей

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

Начнём с того, что многие геймеры считают алгоритм трассировки лучей принципиально лучше, чем растеризации, поскольку его используют в фильмах. Это не так. Большинство фильмов с синтезированной/рисованной картинкой (например, все фильмы студии Pixar) используют алгоритм под названием REYES, который базируется на растеризации. Pixar добавила трассировку лучей к своему движку рендеринга RenderMan только позднее, во время производства мультфильма "Тачки/Cars". Но даже для этого фильма метод трассировки лучей использовался избирательно, чтобы не перегрузить существующие вычислительные мощности. До этого проекта Pixar использовала внешний модуль для ограниченного использования метода трассировки лучей, например, для эффектов затенения ambient occlusion (AO).

Нажмите на картинку для увеличения.

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

Ниже показано, как алгоритм растеризации работает с каждым треугольником сцены.

• Определяется набор пикселей, который покрывает каждый треугольник;
• для каждого задействованного пикселя его глубина сравнивается с глубиной соседнего пикселя.

Основное ограничение метода растеризации касается числа треугольников. Алгоритм имеет сложность O(n), где n - число треугольников. Алгоритм в данном случае имеет линейную сложность в зависимости от числа треугольников, поскольку для каждого кадра составляется список треугольников, которые нужно обработать, один за другим.

Напротив, алгоритм трассировки лучей работает следующим образом.

Для каждого пикселя кадра:

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

Как видим, последовательность обработки стала обратной. В первом случае мы брали каждый полигон и смотрели, какие пиксели он покрывает. А во втором случае мы брали каждый пиксель и смотрели, какой полигон ему соответствует. Поэтому можно подумать, что метод трассировки лучей меньше зависит от числа полигонов, чем метод растеризации, поскольку число полигонов не влияет на основной цикл. Но на практике это не так. Фактически, чтобы определить, какой треугольник будет пересекаться с лучом, нам нужно обработать все треугольники сцены. Здесь, конечно, защитники метода трассировки лучей скажут, что не нужно обрабатывать все треугольники сцены с каждым лучом. Если использовать соответствующий тип структуры данных, то очень легко организовать треугольники таким образом, чтобы только небольшой их процент тестировался с каждым лучом, то есть мы получаем, что метод трассировки лучей имеет сложность O(log n), где n - число полигонов.

Да, доводы можно признать верными. Но защитники метода трассировки лучей немного лукавят в том, что то же самое верно и для растеризации. Игровые движки уже многие годы используют BSP-деревья (binary space partitioning) и другие методы, ограничивающие число полигонов, которые нужно рассчитать для каждого кадра. Ещё один спорный момент - такие структуры более всего эффективны для статических данных. Всё, что нам нужно: рассчитать данные один раз, после чего просто обеспечивать к ним доступ, и это даёт очень хорошие результаты. Но что делать с динамическими данными? В данном случае данные придётся пересчитывать для каждого изображения, а для этого нет никаких чудесных формул. Всё равно придётся изучать каждый полигон.

Простой алгоритм?

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

Дэвид Любке (David Luebke), инженер nVidia, сделал следующий комментарий, прекрасно отражающий реальность: "Растеризация выполняется быстро, но необходимо тщательно продумывать то, как выполнять сложные визуальные эффекты. Метод трассировки лучей поддерживает сложные визуальные эффекты, но необходимо тщательно продумывать то, как сделать его быстрым".

Код минимального алгоритма трассировки лучей, написанный Полем Хекбертом (Paul Heckbert), чтобы уместить его на "визитке". Нажмите на картинку для увеличения.

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

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

Визуализация "стоимости" рендеринга каждого пикселя, где красные пиксели являются самыми "дорогими". Как можно видеть, рендеринг деревьев стоит очень дорого в версии Quake Wars с методом трассировки лучей. Нажмите на картинку для увеличения.

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

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

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

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

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

У видеокарт задержки памяти (latency) уменьшаются намного медленнее, чем увеличивается пропускная способность (bandwidth). Если последняя улучшается в 10 раз, то задержки улучшаются только в два раза.

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

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

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

Гибридный движок рендеринга?

Если вы прочитали всю статью до этого места, то наверняка уже подумываете о том, что метод трассировки лучей пока что не может заменить растеризацию, но, возможно, стоит смешать две технологии вместе? И на первый взгляд кажется, что две технологии дополняют друг друга. Легко представить растеризацию треугольников для определения видимой картинки, получая преимущество от великолепной производительности данной технологии, после чего будет применяться трассировка лучей только для некоторых поверхностей, добавляя реализм там, где это необходимо, например, для добавления теней или получения хороших отражений и прозрачности. Собственно, такой подход Pixar и использовала для мультфильма "Тачки/Cars". Геометрические модели создаются с помощью REYES, а трассировка лучей используется "по требованию" там, где нужно симулировать определённые эффекты.

Для мультфильма "Тачки/Cars" Pixar использовала гибридный движок рендеринга, сочетающий REYES для визуализации и трассировку лучей "по требованию" для отражений и ambient occlusion. Нажмите на картинку для увеличения.

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

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

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

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

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

На самом деле отражений нет. Например, зеркало бокового вида на корпусе машины не отражается. Но нужен ли вам "честный" рендеринг Audi R8 с помощью метода трассировки лучей? Нажмите на картинку для увеличения.

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

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

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

Нажмите на картинку для увеличения.

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

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

Впрочем, нас это вряд ли убедит. В любом случае, мы ещё пока далеки до того времени, когда мы сможем пожертвовать производительностью из-за элегантности и простоты. Просто посмотрите, что произошло за последние 10 лет в мире оффлайнового рендеринга. Если рендеринг одного кадра мультфильма "История игрушек/Toy Story" выполнялся, в среднем, за два часа, то кадр из мультфильма "Рататуй/Ratatouille" - уже за шесть с половиной часов, несмотря на вычислительную мощность, которая увеличилась в промежутке между двумя картинами более чем в 400 раз. Другими словами, чем больше вычислительной мощности и ресурсов вы предоставляете компьютерным художникам, тем быстрее они их поглощают.

Если даже компания, подобная Pixar, которая может позволить себе выделить несколько часов вычислений для создания одного кадра, решила использовать трассировку лучей только время от времени из-за негативного влияния на производительность, это значит, что времена, когда мы получим достаточную вычислительную мощность в 3D-играх реального времени для выполнения всего рендеринга методом трассировки лучей, очень и очень далеки. Да и в будущем у энтузиастов наверняка будет, куда потратить такую вычислительную мощность.

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

Рассмотрим, как формируется изображение. Изображение получается из-за того, что свет попадает в камеру. Выпустим из источников света множество лучей. Назовем их первичными лучами. Часть этих лучей улетит в свободное пространство, а часть попадет на объекты. На них лучи могут преломиться, отразится. При этом часть энергии луча поглотится. Преломленные и отраженные лучи образуют множество вторичных лучей. Далее эти лучи опять же преломятся и отразятся и образуют новое поколение лучей. В конечном итоге часть лучей попадет в камеру и сформирует изображение.

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

Метод обратной трассировки лучей позволяет значительно сократить перебор световых лучей. Этот метод разработали в 80-х годах Уиттед и Кэй. В этом методе отслеживаются лучи не от источников, а из камеры. Таким образом, трассируется определенное число лучей, равное разрешению картинки.

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

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

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

Таким образом, первичный луч, найдя пересечение с объектом, делится в общем случае на два луча (отраженный и преломленный). Далее эти два луча делятся еще на два и так далее.

Главной процедурой обратной трассировки лучей в моей программе является процедура Ray. Она имеет следующую структуру:

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

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

Если такого треугольника нет, возвращаем цвет фона, если есть, идем дальше.

Если поверхность, с которой было найдено пересечение, отражает, то формируем отраженный луч и вызываем рекурсивно процедуру Ray с поколением луча, увеличенным на 1.

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

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

Я уже рассмотрели ряд ограничений метода трассировки, когда говорили о диффузном преломлении и о неровном зеркале. Рассмотрим и некоторые другие.

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

Свойства отражающей поверхности состоят из двух компонент - диффузной и зеркальной.

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

Зеркальность тоже делится на две составляющие.

reflection - учитывает отражение от других объектов (не источников света)

specular - учитывает блики от источников света

В трассировке не учитываются зависимости от длины волны света:

коэффициента преломления

коэффициента поглощения

коэффициента отражения

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

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

В моей программе есть возможность включить сглаживание изображения. Сглаживание заключается в том, что для определения цвета пиксела. пускается не один луч, а четыре и определяется среднее значение цвета у этих лучей. Если необходимо найти цвет пиксела (i,j), то пускаются 4 луча в точки экранной плоскости с координатами (i-0.25,j-0.25), (i-0.25,j+0.25), (i+0.25,j-0.25), (i+0.25,j+0.25).