[Перевод] Трёхмерная графика с нуля. Часть 1: трассировка лучей20.11.2017 12:48

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

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

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

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

В статье в виде неформального псевдокода представлен код примеров, также в нём содержатся полностью рабочие реализации, написанные на 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 на этом луче. Заметьте, что при  мы получим , а при  мы получим . При отрицательных числах мы получим точки в противоположном направлении, то есть за камерой. То есть мы можем разделить область параметров на три части:

	За камерой
	Между камерой и плоскостью проекции
Заметьте, что ничего в уравнении пересечения не говорит, что сфера должна быть перед камерой; уравнение совершенно без проблем даёт решения и для пересечений за камерой. Очевидно, что нам этого не нужно; поэтому нам нужно игнорировать все решения при . Чтобы избежать дополнительных математических сложностей, мы ограничим решения (Примечание: в языках, в которых нельзя непосредственно задать бесконечность, достаточно будет очень большого числа.) Теперь мы можем формализовать всё то, что сделали в псевдокоде. В общем случае я буду предполагать, что код имеет доступ к лю © Habrahabr.ru О проекте Архив Реклама Партнёры Правовая информация Контакты Обратная связь