Трёхмерная графика с нуля. Часть 1: трассировка лучей

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

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

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



Хотя их возможности во многом пересекаются, они не аналогичны, поэтому в статье рассматриваются их сильные стороны:



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

Зачем читать эту статью?

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

1. Шейдеры. В первых видеопроцессорах алгоритмы были жёстко заданы в «железе», но в современных программист должен писать собственные шейдеры. Другими словами, вам всё равно нужно реализовывать большие фрагменты ПО рендеринга, только теперь оно выполняется в видеопроцессоре.
2. Понимание. Вне зависимости от того, используете ли вы готовый конвейер или пишете свои шейдеры, понимание того, что происходит за кулисами позволит вам оптимальнее использовать готовый конвейер и писать шейдеры лучше.
3. Интересность. Немногие области информатики могут похвастаться возможностью мгновенного получения видимых результатов, которые даёт нам компьютерная графика. Чувство гордости после запуска выполнения первого запроса SQL несравнимо с тем, что вы чувствуете в первый раз, когда удастся правильно оттрассировать отражения. Я преподавал компьютерную графику в университете в течение пяти лет. Меня часто удивляло, как мне удавалось семестр за семестром получать удовольствие: в конце концов мои усилия оправдывали себя радостью студентов от того, что они могли использовать свои первые рендеры в качестве обоев рабочего стола.

Общие концепции

Холст (Canvas)

В процессе работы мы будем рисовать объекты на холсте (canvas). Холст — это прямоугольный массив пикселей, которые можно индивидуально раскрашивать. Будет ли он отображаться на экране, печататься на бумаге или использоваться как текстура при последующем рендеринге? Для нашей работы это не важно: мы сосредоточимся на рендеринге изображений на этом абстрактном прямоугольном массиве пикселей.

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

canvas.PutPixel(x, y, color)

Теперь мы изучим параметры этого метода — координаты и цвета.

Системы координат

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



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



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

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

Цветовые модели

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

Цветом называется способ интерпретации мозгом фотонов, попадающих в наш глаз. Эти фотоны переносят энергию различной частоты, наши глаза связывают эти частоты с цветами. Наименьшая воспринимаемая нами энергия имеет частоту примерно 450 ТГц, мы воспринимаем её как красный цвет. На другом конце спектра находятся 750 ТГц, которые мы видим как «фиолетовый». Между этими двумя частотами мы видим непрерывный спектр цветов, (например, зелёный — это примерно 575 ТГц).

В обычном состоянии мы не можем видеть частоты за пределами этого диапазона. Более высокие частоты несут большую энергию, поэтому инфракрасное излучение (частоты ниже 450 ТГц) безвредно, но ультрафиолет (частоты выше 750 ТГц) может обжечь кожу.

Любой цвет можно описать как различные сочетания этих цветов (в частности, «белый» — это сумма всех цветов, а «чёрный» — отсутствие всех цветов). Описывать цвета указанием точной частоты неудобно. К счастью, можно создать почти все цвета как линейную комбинацию всего трёх цветов, которые мы называем «основными цветами».

Субтрактивная цветовая модель

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

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

Однако эта модель не совсем верна. На самом деле основными цветами в субтрактивной модели являются не синий, красный и жёлтый, как учат детей и студентов, а голубой (Cyan), пурпурный (Magenta) и жёлтый (Yellow). Более того, смешение трёх основных цветов даёт какой-то темноватый цвет, который не совсем похож на чёрный, поэтому в качестве четвёртого «основного» цвета добавляется чёрный. Чёрный обозначается буквой K — и так получается цветовая модель CMYK, используемая для принтеров.

Аддитивная цветовая модель

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

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

Забудем о подробностях

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

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

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

Глубина и представление цвета

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

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

В самом популярном сегодня формате используется по 8 бит на основной цвет (также называемый цветовым каналом). 8 бит на канал дают нам 24 бита на пискель, то есть всего различных цветов (приблизительно 16,7 миллионов). Этот формат, известный как 888, мы и будем использовать в нашей работе. Можно сказать, что этот формат имеет глубину цвета 24 бит.

Однако он ни в коем случае не является единственным возможным форматом. Не так давно для экономии памяти были популярны 15-битные и 16-битные форматы, назначавшие по 5 бит на канал или 5 бит для красного, 6 для зелёного и 5 для синего (этот формат был известен как 565). Почему зелёный цвет получил лишний бит? Потому что наши глаза более чувствительны к изменениям зелёного, чем красного или синего.

16 бит дают нам цветов (примерно 65 тысяч). Это значит, что мы получаем один цвет для каждых 256 цветов 24-битного режима. Хотя 65 тысяч — это много, на изображениях с постепенно меняющимися цветами можно заметить очень небольшие «ступеньки», которые незаметны в 16,7 миллионах цветов, потому что там достаточно бит для представления промежуточных цветов. 16,7 миллионов цветов — это ещё и больше, чем может распознать человеческий глаз, поэтому в обозримом будущем мы скорее всего продолжим использовать 24-битные цвета. (Примечание: это относится только к отображению изображений, хранение изображений с более широким диапазоном — это совершенно другой вопрос, который мы рассмотрим в главе «Освещение».)

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

Управление цветом

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

Мы можем увеличить яркость цвета, увеличив каждый цветовой канал на константу:

Мы можем сложить два цвета, сложив отдельно цветовые каналы:

Например, если у нас есть красновато-фиолетовый

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

Внимательный читатель может сказать, что при таких операциях мы можем получить неверные значения: например, удвоив яркость , мы получим значение R вне цветового диапазона. Мы будем считать любое значение больше 255 равным 255, а любое значение меньше 0 равным 0. Это более-менее аналогично тому, когда вы делаете снимок со слишком большой или малой выдержкой — на нём появляются совершенно чёрные или совершенно белые области.

Сцена

Холст (canvas) — это абстракция, на которой мы всё рендерим. Что же мы рендерим? Ещё одну абстракцию — сцену.

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

Для того, чтобы говорить об объектах в сцене, нам нужна система координат. Выбрать можно любую, но мы подберём что-нибудь полезное для наших целей. Ось Y будет направлена вверх. Оси X и Z горизонтальны. То есть плоскость XZ будет «полом», а XY и YZ — вертикальными «стенами».

Поскольку мы говорим здесь о «физических» объектах, то нужно выбрать единицы их измерения. Они тоже могут быть любыми, но сильно зависят от того, что представлено в сцене. «1» может быть одним миллиметром при моделировании кружки, или одной астрономической единицей при моделировании Солнечной системы. К счастью, ничто из описанного ниже не зависит от единиц измерения, поэтому мы просто проигнорируем их. Пока мы сохраняем единообразие (т.е. «1» всегда означает для всей сцены одно и то же), то всё будет работать нормально.

Часть I: трассировка лучей

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


Швейцарский ландшафт

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

Не обязательно. Может у вас и нет таланта, но есть методичность.

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

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


Грубая аппроксимация ландшафта

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

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

Очень просто!

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

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

Это по-прежнему слишком абстрактно, но уже начинает походить на алгоритм. Удивительно, но это и есть высокоуровневое описание всего алгоритма трассировки лучей. Да, всё настолько просто.

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

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

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

Во-первых, мы будем считать, что точка обзора фиксирована. Точка обзора — это место, в котором располагается глаз в нашей аналогии, и оно обычно называется положением камеры; давайте назовём его . Мы будем считать, что камера расположена в начале системы координат, то есть .

Во-вторых, мы будем считать, что ориентация камеры тоже фиксирована, то есть камера всегда направлена в одно и то же место. Будем считать, что она смотрит вниз по положительной оси Z, положительная ось Y направлена вверх, а положительная ось X — вправо:



Положение и ориентация камеры теперь фиксированы. Но у нас всё ещё нет «рамки» из предложенной нами аналогии, через которую мы смотрим на сцену. Будем считать, что рамка имеет размеры и , она фронтальна относительно положения камеры (то есть перпендикулярна ) и находится на расстоянии , её стороны параллельны осям X и Y, и она центрирована относительно . Описание выглядит сложно, но на самом деле всё довольно просто:



Этот прямоугольник, который будет нашим окном в мир, называется окном просмотра (viewport). В сущности, мы будем рисовать на холсте всё то, что видим через окно просмотра. Важно, что размер окна просмотра и расстояние до камеры определяют угол видимости из камеры, называемый областью видимости (field of view) или для краткости FOV. У людей FOV по горизонтали составляет почти , однако большая часть его составляет смутное периферическое зрение без ощущения глубины. В общем случае достоверные изображения получаются при использовании FOV в вертикальном и горизонтальном направлении; этого можно достичь, задав .

Давайте вернёмся к «алгоритму», представленному в предыдущем разделе, обозначим его шаги цифрами:

Разместить глаз и рамку в нужных местах (1)
Для каждого пикселя холста
    Определить квадрат сетки, соответствующий этому пикселю (2)
    Определить цвет, видимый сквозь этот квадрат (3)
    Закрасить пиксель этим цветом (4)

Мы уже выполнили шаг 1 (или, если точнее, избавились от него на время). Шаг 4 тривиален (canvas.PutPixel(x, y, color) ). Давайте вкратце рассмотрим шаг 2, а затем сосредоточимся на гораздо более сложных способах реализации шага 3.

Из холста в окно просмотра

На шаге 2 нам нужно "Определить квадрат сетки, соответствующий этому пикселю". Мы знаем координаты пикселя на холсте (мы рисуем их все) — давайте назовём их и . Заметьте, как удобно мы расположили окно просмотра — его оси соответствуют ориентации осей холста, а его центр соответствует центру окна просмотра. То есть перейти от координат холста к координатам пространства можно простым изменением масштаба!

Есть ещё одна тонкость. Хотя окно просмотра двухмерно, оно встроено в трёхмерное пространство. Мы указали, что оно находится на расстоянии d от камеры. У каждой точки в этой плоскости (называемой плоскостью проекции) по определению . Следовательно,

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

Трассируем лучи

Так через какого же цвета достигает свет после прохождения через ?

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

Вместо этого мы будем трассировать лучи «в обратном порядке» — мы начнём с луча, находящегося на камере, проходящего через точку в окне просмотра и двигаясь, пока он не столкнётся с каким-нибудь объектом в сцене. Этот объект будет «виден» из камеры через эту точку окна просмотра. То есть в качестве первого приближения мы просто возьмём цвет этого объекта как «цвет света, прошедшего через эту точку».



Теперь нам нужно всего лишь несколько уравнений.

Уравнение лучей

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

где t — произвольное действительное число.

Давайте обозначим , то есть направление луча, как ; тогда уравнение примет простой вид

Подробнее можно прочитать об этом в линейной алгебре; интуитивно понятно, что если мы начнём из начальной точки и продвинемся на какое-нибудь кратное направления луча, то всегда будем двигаться вдоль луча:

Уравнение сферы

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

Что такое сфера? Сфера — это множество точек, лежащих на постоянном расстоянии (называемом радиусом сферы) от фиксированной точки (называемой центром сферы):



Заметьте, что судя по определению, сферы являются полыми.

Если C — центр сферы, а r — радиус сферы, то точки P на поверхности сферы удовлетворяют следующему уравнению:

Давайте немного поэкспериментируем с этим уравнением. Расстояние между P и C- это длина вектора из P в C:

Длина вектора — это квадратный корень его скалярного произведения на себя:

И чтобы избавиться от квадратного корня,

Луч встречается со сферой

Теперь у нас есть два уравнения, одно из которых описывает точки сферы, а другое — точки луча:

Точка P, в которой луч падает на сферу, является одновременно и точкой луча, и точкой на поверхности сферы, поэтому она должна удовлетворять обоим уравнениям одновременно. Заметьте, что единственная переменная в этих уравнениях — это параметр t, потому что O, , C и r заданы, а P — это точка, которую нам нужно найти.

Поскольку P — это одна и та же точка в обоих уравнениях, мы можем заменить P в первом на выражение для P во втором. Это даёт нам

Какие значения t удовлетворяют этому уравнению?

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

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

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

Преобразовав его немного, получим

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

Стало ли оно менее громоздким? Заметьте, что скалярное произведение двух векторов является действительным числом, поэтому каждый член в скобках является действительным числом. Если мы обозначим их названиями, то получим что-то гораздо более знакомое:

Это ничто иное, как старое доброе квадратное уравнение. Его решение даёт нам значения параметра t, при которых луч пересекается со сферой:

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



Если мы возьмём значение t и вставим его в уравнение луча, то наконец получим точку пересечения P, соответствующее этому значению t.

Рендеринг наших первых сфер

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

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

Однако стоит уделить особое внимание параметру t. Вернёмся к уравнению луча:

Поскольку исходная точка и направление луча постоянны, меняя t во множестве действительных чисел, мы получим каждую точку P на этом луче. Заметьте, что при мы получим , а при мы получим . При отрицательных числах мы получим точки в противоположном направлении, то есть за камерой. То есть мы можем разделить область параметров на три части:

	За камерой
	Между камерой и плоскостью проекции
	Сцена

Вот схема области параметров:


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

С другой стороны, нам не нужно устанавливать верхний предел значения t; мы хотим видеть объекты перед камерой, вне зависимости от того, насколько они далеко. Поскольку на более поздних этапах мы будем ограничивать длину луча, то нам всё-таки нужно добавить эту формальность и ограничить t верхним значением (Примечание: в языках, в которых нельзя непосредственно задать бесконечность, достаточно будет очень большого числа.)

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

Основной метод теперь выглядит так:

O = <0, 0, 0>
for x in [-Cw/2, Cw/2] {
    for y in [-Ch/2, Ch/2] {
        D = CanvasToViewport(x, y)
        color = TraceRay(O, D, 1, inf)
        canvas.PutPixel(x, y, color)
    }
}

Функция CanvasToViewport очень проста:

CanvasToViewport(x, y) {
    return (x*Vw/Cw, y*Vh/Ch, d)
}

В этом фрагменте кода d — это расстояние до плоскости проекции.

Метод TraceRay вычисляет пересечение луча с каждой сферой, и возвращает цвет сферы в ближайшей точке пересечения, которая находится в требуемом интервале t:

TraceRay(O, D, t_min, t_max) {
    closest_t = inf
    closest_sphere = NULL
    for sphere in scene.Spheres {
        t1, t2 = IntersectRaySphere(O, D, sphere)
        if t1 in [t_min, t_max] and t1 < closest_t
            closest_t = t1
            closest_sphere = sphere
        if t2 in [t_min, t_max] and t2 < closest_t
            closest_t = t2
            closest_sphere = sphere
    }
    if closest_sphere == NULL
        return BACKGROUND_COLOR
    return closest_sphere.color
}

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

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

И, наконец, IntersectRaySphere просто решает квадратное уравнение:

IntersectRaySphere(O, D, sphere) {
    C = sphere.center
    r = sphere.radius
    oc = O - C

    k1 = dot(D, D)
    k2 = 2*dot(OC, D)
    k3 = dot(OC, OC) - r*r

    discriminant = k2*k2 - 4*k1*k3
    if discriminant < 0:
        return inf, inf

    t1 = (-k2 + sqrt(discriminant)) / (2*k1)
    t2 = (-k2 - sqrt(discriminant)) / (2*k1)
    return t1, t2
}

Давайте зададим очень простую сцену:



На псевдоязыке сцены она будет задана примерно так:

viewport_size = 1 x 1
projection_plane_d = 1
sphere {
    center = (0, -1, 3)
    radius = 1
    color = (255, 0, 0)  # Красный
}
sphere {
    center = (2, 0, 4)
    radius = 1
    color = (0, 0, 255)  # Синий
}
sphere {
    center = (-2, 0, 4)
    radius = 1
    color = (0, 255, 0)  # Зелёный
}

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



Исходный код и рабочее демо >>

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

Освещение

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

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

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

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

Источники освещения

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

Точечные источники

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

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

Давайте зададим вектор как направление из точки P в сцене к источнику освещения Q. Этот вектор, называемый световым вектором, просто равен . Заметьте, что поскольку Q фиксирована, а P может быть любой точкой сцены, то в общем случае будет разным для каждой точки сцены.

Направленные источники

Если точечный источник является хорошей аппроксимацией лампы накаливания, то что может служить аппроксимацией Солнца?

Это хитрый вопрос, и ответ зависит от того, что вы хотите отрендерить.

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

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

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

В случае точечных источников нам нужно вычислять новый световой вектор для каждой точки P сцены, но в этом случае задан. В сцене с Солнцем и Землёй будет равен .

Окружающее освещение

Можно ли смоделировать любое освещение реального мира как точечный или направленный источник? Почти всегда да (Примечание: но это необязательно будет просто; зональное освещение (представьте источник за рассеивателем) можно аппроксимировать множеством точечных источников на его поверхности, но это сложно, более затратно по вычислениям, а результаты оказываются неидеальными.). Достаточно ли этих двух типов источников для наших целей? К сожалению, нет.

Представьте, что происходит на Луне. Единственным значимым источником освещения поблизости является Солнце. То есть «передняя половина» Луны относительно Солнца получает всё освещение, а «задняя половина» находится в полной темноте. Мы видим это с разных углов на Земле, и этот эффект создаёт то, что мы называем «фазами» Луны.

Однако ситуация на Земле немного отличается. Даже точки, не получающие освещения непосредственно от источника освещения, не находятся полностью в темноте (просто посмотрите на пол под столом). Как лучи света достигают этих точек, если «обзор» на источники освещения чем-то перекрыт?

Как я упомянул в разделе Цветовые модели, когда свет падает на объект, часть его поглощается, но остальная часть рассеивается в сцене. Это значит, что свет может поступать не только от источников освещения, но и от других объектов, получающих его от источников освещения и рассеивающих его обратно. Но зачем останавливаться на этом? Рассеянное освещение в свою очередь падает на какой-нибудь другой объект, часть его поглощается, а часть снова рассеивается в сцене. При каждом отражении свет теряет часть своей яркости, но теоретически можно продолжать ad infinitum (Примечание: на самом деле нет, потому что свет имеет квантовую природу, но достаточно близко к этому.).

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

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

Освещённость одной точки

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

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

Итак, что произойдёт, когда луч света с направлением из направленного или точечного источника падает на точку P какого-нибудь объекта в нашей сцене?

Интуитивно мы можем разбить объекты на два общих класса, в зависимости от того, как они ведут себя со светом: «матовые» и «блестящие». Поскольку большинство окружающих нас предметов можно считать «матовыми», то с них мы и начнём.

Диффузное рассеяние

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

Чтобы убедиться в этом, внимательно посмотрите на какой-нибудь матовый объект, например, на стену: если двигаться вдоль стены, её цвет не меняется. То есть, видимый вами свет, отражённый от объекта, одинаков вне зависимости от того, в какое место объекта вы смотрите.

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



Чтобы выразить это математически, давайте охарактеризуем ориентацию поверхности по её вектору нормали. Вектор нормали, или просто «нормаль» — это вектор, перпендикулярный поверхности в какой-то точке. Также он является единичным вектором, то есть его длина равна 1. Мы будем называть этот вектор .

Моделирование диффузного отражения

Итак, луч света с направлением и яркостью падает на поверхность с нормалью . Какая часть отражается обратно сцену как функция от , и ?

Для геометрической аналогии давайте представим яркость света как «ширину» луча. Его энергия распределяется по поверхности размером . Когда и имеют одно направление, то есть луч перпендикулярен поверхности, , а это значит, что энергия, отражённая на единицу площади равна падающей энергии на единицу площади; <. С другой стороны, когда угол между и приближается к , приближается к , то есть энергия на единицу площади приближается к 0; . Но что происходит в промежутках?

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



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

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

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

Один из углов равен , а другой — . Тогда третий угол равен . Но нужно заметить, что и тоже образуют прямой угол, то есть тоже должны быть . Следовательно, :



Давайте рассмотрим треугольник . Его углы равны , и . Сторона равна , а сторона равна .

И теперь… тригонометрия спешит на помощь! По определению ; заменяем на , а на , и получаем

что преобразуется в

Мы почти закончили. — это угол между и , то есть можно выразить как

И наконец

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

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

Уравнение диффузного отражения

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

Стоит снова повторить, что члены, в которых не должны прибавляться к освещённости точки.

Нормали сферы

Здесь только отсутствует единственная мелочь: откуда берутся нормали?

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



Почему я написал «направление нормали», а не «нормаль»? Кроме перпендикулярности к поверхности, нормаль должна быть единичным вектором; это было бы справедливо, если бы радиус сферы был равен , что не всегда верно. Для вычисления самой нормали нам нужно разделить вектор на его длину, получив таким образом длину :

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

Рендеринг с диффузным отражением

Давайте переведём всё это в псевдокод. Во-первых, давайте добавим в сцену пару источников освещения:

light {
    type = ambient
    intensity = 0.2
}
light {
    type = point
    intensity = 0.6
    position = (2, 1, 0)
}
light {
    type = directional
    intensity = 0.2
    direction = (1, 4, 4)
}

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

Уравнение освещения довольно просто преобразовать в псевдокод:

ComputeLighting(P, N) {
    i = 0.0
    for light in scene.Lights {
        if light.type == ambient {
            i += light.intensity
        } else {
            if light.type == point
                L = light.position - P
            else
                L = light.direction

            n_dot_l = dot(N, L)
            if n_dot_l > 0
                i += light.intensity*n_dot_l/(length(N)*length(L))
        }
    }
    return i
}

И единственное, что осталось — использовать ComputeLighting в TraceRay. Мы заменим строку, возвращающую цвет сферы

    return closest_sphere.color

на этот фрагмент:

    P = O + closest_t*D  # вычисление пересечения
    N = P - closest_sphere.center  # вычисление нормали сферы в точке пересечения
    N = N / length(N)
    return closest_sphere.color*ComputeLighting(P, N)

Просто ради интереса давайте добавим большую жёлтую сферу:

sphere {
    color = (255, 255, 0)  # Yellow
    center = (0, -5001, 0)
    radius = 5000
}

Мы запускаем рендерер, и узрите — сферы наконец начали выглядеть как сферы!



Исходный код и рабочее демо >>

Но постойте, как большая жёлтая сфера превратилась в плоский жёлтый пол?

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

Отражение от гладкой поверхности

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

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

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

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



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



В зависимости от степени «отполированности» поверхности, она более или менее похожа на зеркало; то есть мы получаем «зеркальное» отражение (specular reflection, от латинского «speculum», то есть «зеркало»).

Для идеально отполированного зеркала падающий луч света отражается в единственном направлении . Именно это позволяет нам чётко видеть объекты в зеркале: для каждого падающего луча есть единственный отражённый луч . Но не каждый объект отполирован идеально; хотя бОльшая часть света отражается в направлении , часть его отражается в направлениях, близких к ; чем ближе к , тем больше света отражается в этом направлении. «Блеск» объекта определяет то, насколько быстро отражённый свет уменьшается при отдалении от :



Нас интересует то, как выяснить, какое количество света от отражается обратно в направлении нашей точки обзора (потому что это свет, который мы используем для определения цвета каждой точки). Если — это «вектор обзора», указывающий из в камеру, а — угол между и , то вот, что мы имеем:



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

Моделирование «зеркального» отражения

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

Давайте возьмём . У него есть хорошие свойства: , , а значения постепенно уменьшаются от до по очень красивой кривой:



соответствует всем требованиям к функции «зеркального» отражения, так почему бы не использовать его?

Но нам не хватает ещё одной детали. В такой формулировке все объекты блестят одинаково. Как изменить уравнение для получения различных степеней блеска?

Не забывайте, что этот блеск — мера того, насколько быстро функция отражения уменьшается при увеличении . Очень простой способ получения различных кривых блеска заключается в вычислении степени некоего положительного показателя . Поскольку , то очевидно, что ; то есть ведёт себя точкно так же, как , только «уже». Вот для разных значений :



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

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

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

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

Мы можем разложить на два вектора и , таких, что , где параллелен , а перпендикулярен :



— это проекция на ; по свойствам скалярного произведения и исходя из того, что , длина этой проекции равна . Мы определили, что будет параллелен , поэтому .

Поскольку , мы можем сразу получить .

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



Подставляя полученные ранее выражения, мы получим

и немного упростив, получаем

Значение «зеркального» отражения

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

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

Рендеринг с «зеркальными» отражениями

Давайте добавим в сцену «зеркальные» отражения, над которыми мы сейчас работали. Во-первых, внесём некоторые изменения в саму сцену:

sphere {
    center = (0, -1, 3)
    radius = 1
    color = (255, 0, 0)  # Красный
    specular = 500  # Блестящий
}
sphere {
    center = (-2, 1, 3)
    radius = 1
    color = (0, 0, 255)  # Синий
    specular = 500  # Блестящий
}
sphere {
    center = (2, 1, 3)
    radius = 1
    color = (0, 255, 0)  # Зелёный
    specular = 10  # Немного блестящий
}
sphere {
    color = (255, 255, 0)  # Жёлтый
    center = (0, -5001, 0)
    radius = 5000
    specular = 1000  # Очень блестящий
}

В коде нам нужно изменить ComputeLighting, чтобы он при необходимости вычислял значение «зеркальности» и прибавлял его к общему освещению. Заметьте, что теперь ему требуются и :

ComputeLighting(P, N, V, s) {
    i = 0.0
    for light in scene.Lights {
        if light.type == ambient {
            i += light.intensity
        } else {
            if light.type == point
                L = light.position - P
            else
                L = light.direction

            # Диффузность
            n_dot_l = dot(N, L)
            if n_dot_l > 0
                i += light.intensity*n_dot_l/(length(N)*length(L))

            # Зеркальность
            if s != -1 {
                R = 2*N*dot(N, L) - L
                r_dot_v = dot(R, V)
                if r_dot_v > 0
                    i += light.intensity*pow(r_dot_v/(length(R)*length(V)), s)
            }
        }
    }
    return i
}

И наконец нам нужно изменить TraceRay, чтобы он передавал новые параметры ComputeLighting. очевиден; он берётся из данных сферы. Но как насчёт ? — это вектор, указывающий от объекта в камеру. К счастью, в TraceRay у нас уже есть вектор, направленный из камеры к объекту — это , направление трассируемого луча! То есть — это просто .

Вот новый код TraceRay с «зеркальным» отражением:

TraceRay(O, D, t_min, t_max) {
    closest_t = inf
    closest_sphere = NULL
    for sphere in scene.Spheres {
        t1, t2 = IntersectRaySphere(O, D, sphere)
        if t1 in [t_min, t_max] and t1 < closest_t
            closest_t = t1
            closest_sphere = sphere
        if t2 in [t_min, t_max] and t2 < closest_t
            closest_t = t2
            closest_sphere = sphere
    }
    if closest_sphere == NULL
        return BACKGROUND_COLOR

    P = O + closest_t*D  # Вычисление пересечения
    N = P - closest_sphere.center  # Вычисление нормали сферы в точке пересечения
    N = N / length(N)
    return closest_sphere.color*ComputeLighting(P, N, -D, sphere.specular)
}

И вот наша награда за всё это жонглирование векторами:



Исходный код и рабочее демо >>

Тени

Там, где есть свет и объекты, должны быть и тени. Так где же наши тени?

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

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

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

Мы хотим выделить два следующих случая:



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

Давайте начнём с направленного источника. Мы знаем ; это точка, которая нас интересует. Мы знаем ; это часть определения источника освещения. Имея и , мы можем задать луч, а именно , который проходит из точки до бесконечно отдалённого источника освещения. Пересекает ли этот луч другой объект? Если нет, то между точкой и источником ничего нет, то есть мы можем вычислить освещённость от этого источника и прибавить его к общей освещённости. Если пересекает, то мы игнорируем этот источник.

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

Однако параметры немного отличаются. Вместо того, чтобы начинаться с камеры, лучи испускаются из . Направление равно не , а . И нас интересуют пересечения со всем после на бесконечное расстояние; это значит, что и .



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



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

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

Рендеринг с тенями

Давайте превратим это в псевдокод.

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

ClosestIntersection(O, D, t_min, t_max) {
    closest_t = inf
    closest_sphere = NULL
    for sphere in scene.Spheres {
        t1, t2 = IntersectRaySphere(O, D, sphere)
        if t1 in [t_min, t_max] and t1 < closest_t
            closest_t = t1
            closest_sphere = sphere
        if t2 in [t_min, t_max] and t2 < closest_t
            closest_t = t2
            closest_sphere = sphere
    }
    return closest_sphere, closest_t
}

В результате TraceRay получается гораздо проще:

TraceRay(O, D, t_min, t_max) {
    closest_sphere, closest_t = ClosestIntersection(O, D, t_min, t_max)

    if closest_sphere == NULL
        return BACKGROUND_COLOR

    P = O + closest_t*D  # Compute intersection
    N = P - closest_sphere.center  # Compute sphere normal at intersection
    N = N / length(N)
    return closest_sphere.color*ComputeLighting(P, N, -D, sphere.specular)
}

Теперь нам нужно добавить в ComputeLighting проверку тени:

ComputeLighting(P, N, V, s) {
    i = 0.0
    for light in scene.Lights {
        if light.type == ambient {
            i += light.intensity
        } else {
            if light.type == point {
                L = light.position - P
                t_max = 1
            } else {
                L = light.direction
                t_max = inf
            }

            # Проверка тени
            shadow_sphere, shadow_t = ClosestIntersection(P, L, 0.001, t_max)
            if shadow_sphere != NULL
                continue

            # Диффузность
            n_dot_l = dot(N, L)
            if n_dot_l > 0
                i += light.intensity*n_dot_l/(length(N)*length(L))

            # Зеркальность
            if s != -1 {
                R = 2*N*dot(N, L) - L
                r_dot_v = dot(R, V)
                if r_dot_v > 0
                    i += light.intensity*pow(r_dot_v/(length(R)*length(V)), s)
            }
        }
    }
    return i
}

Вот как будет выглядеть наша заново отрендеренная сцена:


Исходный код и рабочее демо >>

Теперь у нас уже что-то получается.

Отражение

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

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



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

О, постойте, у нас же она есть: она называется TraceRay.

Итак, мы начинаем с основного цикла TraceRay, чтобы увидеть, что «видит» луч, испущенный из камеры. Если TraceRay определяет, что луч видит отражающий объект, то он просто должен вычислить направление отражённого луча и вызвать… сам себя.

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

Не торопитесь, я подожду.

…

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

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

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

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

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

Рендеринг с отражением

Давайте добавим к коду трассировщика лучей отражение.

Как и ранее, в первую очередь мы изменяем сцену:

sphere {
    center = (0, -1, 3)
    radius = 1
    color = (255, 0, 0)  # Красный
    specular = 500  # Блестящий
    reflective = 0.2  # Немного отражающий
}
sphere {
    center = (-2, 1, 3)
    radius = 1
    color = (0, 0, 255)  # Синий
    specular = 500  # Блестящий
    reflective = 0.3  # Немного более отражающий
}
sphere {
    center = (2, 1, 3)
    radius = 1
    color = (0, 255, 0)  # Зелёный
    specular = 10  # Немного блестящий
    reflective = 0.4  # Ещё более отражающий
}
sphere {
    color = (255, 255, 0)  # Жёлтый
    center = (0, -5001, 0)
    radius = 5000
    specular = 1000  # Очень блестящий
    reflective = 0.5  # Наполовину отражающий
}

Мы используем формулу «луча отражения» в паре мест, поэтому может избавиться от неё. Она получает луч и нормаль , возвращая , отражённый относительно :

ReflectRay(R, N) {
    return 2*N*dot(N, R) - R;
}

Единственным изменением в ComputeLighting является замена уравнения отражения на вызов этого нового ReflectRay.

В основной метод внесено небольшое изменение — нам нужно передать TraceRay верхнего уровня предел рекурсии:

        color = TraceRay(O, D, 1, inf, recursion_depth)

Константе recursion_depth можно задать разумное значение, например, 3 или 5.

Единственные важные изменения происходят ближе к концу TraceRay, где мы рекурсивно вычисляем отражения:

TraceRay(O, D, t_min, t_max, depth) {
    closest_sphere, closest_t = ClosestIntersection(O, D, t_min, t_max)

    if closest_sphere == NULL
        return BACKGROUND_COLOR

    # Вычисление локального цвета
    P = O + closest_t*D  # Вычисление точки пересечения
    N = P - closest_sphere.center  # Вычисление нормали к сфере в точке пересечения
    N = N / length(N)
    local_color = closest_sphere.color*ComputeLighting(P, N, -D, sphere.specular)

    # Если мы достигли предела рекурсии или объект не отражающий, то мы закончили
    r = closest_sphere.reflective
    if depth <= 0 or r <= 0:
        return local_color

    # Вычисление отражённого цвета
    R = ReflectRay(-D, N)
    reflected_color = TraceRay(P, R, 0.001, inf, depth - 1)

    return local_color*(1 - r) + reflected_color*r
}

Пусть результаты говорят сами за себя:



Исходный код и рабочее демо >>

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



А вот тот же увеличенный вид той же сцены, на этот раз отрендеренный с :



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

Произвольная камера

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

Давайте начнём с положения. Вы наверно заметили, что используется во всём псевдокоде только один раз: в качестве начальной точки лучей, исходящих из камеры в методе верхнего уровня. Если мы хотим поменять положение камеры. то единственное, что нужно сделать — это использовать другое значение для .

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

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

Меняется только функция верхнего уровня:

for x in [-Cw/2, Cw/2] {
    for y in [-Ch/2, Ch/2] {
        D = camera.rotation * CanvasToViewport(x, y)
        color = TraceRay(camera.position, D, 1, inf)
        canvas.PutPixel(x, y, color)
    }
}

Вот как выглядит наша сцена при наблюдении из другого положения и при другой ориентации:



Исходный код и рабочее демо >>

Куда двигаться дальше

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

Оптимизация

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

Параллелизация

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

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

Кэширование значений

Рассмотрим значения, вычисляемые IntersectRaySphere, на который трассировщик лучей обычно тратит большинство времени:

    k1 = dot(D, D)
    k2 = 2*dot(OC, D)
    k3 = dot(OC, OC) - r*r

Некоторые из этих значений постоянны для всей сцены — как только вы узнаете, как расположены сферы, r*r и dot(OC, OC) больше не меняются. Можно вычислить их один раз во время загрузки сцены и хранить их в самих сферах; вам просто нужно будет пересчитать их, если сферы должны переместиться в следующем кадре. dot(D, D) — это константа для заданного луча, поэтому можно вычислить его в ClosestIntersection и передать в IntersectRaySphere.

Оптимизации теней

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



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

Аналогично, при вычислении пересечения между лучом света и объектами в сцене на самом деле нам не нужно ближайшее пересечение — достаточно знать, что существует по крайней мере одно пересечение. Можно использовать специальную версию ClosestIntersection, которая возвращает результат, как только найдёт первое пересечение (и для этого нам нужно вычислять и возвращать не closest_t, а просто булево значение).

Пространственные структуры

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

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

Подробнее об этом можно узнать, прочитав о иерархии ограничивающих объёмов.

Субдискретизация

Вот простой способ сделать трассировщик лучей в раз быстрее: вычислять в раз пикселей меньше!

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

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

Разумеется, так можно запросто пропустить очень тонкий объект: в отличие от рассмотренных ранее, это «неправильная» оптимизация, потому что результаты её использования не идентичны тому, что бы мы получили без неё; в каком-то смысле, мы «жульничаем» на этой экономии. Хитрость в том, как догадаться сэкономить правильно, обеспечив удовлетворительные результаты.

Другие примитивы

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

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

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

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

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

Как это работает? Для каждого объекта можно вычислить места, где луч входит и выходит из объекта; например, в случае сферы луч входит в и выходит в . Предположим, что нам нужно вычислить пересечение двух сфер; луч находится внутри пересечения, когда находится внутри обеих сфер, и снаружи в противоположном случае. В случае вычитания луч находится внутри, когда он находится внутри первого объекта, но не внутри второго.

В более общем виде, если мы хотим вычислить пересечение между лучом и (где — любой булевый оператор), то сначала нужно по отдельности вычислить пересечение луч- и луч-, что даёт нам «внутренний» интервал каждого объекта и . Затем мы вычисляем , который находится во «внутреннем» интервале . Нам нужно просто найти первое значение , которое находится и во «внутреннем» интервале и в интервале , которые нас интересуют:



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

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

Прозрачность

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

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

Преломление

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

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

Например, приблизительно равен , а приблизительно равен . То есть для луча, входящего в воду под углом получаем

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

Суперсэмплинг

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

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

Решить эту проблему можно трассированием нескольких лучей на пиксель — 4, 9, 16, и так далее, а затем усредняя их, чтобы получить цвет пикселя.

Разумеется, при этом трассировщик лучей становится в 4, 9 или 16 раз медленнее, по той же причине, по которой субдискретизация делает его в раз быстрее. К счастью, существует компромисс. Мы можем предположить, что свойства объекта вдоль его поверхности меняются плавно, то есть испускание 4 лучей на пиксель, которые падают на один объект в немного отличающихся точках, не слишком улучшит вид сцены. Поэтому мы можем начать с одного луча на пиксель и сравнивать соседние лучи: если они падают на другие объекты или их цвет отличается больше, чем на переделённое пороговое значение, то применяем к обоим подразделение пикселей.

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

Ниже представлена полная версия псевдокода, созданного нами в главах о трассировке лучей:

CanvasToViewport(x, y) {
    return (x*Vw/Cw, y*Vh/Ch, d)
}


ReflectRay(R, N) {
    return 2*N*dot(N, R) - R;
}


ComputeLighting(P, N, V, s) {
    i = 0.0
    for light in scene.Lights {
        if light.type == ambient {
            i += light.intensity
        } else {
            if light.type == point {
                L = light.position - P
                t_max = 1
            } else {
                L = light.direction
                t_max = inf
            }

            # Проверка теней
            shadow_sphere, shadow_t = ClosestIntersection(P, L, 0.001, t_max)
            if shadow_sphere != NULL
                continue

            # Диффузность
            n_dot_l = dot(N, L)
            if n_dot_l > 0
                i += light.intensity*n_dot_l/(length(N)*length(L))

            # Блеск
            if s != -1 {
                R = ReflectRay(L, N)
                r_dot_v = dot(R, V)
                if r_dot_v > 0
                    i += light.intensity*pow(r_dot_v/(length(R)*length(V)), s)
            }
        }
    }
    return i
}


ClosestIntersection(O, D, t_min, t_max) {
    closest_t = inf
    closest_sphere = NULL
    for sphere in scene.Spheres {
        t1, t2 = IntersectRaySphere(O, D, sphere)
        if t1 in [t_min, t_max] and t1 < closest_t
            closest_t = t1
            closest_sphere = sphere
        if t2 in [t_min, t_max] and t2 < closest_t
            closest_t = t2
            closest_sphere = sphere
    }
    return closest_sphere, closest_t
}


TraceRay(O, D, t_min, t_max, depth) {
    closest_sphere, closest_t = ClosestIntersection(O, D, t_min, t_max)

    if closest_sphere == NULL
        return BACKGROUND_COLOR

    # Вычисление локального цвета
    P = O + closest_t*D  # Вычисление точки пересечения
    N = P - closest_sphere.center  # Вычисление нормали сферы в точке пересечения
    N = N / length(N)
    local_color = closest_sphere.color*ComputeLighting(P, N, -D, sphere.specular)

    # Если мы достигли предела рекурсии или объект не отражающий, то мы закончили
    r = closest_sphere.reflective
    if depth <= 0 or r <= 0:
        return local_color

    # Вычисление отражённого цвета
    R = ReflectRay(-D, N)
    reflected_color = TraceRay(P, R, 0.001, inf, depth - 1)

    return local_color*(1 - r) + reflected_color*r
}


for x in [-Cw/2, Cw/2] {
    for y in [-Ch/2, Ch/2] {
        D = camera.rotation * CanvasToViewport(x, y)
        color = TraceRay(camera.position, D, 1, inf)
        canvas.PutPixel(x, y, color)
    }
}

А вот сцена, использованная для рендеринга примеров:

viewport_size = 1 x 1
projection_plane_d = 1

sphere {
    center = (0, -1, 3)
    radius = 1
    color = (255, 0, 0)  # Красный
    specular = 500  # Блестящий
    reflective = 0.2  # Немного отражающий
}
sphere {
    center = (-2, 1, 3)
    radius = 1
    color = (0, 0, 255)  # Синий
    specular = 500  # Блестящий
    reflective = 0.3  # Немного более отражающий
}
sphere {
    center = (2, 1, 3)
    radius = 1
    color = (0, 255, 0)  # Зелёный
    specular = 10  # Немного блестящий
    reflective = 0.4  # Ещё более отражающий
}
sphere {
    color = (255, 255, 0)  # Жёлтый
    center = (0, -5001, 0)
    radius = 5000
    specular = 1000  # Очень блестящий
    reflective = 0.5  # Наполовину отражающий
}


light {
    type = ambient
    intensity = 0.2
}
light {
    type = point
    intensity = 0.6
    position = (2, 1, 0)
}
light {
    type = directional
    intensity = 0.2
    direction = (1, 4, 4)
}