Зачем всё это

Основной целью этой работы было попытаться реализовать реалистичную сцену горного ландшафта с воздушным шаром, используя "чистый" C++ и QT только для вывода пикселей. Мне было интересно превратить код в картинку, не имея других инструментов. Я не буду приводить код в самой статье, его можно найти по ссылке на репозиторий в конце статьи.

Растеризация

Или как превратить объекты в пиксели.

В реальном мире свет от объектов проецируется на глаз - перспективное проецирование. Именно его я и решил попробовать сначала.

Координаты экрана (xs, y0) мы знаем, координаты наблюдаемой точки (xp, yp) знаем, координаты "глаза" (xe, y0) знаем. Для того, чтобы знать какой пиксель высветить, нужно найти координату "y?" .
Имеем два подобных прямоугольных треугольника (xe, y0)(xp, yp)(xp, y0) и (xe, y0)(xs, y?)(xs, y0).
В подобных треугольниках соответствующие стороны относятся друг другу как коэффициент подобия:

Здесь (x1, y1)(x2, y2) это абсолютное значение длины вектора заданного точками (x1, y1) и (x2, y2). Можем найти длину (xs, y?)(xs, y0) и отобразить пиксель ys на экране.

Но точка может находиться между экраном и "глазом" и такой метод все равно отобразит ее на экране. Для того, чтобы этого избежать, проводят отсечение. Часто используют отсечение по пирамиде видимости: усеченная пирамида составляется из плоскости экрана (Near clipping plane), задней плоскости (Far clipping plane, это плоскость дальше которой ничего не видно) и граней, соединяющих эти плоскости. Отсечение объектом по пирамиде видимости подразумевает игнорирование объектов, которые находятся полностью вне пирамиды, отображение объектов, находящихся полностью внутри пирамиды, и обрезку объектов, которые находятся в пирамиде частично. Обычно объект это многоугольник (часто треугольник). Треугольник состоит из отрезков. Для того, чтобы обрезать отрезок можно использовать различные алгоритмы отсечения, например Сазерленда-Коэна. Так обрезаются все отрезки треугольника - формируется новый многоугольник. Этот многоугольник закрашивается.

Получается следующее:

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

Трассировка на процессоре

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

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

Цвет пикселя

Освещенность равна отношению светового потока через поверхность к площади этой поверхности: E = Ф / S (в случае если световой поток перпендикулярен поверхности). Но если мы поворачиваем поверхность, то количество света, проходящего через поверхность становится меньше:

Поэтому освещенность будет зависеть от угла между направлением света и нормалью к повехности (за это отвечает скалярное произведение между вектором N (нормаль к поверхности) и вектором L (луч)):

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

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

Тени

Чтобы добавить тени, нужно посчитать координату пересечения выпущенного через пиксель луча с поверхностью и из этой координаты выпустить луч в источник света. Если этот луч столкнется с другой поверхностью - значит первая поверхность находится в тени. Устанавливаем цвет пикселя либо в (0, 0, 0), что будет выглядеть менее реалистично, так как в реальном мире свет отражается от других объектом и все равно немного попадает на поверхности, находящиеся в тени. Можно установить пиксель в значение I = 0.2 * (r, g, b). Здесь коэффициент 0.2 выбран с использованием метода "пальцем в небо", обычно его называют ambient light или коэффициент фонового освещения. Так грань будет немного освещена.

Кратко о математике пересечения

Для описания точки на луче используется параметрическое уравнение:
R(t) = O + t * D, где O - координаты "глаза" наблюдателя, D - координаты пикселя, через который запускаем луч, t - параметр, определяющий расстояние от начала луча.

Для описания точки треугольника используем барицентрические координаты:
P = V0 + u * (V1 - V0) + v * (V2 - V0)

Чтобы точка лежала внутри треугольника необходимо:
u >= 0
v >= 0
(u + v) <= 1

Пусть P точка треугольника и находится на луче:
V0 + u * (V1 - V0) + v * (V2 - V0) = O + t * D

Теперь решаем систему, находим u, v, t и если точка лежит внутри треугольника (выполняются три условия) то рассчитываем цвет пикселя.

Шаги построения первой сцены

То есть для построения сцены нам необходимо:

1. Разбить объект на треугольники.

2. Через каждый пиксель пропустить луч.

3. Проверить есть ли пересечение луча с каждым треугольником, если есть - посчитать координату этого пересечения.

4. Выпустить луч из точки пересечения в источник, если есть пересечение с другим треугольником - выкрутить цвет треугольника в ноль, иначе посчитать по формуле освещенности.

На этом этапе также применяем отсечение невидимых граней: для пикселя запоминаем координату по Z (если ось Z направлена по направлению взгляда). Если луч пересекается с первым треугольником запоминаем координату пересечения Z1, устанавливаем пиксель в вычисленный цвет. Если луч пересекается с вторым треугольником, вычисляем координату пересечения Z2, если Z2 < Z1 (ближе к экрану, ось Z направлена от наблюдателя), то пересчитываем цвет пикселя, иначе оставляем цвет пикселя.

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

Здесь каждая грань куба состоит из двух треугольников.

Трюк со сферой

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

Занимаем процессор

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

Генерация гор

Для генерации гор я решил использовать самое банальное решение - шум Перлина. В этой статье я не хочу на нем особо останавливаться. Генерируем Шум: получаем трехмерные координаты точек поверхности и аппроксимируем полученную поверхность треугольниками.

Получилось следующее:

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

Закраска Фонга

ВАЖНО: именно на этом моменте я понял, что для каждого треугольника нужно задавать внешнюю нормаль (которая направлена "из объекта"), потому что посчитать ее аналитически, имея только координаты треугольника, очень трудно, если вообще возможно. Посчитать нормаль векторным произведением можно, но таким способом мы получим две нормали. Как определить какая из них внешняя?

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

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

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

А вот на "гладких" объектах закраска Фонга выглядит лучше:

Горы после перехода на закраску Фонга стали такими:

Тестуры или графика дешевых игр

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

Звездное небо это просто текстура для заднего фона.

Заключение и появление "AirBallon"

Для полноты сцены я решил добавить красный воздушный шар и разные текстуры.

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

Весь код и другие картинки вы сможете найти в репозитории.