256 строчек голого C++: пишем трассировщик лучей с нуля за несколько часов

Публикую очередную главу из моего курса лекций по компьютерной графике ^[1] (вот тут можно читать ^[2] оригинал на русском, хотя английская версия новее). На сей раз тема разговора — отрисовка сцен при помощи трассировки лучей. Как обычно, я стараюсь избегать сторонних библиотек, так как это заставляет студентов заглянуть под капот.

Подобных проектов в интернете уже море, но практически все они показывают законченные программы, в которых разобраться крайне непросто. Вот, например, очень известная программа рендеринга, влезающая на визитку ^[3]. Очень впечатляющий результат, однако разобраться в этом коде очень непросто. Моей целью является не показать как я могу, а детально рассказать, как подобное воспроизвести. Более того, мне кажется, что конкретно эта лекция полезна даже не столь как учебный материал по комьпютерной графике, но скорее как пособие по программированию. Я последовательно покажу, как прийти к конечному результату, начиная с самого нуля: как разложить сложную задачу на элементарно решаемые этапы.

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

Итак, сегодня я покажу, как отрисовывать подобные картинки:

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

Я не хочу заморачиваться с оконными менеджерами, обработкой мыши/клавиатуры и тому подобным. Результатом работы нашей программы будет простая картинка, сохранённая на диск. Итак, первое, что нам нужно уметь, это сохранить картинку на диск. Вот здесь ^[4] лежит код, который позволяет это сделать. Давайте я приведу его основной файл:

#include <limits>
#include <cmath>
#include <iostream>
#include <fstream>
#include <vector>
#include "geometry.h"

void render() {
    const int width    = 1024;
    const int height   = 768;
    std::vector<Vec3f> framebuffer(width*height);

    for (size_t j = 0; j<height; j++) {
        for (size_t i = 0; i<width; i++) {
            framebuffer[i+j*width] = Vec3f(j/float(height),i/float(width), 0);
        }
    }

    std::ofstream ofs; // save the framebuffer to file
    ofs.open("./out.ppm");
    ofs << "P6n" << width << " " << height << "n255n";
    for (size_t i = 0; i < height*width; ++i) {
        for (size_t j = 0; j<3; j++) {
            ofs << (char)(255 * std::max(0.f, std::min(1.f, framebuffer[i][j])));
        }
    }
    ofs.close();
}

int main() {
    render();
    return 0;
}

В функции main вызывается только функция render(), больше ничего. Что же внутри функции render()? Перво-наперво я определяю картинку как одномерный массив framebuffer значений типа Vec3f, это простые трёхмерные векторы, которые дают нам цвет (r,g,b) для каждого пикселя.

Класс векторов живёт в файле geometry.h, описывать я его здесь не буду: во-первых, там всё тривиально, простое манипулирование двух и трёхмерными векторами (сложение, вычитание, присваивание, умножение на скаляр, скалярное произвдение), а во-вторых, gbg ^[5] его уже подробно описал ^[6] в рамках курса лекций по компьютерной графике.

Картинку я сохраняю в формате ppm ^[7]; это самый простой способ сохранения изображений, хотя и не всегда самый удобный для дальнейшего просматривания. Если хотите сохранять в других форматах, то рекомендую всё же подключить стороннюю библиотеку, например, stb ^[8]. Это прекрасная библиотека: достаточно в проект включить один заголовочный файл stb_image_write.h, и это позволит сохранять хоть в png, хоть в jpg.

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

Этап второй, самый сложный: непосредственно трассировка лучей

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

Для удобства в моём репозитории по одному коммиту на каждый этап; Github позволяет очень удобно просматривать внесённые изменения. Вот, например ^[9], что изменилось во втором коммите по сравнению с первым.

Для начала: что нам нужно, чтобы в памяти компьютера представить сферу? Нам достаточно четырёх чисел: трёхмерный вектор с центром сферы и скаляр, описывающий радиус:

struct Sphere {
    Vec3f center;
    float radius;

    Sphere(const Vec3f &c, const float &r) : center(c), radius(r) {}

    bool ray_intersect(const Vec3f &orig, const Vec3f &dir, float &t0) const {
        Vec3f L = center - orig;
        float tca = L*dir;
        float d2 = L*L - tca*tca;
        if (d2 > radius*radius) return false;
        float thc = sqrtf(radius*radius - d2);
        t0       = tca - thc;
        float t1 = tca + thc;
        if (t0 < 0) t0 = t1;
        if (t0 < 0) return false;
        return true;
    }
};

Единственная нетривиальная вещь в этом коде — это функция, которая позволяет проверить, пересекается ли заданный луч (исходящий из orig в направлении dir) с нашей сферой. Детальное описание алгоритма проверки пересечения луча и сферы можно прочитать тут ^[10], очень рекомендую это сделать и проверить мой код.

Как работает трассировка лучей? Очень просто. На первом этапе мы просто замели картинку градиентом:

    for (size_t j = 0; j<height; j++) {
        for (size_t i = 0; i<width; i++) {
            framebuffer[i+j*width] = Vec3f(j/float(height),i/float(width), 0);
        }
    }

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

Если пересечения со сферой нет, то мы поставим цвет1, иначе цвет2:

Vec3f cast_ray(const Vec3f &orig, const Vec3f &dir, const Sphere &sphere) {
    float sphere_dist = std::numeric_limits<float>::max();
    if (!sphere.ray_intersect(orig, dir, sphere_dist)) {
        return Vec3f(0.2, 0.7, 0.8); // background color
    }
    return Vec3f(0.4, 0.4, 0.3);
}

void render(const Sphere &sphere) {
	[...]
    for (size_t j = 0; j<height; j++) {
        for (size_t i = 0; i<width; i++) {
            float x =  (2*(i + 0.5)/(float)width  - 1)*tan(fov/2.)*width/(float)height;
            float y = -(2*(j + 0.5)/(float)height - 1)*tan(fov/2.);
            Vec3f dir = Vec3f(x, y, -1).normalize();
            framebuffer[i+j*width] = cast_ray(Vec3f(0,0,0), dir, sphere);
        }
    }
	[...]
}

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

• ширина картинки, width
• высота картинки, height
• угол обзора, fov
• расположение камеры, Vec3f(0,0,0)
• направление взора, вдоль оси z, в направлении минус бесконечности

Этап третий: добавляем ещё сфер

Всё самое сложное уже позади, теперь наш путь безоблачен. Если мы умеем нарисовать одну сферу. то явно добавить ещё несколько труда не составит. Вот тут ^[11] смотреть изменения в коде, а вот так выглядит результат:

Этап четвёртый: освещение

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

struct Light {
    Light(const Vec3f &p, const float &i) : position(p), intensity(i) {}
    Vec3f position;
    float intensity;
};

Считать настоящее освещение — это очень и очень непростая задача, поэтому, как и все, мы будем обманывать глаз, рисуя совершенно нефизичные, но максимально возможно правдоподобные результаты. Первое замечание: почему зимой холодно, а летом жарко? Потому что нагрев поверхности земли зависит от угла падения солнечных лучей. Чем выше солнце над горизонтом, тем ярче освещается поверхность. И наоборот, чем ниже над горизонтом, тем слабее. Ну а после того, как солнце сядет за горизонт, до нас и вовсе фотоны не долетают. Применительно к нашим сферам: вот наш луч, испущенный из камеры (никакого отношения к фотонам, обратите внимание!) пересёкся со сферой. Как нам понять, как освещена точка пересечения? Можно просто посмотреть на угол между нормальным вектором в этой точке и вектором, описывающим направление света. Чем меньше угол, тем лучше освещена поверхность. Чтобы считать было ещё удобнее, можно просто взять скалярное произвдение между вектором нормали и вектором освещения. Напоминаю, что скалярное произвдение между двумя векторами a и b равно произведению норм векторов на косинус угла между векторами: a*b = |a| |b| cos(alpha(a,b)). Если взять векторы единичной длины, то простейшее скалярное произведение даст нам интенсивность освещения поверхности.

Таким образом, в функции cast_ray вместо постоянного цвета будем возвращать цвет с учётом источников освещения:

Vec3f cast_ray(const Vec3f &orig, const Vec3f &dir, const Sphere &sphere) {
    [...]
    float diffuse_light_intensity = 0;
    for (size_t i=0; i<lights.size(); i++) {
        Vec3f light_dir      = (lights[i].position - point).normalize();
        diffuse_light_intensity  += lights[i].intensity * std::max(0.f, light_dir*N);
    }
    return material.diffuse_color * diffuse_light_intensity;
}

Измениия смотреть тут ^[12], а вот результат работы программы:

Этап пятый: блестящие поверхности

Трюк со скалярным произведением между нормальным вектором и вектором света неплохо приближает освещение матовых поверхностей, в литературе называется диффузным освещением. Что же делать, если мы хотим гладкие да блестящие? Я хочу получить вот такую картинку:

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

Эта гимнастика с освещением матовых и блестящих поверхностей известна как модель Фонга ^[14]. В вики есть довольно детальное описание этой модели освещения, она хорошо читается при параллельном сравнении с моим кодом. Вот ключевая для понимания картинка:

Этап шестой: тени

А почему это у нас есть свет, но нет теней? Непорядок! Хочу вот такую картинку:

Всего шесть строчек кода ^[15] позволяют этого добиться: при отрисовке каждой точки мы просто убеждаемся, не пересекает ли луч точка-источник света объекты нашей сцены, и если пересекает, то пропускам текущий источник света. Тут есть только маленькая тонкость: я самую малость сдвигаю точку в направлении нормали:

Vec3f shadow_orig = light_dir*N < 0 ? point - N*1e-3 : point + N*1e-3;

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

Этап седьмой: отражения

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

    Vec3f reflect_dir = reflect(dir, N).normalize();
    Vec3f reflect_orig = reflect_dir*N < 0 ? point - N*1e-3 : point + N*1e-3; // offset the original point to avoid occlusion by the object itself
    Vec3f reflect_color = cast_ray(reflect_orig, reflect_dir, spheres, lights, depth + 1);

Убедитесь в этом сами: ^[16] при пересечении с объектом мы просто считаем отражённый луч (функция из подсчёта отбесков пригодилась!) и рекурсивно вызываем функцию cast_ray в направлении отражённого луча. Обязательно поиграйте с глубиной рекурсии ^[17], я её поставил равной четырём, начните с нуля, что будет изменяться на картинке? Вот мой результат с работающим отражением и глубиной четыре:

Этап восьмой: преломление

Научившись считать отражения, преломления считаются ровно так же ^[18]. Одна функция позволяющая посчитать направление преломившегося луча (по закону Снеллиуса ^[19]), и три строчки кода в нашей рекурсивной функции cast_ray. Вот результат, в котором ближайший шарик стал «стеклянным», он и преломляет, и немного отражает:

Этап девятый: добавляем ещё объекты

А чего это мы всё без молока, да без молока. До этого момента мы рендерили только сферы, поскольку это один из простейших нетривиальных математических объектов. А давайте добавим кусок плоскости. Классикой жанра является шахматная доска. Для этого нам вполне достаточно десятка строчек ^[20] в функции, которая считает пересечение луча со сценой.

Ну и вот результат:

Как я и обещал, ровно 256 строчек кода, посчитайте сами ^[21]!

Этап десятый: домашнее задание

Мы прошли довольно долгий путь: научились добавлять объекты в сцену, считать довольно сложное освещение. Давайте я оставлю два задания в качестве домашки. Абсолютно вся подготовительная работа уже сделана в ветке homework_assignment ^[22]. Каждое задание потребует максимум десять строчек кода.

Задание первое: Environment map

На данный момент, если луч не пересекает сцену, то мы ему просто ставим постоянный цвет. А почему, собственно, постоянный? Давайте возьмём сферическую фотографию (файл envmap.jpg ^[23]) и используем её в качестве фона! Для облегчения жизни я слинковал наш проект с библиотекой stb для удобства работы со жпегами. Должен получиться вот такой рендер:

Задание второе: кря!

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

Заключение

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

Двести пятьдесят строчек рейтрейсинга реально написать за несколько часов. Пятьсот строчек ^[24] софтверного растеризатора можно осилить за несколько дней. В следующий раз разберём по полочкам рейкастинг ^[25], и заодно я покажу простейшие игры, которые пишут мои студенты-первокурсники в рамках обучения программированию на С++. Stay tuned!

Автор: haqreu

Источник ^[26]