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

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

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

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

Обратная трассировка. Метод обратной трассировки разработан в 80-х годах. Основополагающими считаются работы Уиттеда и Кея.

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

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

● луч выходит за пределы сцены,

● луч встречается с непрозрачным телом, поглощающим свет,

● луч попадает в источник света,

● интенсивность луча падает ниже порога чувствительности,

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

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

Метод обратной трассировки фактически аккумулирует все лучи, в действительности приходящие в приемник из определенного направления независимо от их начала. Это позволяет видеть и изображать на экране:

● непрозрачные объекты, поглощающие обратные лучи;

● прозрачные объекты, через которые благодаря преломлению наблюдателю видны другие объекты;

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

● тени, образующиеся в точках поверхности, заслоненных от источника другими объектами;

● другие разнообразные оптические эффекты.

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

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

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

Ограничения метода обратной трассировки:

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

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

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

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

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

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

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

Положительные черты метода обратной трассировки:

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

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

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

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

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

Недостатки метода обратной трассировки:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

технологий

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

«Анализ перспективности использования метода трассировки лучей в 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 Падения света на впадены в шаре(слева А, справа Б)

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

Недавно в интернете я наткнулся на трассировщик лучей на визитке Пола Гекберта. Для тех, кто не в курсе: это очень известная задача, изначально предложенная Полом Гекбертом 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 - много математики, но все очень подробно и ясно объясняется.