ВВЕДЕНИЕ

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

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

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

излучают;

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

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

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

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

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

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

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

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

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

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 с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что такое Nvidia RTX?

Nvidia RTX - платформа, содержащая ряд полезных инструментов для разработчиков, которые открывают доступ к новому уровню компьютерной графики. Nvidia RTX доступна только для нового поколения видеокарт Nvidia GeForce RTX, построенного на архитектуре Turing. Основная особенность платформы - наличие возможности трассировки лучей в реальном времени (также называемой рейтресингом).

Что за трассировка лучей?

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

Это исправляет новая серия видеокарт Nvidia GeForce RTX, обладающая достаточной мощностью для расчёта пути лучей.

Как это работает?

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

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

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

Это побудило Nvidia внедрить дополнительные ядра в видеокарты GeForce RTX, которые возьмут на себя большую часть нагрузки, улучшая производительность. Они также снабжены искусственным интеллектом, задача которого - высчитывать возможные ошибки во время процесса трассировки, что поможет их избежать заранее. Это, как заявляют разработчики, также повысит скорость работы.

И как трассировка лучей влияет на качество?

Во время презентации видеокарт Nvidia продемонстрировала ряд примеров работы трассировки лучей: в частности, стало известно, что некоторые грядущие игры, включая Shadow of the Tomb Raider и Battlefield 5 будут работать на платформе RTX. Функция эта, тем не менее, будет в игре необязательной, так как для трассировки нужна одна из новых видеокарт. Трейлеры, показанные компанией во время презентации, можно посмотреть ниже:

Shadow of the Tomb Raider , релиз которой состоится 14 сентября этого года:

Battlefield 5 , которая выйдет 19 октября:

Metro Exodus , чей выход намечен на 19 февраля 2019 года:

Control , дата выхода которой пока неизвестна:

Вместе с этим всем, Nvidia , какие ещё игры получат функцию трассировки лучей.

Как включить RTX?

Ввиду технических особенностей данной технологии, рейтресинг будут поддерживать только видеокарты с архитектурой Turing - имеющиеся сейчас устройства не справляются с объёмом работы, который требует трассировка. На данный момент, единственные видеокарты с данной архитектурой - серия Nvidia GeForce RTX, модели которой доступны для предзаказа от 48 000 до 96 000 рублей.

А есть ли аналоги у AMD?

У AMD есть свой собственный вариант технологии трассировки лучей в реальном времени, который присутствует в их движке Radeon ProRender. Компания анонсировала свою разработку ещё на GDC 2018, которая прошла в марте. Основное отличие метода AMD от Nvidia заключается в том, что AMD даёт доступ не только к трассировке, но и к растеризации - технологии, которая применяется сейчас во всех играх. Это позволяет как использовать трассировку, получая более качественное освещение, так и экономить ресурсы в местах, где трассировка будет излишней нагрузкой на видеокарту.

Технология, которая будет работать на API Vulkan, пока находится в разработке.

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

Недавно в интернете я наткнулся на трассировщик лучей на визитке Пола Гекберта. Для тех, кто не в курсе: это очень известная задача, изначально предложенная Полом Гекбертом 4-ого мая 1984 на comp.graphics. Ее суть в том, чтобы написать демонстрацию метода бросания лучей, которая бы… умещалась на визитной карточке (больше об этом читайте в разделе «Трассировка лучей» из книги «Графические драгоценности IV»)!

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

Обратная сторона визитки

Вот так выглядит сам код:

#include // card > aek.ppm #include #include typedef int i;typedef float f;struct v{ f x,y,z;v operator+(v r){return v(x+r.x ,y+r.y,z+r.z);}v operator*(f r){return v(x*r,y*r,z*r);}f operator%(v r){return x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r. y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v operator!(){return*this*(1/sqrt(*this%* this));}};i G={247570,280596,280600, 249748,18578,18577,231184,16,16};f R(){ return(f)rand()/RAND_MAX;}i T(v o,v d,f &t,v&n){t=1e9;i m=0;f p=-o.z/d.z;if(.01 0){f s=-b-sqrt(q);if(s.01)t=s,n=!(p+d*t),m=2;}}return m;}v S(v o,v d){f t ;v n;i m=T(o,d,t,n);if(!m)return v(.7, .6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R(),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l% n;if(b<0||T(h,l,t,n))b=0;f p=pow(l%r*(b >0),99);if(m&1){h=h*.2;return((i)(ceil(h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b *.2+.1);}return v(p,p,p)+S(h,r)*.5;}i main(){printf("P6 512 512 255 ");v g=!v (-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a)*.002,c=(a+b)*-256+g;for(i y=512;y--;) for(i x=512;x--;){v p(13,13,13);for(i r =64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)* 99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b *(y+R())+c)*16))*3.5+p;}printf("%c%c%c" ,(i)p.x,(i)p.y,(i)p.z);}}

Код выше выглядит… пугающе, но компилируется и запускается без проблем! Вы можете сохранить его на рабочем столе как card.cpp , открыть консоль и ввести:

C++ -O3 -o card card.cpp ./card > card.ppm

Через 27 секунд на экране появится следующее изображение:

Возможности визитки-трассировщика лучей

Возможности просто поражают!

• мир, состоящий из строго организованных сфер;
• текстурированный пол;
• небо с градиентом;
• мягкие тени;
• OMG, глубина резкости! Вы шутите?!

И все это на одной стороне визитной карточки! Посмотрим, как это работает.

Класс Vector

Рассмотрим первую часть кода:

#include // card > aek.ppm #include #include typedef int i;typedef float f;struct v{ f x,y,z;v operator+(v r){return v(x+r.x ,y+r.y,z+r.z);}v operator*(f r){return v(x*r,y*r,z*r);}f operator%(v r){return x*r.x+y*r.y+z*r.z;}v(){}v operator^(v r){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r. y-y*r.x);}v(f a,f b,f c){x=a;y=b;z=c;}v operator!(){return*this*(1/sqrt(*this%* this));}};

Главная хитрость здесь - это сокращение ключевых слов типов int и float до i и f с помощью typedef . Другой ход, с помощью которого можно можно уменьшить количество кода - это класс v , используемый не только в качестве вектора, но и для обработки пикселей.

#include // card > aek.ppm #include #include typedef int i; // Экономим место с помощью сокращения int до i typedef float f; // Экономим еще больше места с f вместо float // Класс вектора с конструктором и операторами struct v{ f x,y,z; // Три координаты вектора v operator+(v r){return v(x+r.x,y+r.y,z+r.z);} // Сумма векторов v operator*(f r){return v(x*r,y*r,z*r);} // Масштабирование векторов f operator%(v r){return x*r.x+y*r.y+z*r.z;} // Скалярное произведение векторов v(){} // Пустой конструктор v operator^(v r){return v(y*r.z-z*r.y,z*r.x-x*r.z,x*r.y-y*r.x);} // Векторное произведение векторов v(f a,f b,f c){x=a;y=b;z=c;} // Конструктор v operator!(){return *this*(1 /sqrt(*this%*this));} // Нормализация вектора };

Rand() и данные для генерации мира

i G={247570,280596,280600, 249748,18578,18577,231184,16,16};f R(){ return(f)rand()/RAND_MAX;}

Следующий код также экономит много места с помощью объявления функции R , которая возвращает случайное значение от 0 до 1 типа float. Это полезно при стохастическом сэмплировании, использующемся для blur-эффекта и мягких теней.

Массив G содержит в себе закодированное целыми числами положение сфер в мире. Совокупность всех чисел - это битовый вектор из 9 строк и 19 столбцов.

Вот код, приведенный выше, но отформатированный и с комментариями:

// Набор позиций сфер, описывающий мир // Все эти числа, по сути, являются по сути битовым вектором i G={247570,280596,280600,249748,18578,18577,231184,16,16}; // Генератор случайных чисел, возвращающий число с плавающей точкой в диапазоне 0-1 f R(){return(f)rand()/RAND_MAX;}

Главный метод

i main(){printf("P6 512 512 255 ");v g=!v (-6,-16,0),a=!(v(0,0,1)^g)*.002,b=!(g^a)*.002,c=(a+b)*-256+g;for(i y=512;y--;) for(i x=512;x--;){v p(13,13,13);for(i r =64;r--;){v t=a*(R()-.5)*99+b*(R()-.5)* 99;p=S(v(17,16,8)+t,!(t*-1+(a*(R()+x)+b *(y+R())+c)*16))*3.5+p;}printf("%c%c%c" ,(i)p.x,(i)p.y,(i)p.z);}}

Главный метод использует простой известный основанный на тексте формат изображений PPM. Изображение состоит из заголовка вида P6 [Ширина] [Высота] [Максимальное значение] , за которым следует RGB-значение каждого пикселя.

Для каждого пикселя на изображении программа сэмплирует (S) цвет 64 лучей, аккумулирует результат и выводит его в stdout .

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

Вот код, приведенный выше, но отформатированный и с комментариями:

// Главная функция. Выводит изображение. // Использовать программу просто: ./card > erk.ppm i main(){ printf("P6 512 512 255 "); // Заголовок PPM // Оператор "!" осуществляет нормализацию вектора v g=!v(-6,-16,0), // Направление камеры a=!(v(0,0,1)^g)*.002, // Вектор, отвечающий за высоту камеры... b=!(g^a)*.002, // Правый вектор, получаемый с помощью векторного произведения c=(a+b)*-256+g; // WTF? Вот здесь https:// news.ycombinator.com/item?id=6425965 написано про это подробнее. for(i y=512;y--;) // Для каждого столбца for(i x=512;x--;){ // Для каждого пикселя в строке // Используем класс вектора, чтобы хранить цвет в RGB v p(13,13,13); // Стандартный цвет пикселя - почти черный // Бросаем по 64 луча из каждого пикселя for(i r=64;r--;){ // Немного меняем влево/вправо и вверх/вниз координаты начала луча (для эффекта глубины резкости) v t=a*(R()-.5)*99+b*(R()-.5)*99; // Назначаем фокальной точкой камеры v(17,16,8) и бросаем луч // Аккумулируем цвет, возвращенный в переменной t p=S(v(17,16,8)+t, // Начало луча!(t*-1+(a*(R()+x)+b*(y+R())+c)*16) // Направление луча с небольшим искажением // ради эффекта стохастического сэмплирования)*3.5+p; // +p для аккумуляции цвета } printf("%c%c%c",(i)p.x,(i)p.y,(i)p.z); } }

Сэмплер

v S(v o,v d){f t ;v n;i m=T(o,d,t,n);if(!m)return v(.7, .6,1)*pow(1-d.z,4);v h=o+d*t,l=!(v(9+R(),9+R(),16)+h*-1),r=d+n*(n%d*-2);f b=l% n;if(b<0||T(h,l,t,n))b=0;f p=pow(l%r*(b >0),99);if(m&1){h=h*.2;return((i)(ceil(h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b *.2+.1);}return v(p,p,p)+S(h,r)*.5;}

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

Обратите внимание на вызов функции R при расчете направления света. Таким образом создается эффект «мягких теней».

Вот код, приведенный выше, но отформатированный и с комментариями:

// (S)эмплируем мир и возвращаем цвет пикселя по // по лучу, начинающемуся в точке o (Origin) и имеющему направление d (Direction) v S(v o,v d){ f t; v n; // Проверяем, натыкается ли луч на что-нибудь i m=T(o,d,t,n); if(!m) // m==0 // Сфера не была найдена, и луч идет вверх: генерируем цвет неба return v(.7,.6,1)*pow(1-d.z,4); // Возможно, луч задевает сферу v h=o+d*t, // h - координата пересечения l=!(v(9+R(),9+R(),16)+h*-1), // "l" = направление света (с небольшим искажеем для эффекта мягких теней) r=d+n*(n%d*-2); // r = полувектор // Расчитываем коэффицент Ламберта f b=l%n; // Рассчитываем фактор освещения (коэффицент Ламберта > 0 или находимся в тени)? if(b<0||T(h,l,t,n)) b=0; // Рассчитываем цвет p (с учетом диффузии и отражения света) f p=pow(l%r*(b>0),99); if(m&1){ // m == 1 h=h*.2; // Сфера не была задета, и луч уходит вниз, в пол: генерируем цвет пола return((i)(ceil(h.x)+ceil(h.y))&1?v(3,1,1):v(3,3,3))*(b*.2+.1); } // m == 2 Была задета сфера: генерируем луч, отскакивающий от поверхности сфера return v(p,p,p)+S(h,r)*.5; // Ослабляем цвет на 50%, так как он отскакивает от поверхности (* .5) }

Трэйсер

i T(v o,v d,f &t,v&n){t=1e9;i m=0;f p=-o.z/d.z;if(.01 0){f s=-b-sqrt(q);if(s.01)t=s,n=!(p+d*t),m=2;}}return m;}

Функция T (Tracer) отвечает за бросание луча из данной точки (o) в данном направлении (d). Она возвращает целое число, которое является кодом для результата бросания луча. 0 - луч ушел в небо, 1 - луч ушел в пол, 2 - луч наткнулся на сферу. Если была задета сфера, то функция обновляет переменные t (параметр, используемый для вычисления дистанции пересения) и n (полу-вектор при отскакивании от сферы).

Вот код, приведенный выше, но отформатированный и с комментариями:

// Тест на пересечение для линии // Возвращаем 2, если была задета сфера (а также дистанцию пересечения t и полу-вектор n). // Возвращаем 0, если луч ничего не задевает и идет вверх, в небо // Возвращаем 1, если луч ничего не задевает и идет вниз, в пол i T(v o,v d,f& t,v& n){ t=1e9; i m=0; f p=-o.z/d.z; if(.010){ // Да. Считаем расстояние от камеры до сферы f s=-b-sqrt(q); if(s.01) // Это минимальное расстояние, сохраняем его. А также // вычиваем вектор отскакивающего луча и записываем его в "n" t=s, n=!(p+d*t), m=2; } } return m; }

Число Leet

Многие программисты пытались сократить код еще больше. Сам автор остановился на версии, предоставленной в этой статье. Знаете, почему?

Fabien$ wc card.cpp 35 95 1337 card.cpp - много математики, но все очень подробно и ясно объясняется.

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

Рис. 8.12. Модели отражения: а – идеальное зеркало, б - неидеальное зеркало, в – диффузное, г – сумма диффузного и зеркального, д – обратное, е - сумма диффузного, зеркального и лбратного

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

излучают;

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

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

Рис. 8.13. Излучение – а – раномерно во все тороны, б - направленно

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

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

В предшествующих параграфах мы с вами уже ознакомились с видами отражения, которые упоминаются наиболее часто - зеркальным и диффузным. Реже в литературе поминается обратное зеркальное или антизеркальное от­ ражение, в котором максимум интенсивности отражения соответствует направлению на источник. Обратное зеркальное отражение имеют некоторые виды растительности на по­верхности Земли, наблюдаемые с высоты рисовые поля.

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

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

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

Рис. 8.14. Преломление а – идеальное, б - дифузное

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

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

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

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

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

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

Рис. 8.15. Схема обратной трассировки лучей

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

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

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

Рис. 8.16. Обратная трассировка для объектов, имеющих свойства зеркального отражения и преломления

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

Для идеального зеркала дос­таточно потом проследить лишь очередную точку пересечения вторичного луча с некоторым объектом. Что означает термин "идеальное зеркало"? Будем считать, что такое зеркало имеет идеально равную отполированную поверхность, поэтому одному отраженному лучу соответствует только один падающий луч. Зеркало может быть затемненным, то есть поглощать часть световой энергии, но все равно выполняется правило: один луч падает - один отражается. Можно рассматривать также "неидеальное зеркало".Это будет означать, что поверхность неровная. Направлению отраженного луча будут соот­ветствовать несколько падающих лучей (или наоборот, один падающий луч порождает не­сколько отраженных лучей), которые образуют некоторый конус, возможно, несимметрич­ный, с осью вдоль линии падающего луча идеального зеркала. Конус соответствует некото­рому закону распределения интенсивностей, простейший из которых описывается моделью Фонга - косинус угла, возведенный в некоторую степень. Неидеальное зеркало резко ус­ложняет трассировку - нужно проследить не один, а множество падающих лучей, учиты­вать взнос излучения от других видимых из данной точки объектов.

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

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

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

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

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

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

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

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

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

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

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

7. Для завершения трассировки вводят некоторое предельное значение освещенности, ко­торое уже не должно вносить взнос в результирующий цвет, или ограничивают количе­ство итераций.

Согласно модели Уиттеда цвет некоторой точки объекта определяется суммарной интенсивностью

I( ) = KaIa( )C( ) + KdId( )C( ) + KsIs( ) + KrIr( ) + KtIt( )

где λ - длина волны,

С (λ) - заданный исходный цвет точки объекта,

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

I a - интенсивность фонового подсвечивания,

I d - интенсивность, учитываемая для диффузного рассеивания,

I s - интенсивность, учитываемая для зеркальности,

I r - интенсивность излучения, приходящего по отраженному лучу,

I t - интенсивность излучения, приходящего по преломленному лучу.

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

I d =

где I i (λ) - интенсивность излученияi - ro источника света, θ i - угол между нормалью к по­верхности объекта и направлением наi - vi источник света.

Для зеркальности:

I d =

где р - показатель степени от единицы до нескольких сотен (согласно модели Фонга),α i -угол между отраженным лучом (обратной трассировки) и направлением на г"-й источник света.

Интенсивности излучений проходящих по отраженному лучу (I r ), а так же по преломленному лучу (I t ) , умножают на коэффициент, учитывающий ослабление интенсивности в зависимости от расстояния, пройденного лучом. Такой коэффициент записывается в виде е -  d где d - пройденное расстояние,  – параметр ослабления, учитывающий свойства среды, в которой распространяется луч.

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

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

Известно несколько способов проверки произвольной точки на принадлежность полиго­ну. Рассмотрим две разновидности, в сущности, одного и того же метода (рис. 8.17).

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

Рис. 8.17. Точка – внутренняя, если: а - точка принадлежит секущему отрезку, б – число пересечений нечетное

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

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

Сделаем общие выводы о относительно метода обратной трассировки лучей.

Положительные черты

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

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

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

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

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

Недостатки

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

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