Raytracing render на C

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

    В данной статье хочу поделиться собственным подходом и полученными результатами.



    Несколько слов про рейтрейсинг


    Представим что у нас есть камера (для упрощения будем считать, что наша камера это материальная точка). Также у нас есть плоскость проектирования, которая является набором пикселей. Теперь, от камеры, к каждому пикселю плоскости проектирования будем проводить векторы (первичные лучи) и для каждого луча находить ближайший объект сцены, который он пересекает. Цветом, что соответствует точке пересечения, можно закрасить соответствующий пиксель на плоскости проектирования. Повторив эту процедуру для всех точек плоскости проектирования — мы получим изображение трехмерной сцены. Если ограничиться только этими операциями, то полученный алгоритм будет называться Ray casting.

    Рекурсивный Ray casting == Ray tracing

    • Из точки пересечения первичного луча с объектом сцены можно выпустить вторичный луч — направленный к источнику света. Если он пересекает какой-либо объект сцены, значит данная точка объекта находится в тени. Этот прием позволяет получать геометрически правильные тени.

    • Если объект обладает зеркальной поверхностью, то по законам геометрической оптики можно рассчитать отраженный луч — и запустить для него процедуру рейтрейсинга (рекурсивно). Затем смешать полученный от зеркального отражения цвет с собственным цветом поверхности. Этот прием позволяет моделировать зеркальные поверхности (подобным образом можно моделировать прозрачные поверхности).

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


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

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

    • Алгоритм не содержит ограничений на геометрию объектов (можно использовать богатый набор примитивов: плоскости, сферы, цилиндры и т.п.)


    Архитектура рендера


    Все объекты хранятся в куче. Рендер оперирует массивом указателей на 3D объекты (на самом деле все объекты еще упакованы в kd-дерево, но пока будем считать, что дерево отсутствует). На данный момент есть 2 типа примитивов: трианглы и сферы.

    Как научить рендер оперировать различными примитивами?

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

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

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

    Рендер оперирует обобщенными структурами (Object3d), содержащими указатель на область данных, в которой хранятся фактические параметры 3D объекта, а также указатели на функции, которые умеют правильным образом обрабатывать эту область данных.

    Описание структуры Object3d из исходников рендера
    typedef 
    struct {
    	// указатель на область данных, содержащую параметры конкретного примитива
    	// в случае полигона: координаты вершин, цвет (или битмапка с текстурой), свойства материала
    	// в случае сферы: координаты центра, радиус, и т.п.
    	void * data;
        
    	// указатель на функцию, которая умеет обрабатывать примитив,
    	// на который ссылается указатель data
    	Boolean (*intersect)(const void * data,
                             const Point3d ray_start_point,
                             const Vector3d ray,
                             // сюда будет сохранятся точка пересечения луча и примитива
                             Point3d * const intersection_point);
    
    	// получение цвета в точке пересечения
    	// здесь можно возвращать просто цвет объекта
    	// или обеспечить процедурную генерацию текстуры
    	// или использовать загруженную из файла текстуру :)
    	Color (*get_color)(const void * data,
                           const Point3d intersection_point);
    
        // получение вектора нормали в точке пересечения (используется для рассчёта освещённости)
        // в случае сферы и полигона - вектор нормали можно рассчитать аналитически
        // как вариант, вместо аналитечских рассчётов - объект может содержать карту нормалей
        Vector3d (*get_normal_vector)(const void * data,
                                      const Point3d intersection_point);
    
    	// вызывается рендером перед удалением Object3d
    	// тут можно освобождать ресурсы, связанные с объектом
    	// например, удалять текстуры
    	void (*release_data)(void * data);
    }
    Object3d;
    





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

    В качестве примера: код сферы из исходников рендера
    sphere.c
    // ... инклуды
    
    typedef
    struct {
        Point3d center;
        Float radius;
        Color color;
    }
    Sphere;
    
    // ... декларации функций
    
    // "конструктор" сферы
    Object3d *
    new_sphere(const Point3d center,
               const Float radius,
               const Color color) {
        
        Sphere * sphere = malloc(sizeof(Sphere));
        sphere->center = center;
        sphere->radius = radius;
        sphere->color = color;
    
        // упаковываем сферу в обобщённую структуру 3D объекта
        Object3d * obj = malloc(sizeof(Object3d));
        obj->data = sphere;
    
        // добавляем функции, которые умеют работать со структурой Sphere
    	obj->get_color = get_sphere_color;
        obj->get_normal_vector = get_sphere_normal_vector;
    	obj->intersect = intersect_sphere;
        obj->release_data = release_sphere_data;
        
        return obj;
    }
    
    // цвет сферы всюду одинаковый
    // но здесь можно реализовать процедурную генерацию текстуры
    static Color
    get_sphere_color(const void * data,
                     const Point3d intersection_point) {
    	const Sphere * sphere = data;
    	return sphere->color;
    }
    
    // вычисляем аналитически вектор нормали в точке на поверхности сферы
    // сюда можно впилить Bump Mapping
    static Vector3d
    get_sphere_normal_vector(const void * data,
                             const Point3d intersection_point) {
        const Sphere * sphere = data;    
        // vector3dp - служебная функция, которая создаёт вектор по двум точкам
        Vector3d n = vector3dp(sphere->center, intersection_point);
        normalize_vector(&n);
        return n;
    }
    
    // пересечение луча и сферы
    static Boolean
    intersect_sphere(const void * data,
                     const Point3d ray_start_point,
                     const Vector3d ray,
                     Point3d * const intersection_point) {
        const Sphere * sphere = data;    
        // чтобы найти точку пересечения луча и сферы - нужно решить квадратное уравнение
        // полную реализацию метода можно найти в исходниках на GitHub
    }
    
    // "деструктор" сферы
    void
    release_sphere_data(void * data) {
    	Sphere * sphere = data;
    	// если бы сфера содержала текстуры - их нужно было бы здесь освободить
    	free(sphere);
    }
    


    Пример того, как можно оперировать различными примитивами, независимо от их реализации
    void
    example(void) {
    	Object3d * objects[2];
    
    	// красная сфера, с центром в точке (10, 20, 30) и радиусом 100
    	objects[0] = new_sphere(point3d(10, 20, 30), 100, rgb(255, 0, 0));
    
    	// зелёный треугольник с вершинами (0, 0, 0), (100, 0, 0) и (0, 100, 0)
    	objects[1] = new_triangle(point3d(0, 0, 0), point3d(100, 0, 0), point3d(0, 100, 0), rgb(0, 255, 0));
    
    	Point3d camera = point3d(0, 0, -100);
    
    	Vector3d ray = vector3df(0, -1, 0);
    
    	int i;
    	for(i = 0; i < 2; i++) {
    		Object3d * obj = objects[i];
    
    		Point3d intersection_point;
    
    		if(obj->intersect(obj->data, camera, ray, &intersection_point)) {
    			// вот так можно получить цвет в точке пересечения луча и примитива
    			Color c = obj->get_color(obj->data, intersection_point);
    			// делаем что-нибудь ещё :-)
    			// например, можно искать ближайшую точку пересечения
    			// и нам совсем не важно, что именно лежит в массиве objects!
    		}
    	}
    }
    


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

    Скорость рендеринга


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



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

    POSIX Threads

    Первое впечатление: семантика Java Threads очень близка к pthreads. Поэтому, особых проблем с пониманием модели POSIX потоков не было. Было приянто решение запилить свой Thread Pool :-)

    Thread Pool содержал очередь для тасков. Каждый таск являлся структурой, содержащей ссылку на функцию, которую нужно выполнить, а также ссылку на список аргументов. Доступ к очереди тасков регулировался посредством мютекса и condition-переменной. Для удобства, весь рендеринг инкапсулирован в отдельной функции, одним из аргументов которой — является количество потоков:

    Сигнатура функции, инкапсулирующей рендеринг
    void
    render_scene(const Scene * const scene,
                 const Camera * const camera,
                 Canvas * canvas,
                 const int num_threads);
    
    // структура Scene содержит 3D объекты, источники света, цвет фона и параметры тумана
    // структура Camera содержит координаты, углы наклона и фокус камеры
    // структура Canvas эмулирует 2х мерный холст - именно в него и ренедрится изображение
    


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

    Но, к сожалению, на 2х ядерном ноуте рендер периодически зависал или падал с ошибкой Abort trap 6 (причём на 4х ядерном это ни разу не воспроизвелось). Я пытался пофиксить это печальный баг, но вскоре нашёл более привлекательное решение.

    OpenMP

    OpenMP берёт на себя всю заботу по созданию и распределению тасков, а также организовывает барьер для ожидания завершения рендеринга. Достаточно дописать всего несколько директив чтобы распараллелить однопоточный код, а баги с зависанием исчезли :-)

    Функция ренедринга из исходников
    void
    render_scene(const Scene * const scene,
                 const Camera * const camera,
                 Canvas * canvas,
                 const int num_threads) {
        
        const int width = canvas->width;
        const int height = canvas->height;
        const Float focus = camera->focus;
        
        // устанавливаем количество потоков
        omp_set_num_threads(num_threads);
        
        int x;
        int y;
        // всего две строчки, для того чтобы распараллелить рендеринг :-)
        #pragma omp parallel private(x, y)
        #pragma omp for collapse(2) schedule(dynamic, CHUNK)
        for(x = 0; x < width; x++) {
            for(y = 0; y < height; y++) {
                const Vector3d ray = vector3df(x, y, focus);
                const Color col = trace(scene, camera, ray);
                set_pixel(i, j, col, canvas);
            }
        }
    }
    



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

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

    Kd-Tree


    Давайте разобьём сцену с объектами на две части: «левая» и «правая» (обозначим их как L и R, соответственно):

    Поскольку мы делим сцену на части параллельно осям координат — то можно относительно быстро просчитать какую часть сцены пересекает луч. Возможны следующие варианты:

    • Луч пересекает только часть сцены L
      Можно не просматривать объекты, содержащиеся в части R
      (на картинке — луч 1)

    • Луч пересекает только часть сцены R
      Можно не просматривать объекты, содержащиеся в части L
      (на картинке — луч 3)

    • Луч пересекает сначала часть сцены L, а потом часть сцены R
      Сначала просматриваем объекты, принадлежащие части сцены L — если пересечение было найдено, тогда объекты принадлежащие части сцены R можно не просматривать. Если луч не пересекает ни один объект из части L — придётся просмотреть объекты из части R
      (на картинке — луч 2)

    • Луч пересекает сначала часть сцены R, а потом часть сцены L
      Такая же логика поиска пересечений, как и в предыдущем варианте (только сначала рассматриваем часть сцены R)

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

    Давайте, для примера, рассмотрим процесс трассировки луча 2:

    1. Луч пересекает сначала левый сегмент сцены (L), потом правый — R
    2. Из части L — луч пересекает только сегмент LL
    3. Сегмент LL не содержит никаких объектов
    4. Переходим к правой половине сцены — R
    5. В правой половине сцены луч пересекает сначала сегмент RL, а потом RR
    6. В части сцены RL было найдено пересечение луча с объектом
    7. Трассировка завершена

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

    Surface Area Heuristic

    Вероятность попадания луча в какой-нибудь сегмент сцены — пропорциональна площади этого сегмента. Чем больше примитивов содержится в участке сцены — тем больше пересечений нужно будет просчитывать при попадании луча в этот сегмент. Таким образом, можно сформулировать критерий разбиения: нужно минимизировать произведение количества примитивов и площади сегмента, в котором они содержатся. Данный критерий называется Surface Area Heuristic (SAH):



    Давайте, на простом примере, рассмотрим эвристику в действии:



    Таким образом, использование SAH позволяет эффективно разделять пустое пространство и 3D объекты — что очень положительно сказывается на производительности рендера.

    Наблюдения

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

    Полученные результаты варьируются для различных сцен (т.к. построение kd-дерева зависит от взаимного расположения примитивов). На графиках изображена зависимость среднего количества пересечений на 1 пиксель изображения от количества примитивов:

    Можно заметить что эта величина значительно меньше количества примитивов, содержащихся в сцене (если бы не было kd-дерева — то получилась бы линейная зависимость, т.к. для каждого луча нужно было бы искать пересечение со всеми N примитивами). Фактически, используя kd-дерево мы понизили сложность алгоритма рейтрейсинга от O(N) до O(log(N)).

    Ради справедливости, стоит заметить что одним из недостатков данного решения является ресурсоёмкость построения kd-дерева. Но для статических сцен — это не критично: загрузили сцену, подождали пока построится дерево — и можно отправляться путешествовать с камерой по сцене :-)

    Сцена, содержащая 16386 треугольников:


    Загрузка моделей

    Научившись рендерить большое количество примитивов — появилось желание загружать 3D модели. Был выбран довольно простой и распостранённый формат — OBJ: модель хранится в текстовом файле, который содержит список вершин и список полигонов (каждый полигон задаётся точками из списка вершин).

    Пример очень простой модели: tetrahedron.obj
    # tetrahedron

    # vertexes:
    v 1.00 1.00 1.00
    v 2.00 1.00 1.00
    v 1.00 2.00 1.00
    v 1.00 1.00 2.00

    # triangles:
    f 1 3 2
    f 1 4 3
    f 1 2 4
    f 2 3 4

    В процессе написания парсера OBJ формата, было замечено, что у многих моделей содержится ещё список нормалей к каждой вершине полигона. Векторы нормалей вершин можно интерполировать для получения вектора нормали в любой точке полигона — этот приём позволяет симулировать гладкие поверхности (см. затенение по Фонгу). Данную фичу было довольно легко реализовать в рамках текущей архитектуры рендера (нужно было просто добавить векторы нормалей в структуру Triangle3d, и написать функцию, которая интерполирует их для любой точки полигона).

    Структура Triangle3d из исходников рендера
    typedef
    struct { 
        // координаты вершин
    	Point3d p1;
    	Point3d p2;
    	Point3d p3;
    
        // вектор нормали, рассчитанный по трём вершинам
        // если используется затенение по Фонгу - тогда нам этот атрибут не важен
        Vector3d norm;
        
        Color color;
    
        Material material;
        
        // если текстура отсутствует - закрашиваем триангл цветом, который указан в color
        Canvas * texture;
    
        // текстурные координаты
        // используем только тогда, когда есть текстура
        Point2d t1;
        Point2d t2;
        Point2d t3;
        
        // векторы нормали в вершинах
        // используем только в случае затенения по Фонгу
        Vector3d n1;
        Vector3d n2;
        Vector3d n3;
    
        // есть ещё несколько служебных атрибутов
        // которые используются для сокращения вычислений
    }
    Triangle3d;
    


    Пример отрендериной сцены, содержащей порядка 19000 полигонов:


    Пример отрендериной сцены, содержащей примерно 22000 полигонов:


    Ради интереса решил добавить скайбокс и загрузить модели автомобилей:
    Сцена содержит порядка 100000 полигонов (kd-дерево строилось несколько минут)



    Заключение


    Я рад что выбрал данную задачу во время изучения С — т.к., она позволила узнать различные аспекты экосистемы языка, и получить красивые результаты.

    Исходники рендера на гитхабе: github.com/lagodiuk/raytracing-render (в описании проекта — рассказано как запустить демку).

    В процессе изучения С мне очень помогли 2 книги:

    1. Брайан Керниган, Деннис Ритчи — Язык программирования Си — вначале испытывал некоторые затруднения при чтении данной книги. Но после прочтения Head First C — снова вернулся к этой книге. В данной книге есть много примеров и задачек, которые помогли в изучении

    2. David Griffiths, Dawn Griffiths — Head First C — эта книга очень понравилась тем, что в ней даётся общее видение экосистемы языка С (как устроена память, как это работает на уровне ОС, в общих чертах описан make, valgrind, POSIX потоки, юнит тестирование, и есть даже несколько страниц про Arduino)

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

    Ещё, хочу порекомендовать очень полезный ресурс: ray-tracing.ru — здесь, в доступной форме, описаны различные алгоритмы, применяемые для фотореалистичного рендеринга (в частности — kd-деревья и SAH).

    P.S.
    Несколько видеороликов созданных в процессе разработки рендера:

    Пирамида Серпинского в тумане


    Куб, человек, фонарь, чайник и пирамида Серпинского :-)



    UPD:
    Получилось ускорить построение дерева. Детали в ветке комментариев: habrahabr.ru/post/187720/#comment_6580722

    UPD 2:
    После обсуждения в данной ветке комментариев: habrahabr.ru/post/187720/#comment_6579384 — был реализован антиалиасинг. Спасибо всем за идеи. Теперь отрендереные изображения выглядят красивее :)
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 54

      +1
      Отличная статья.
      Вы не пытались вынести расчеты на GPU? GPU должно быть намного быстрее чем потоки CPU. Если пытались какие проблемы возникли и почему отказались от такого решения?
        0
        Спасибо.
        Планирую перенести на CUDA (пока что нахожусь на этапе изучения данной технологии).
        Насколько я понял, придётся отказаться от указателей на функции (а ведь на этом сейчас базируется архитектура рендера).
          0
          Присоединяюсь. Это очень круто, но месье всё же знает толк) Можно даже не на куду, а просто шейдерами, например. Правда, это уже совсем другая история…
            +1
            Мьсе правильно мыслит, многие коммерческие рендеры используют GPU
              0
              Видимо, мы про разных месье) Я про автора топика, видимо, неясно выразился… По поводу GPU-то я согласен, естественно…
              +1
              Шейдеры немного по-другому изначально проектировались и использовать их при трассировке лучей, особенно основываясь на физике, не принято. Гораздо полезней в этом плане именно общие вычисления на GPU.
            +3
            Сглаживания границ не хватает на получившихся картинках.
              +3
              антиалиасинг вы имели ввиду. А как же глобальное освещение с просчетом до 3-его отскока фотона, угловые засветы по закону Френеля, подповерхностное свечение, bump меппинг?)
                +1
                Bump mapping можно добавить в текущую архитектуру без особых проблем — по сути это просто отдельная текстура, которая используется для отклонения вектора нормали (а текстуры уже реализованы).

                В плане глобального освещения — мне нравится photon mapping. Для реализации данной технологии можно переиспользовать уже написанное kd-дерево (используется для быстрого поиска фотонов). Хотя, в последнее время всё больше обращаю внимание на path tracing.

                Много чего хочется реализовать, но т.к. это pet project — иногда просто не хватает времени…
                  +1
                  А методом рендера maxwell render или fry render не интересовались? Они конечно дольше но…
                  свои преимущества имеют несомненно в потрясающей реалистичности
                  www.youtube.com/watch?v=gXbKFVD-rvo
                    0
                    Честно говоря, особо не интересовался.
                    Видео красивое, подозреваю что там используется какой-нибудь алгоритм глобального освещения.
                    Я бы с удовольствием занялся реализацией данной фичи :-) но, чувствую что в одиночку это будет довольно долго…
                      0
                      А уж сколько оно рендерилось и представить страшно)
                      А вот кстати… и статья на эту тему habrahabr.ru/post/142003/
                        +1
                        Кстати, у меня была идея написать механизм, который позволял бы распределять на разные компьютеры рендеринг разных кадров (или частей изображения). Хотел написать для этого прослойку на Эрланге. Но, пока что это так и осталось в планах)
                  0
                  Полагаю, имелось ввиду как раз сглаживание границ (зубчатых граней), которое выполняется путём усреднения группы лучей с небольшими отклонениями (например в рамках 2х2 точки с распределением Гаусса). Наверное, эффект антиалиасинга в этом случаетоже может появиться.
                    0
                    Я пробовал увеличить количество лучей (несколько лучей на пиксель) — но это приводило к замедлению рендеринга.
                    Наверное, целесообразно увеличивать количество лучей только в тех участках изображения, где наблюдаются границы объектов.
                    Но в данном случае нужно каким-нибудь эффективным образом детектить границы объектов.
                    В общем, так это и осталось в мыслях )
                      +1
                      Надо не просто увеличивать, но немного смещать их, как я описал выше. Уже при использовании четырех лучей вместо одного картинка улучшается, так что увеличение времени расчета оправдано.

                      Использовать это нужно на всей картинке, это позволит убрать проблемы в случае наличия текстур, отражений и т.д.
                        0
                        Да, согласен. Не подумал об отражениях.
                        Для текстур, кстати, неплохие результаты даёт билинейная фильтрация.
                        +2
                        На сколько я понимаю, многие рендереры просто измеряют контрастность пикселя на фоне остальных, и решают, стоит его разделять на под-пиксели, или нет. Если пиксель сильно отличается от соседей, то с большой долей вероятности тут граница объекта, текстуры, тень, какое-то отражение, или что-то еще, что стоит уточнить.
                          +1
                          Хм, а это мысль!
                          Попробую реализовать: после первого прохода цикла рендеринга — запускать второй, который будет искать границы, и запускать уточняющие лучи.
                            +1
                            Еще проще — каждый пиксел имеет информацию о отображаемом им объекте — если соседние пикселы от разных предметов — можно гладить.
                              +2
                              Тоже сначала подумал об этом. Но в качестве контраргумента придумалось вот такое изображение:



                              В кадре только зеркальная сфера, но в ней отражается вся сцена.
                                +1
                                )) и все-таки даже в вашем примере пикселы несут информацию об отображении отраженных объектов, чуть хитрее но все так же просто. Отражения и тени имеют такую же сквозную нумерацию, как и предметы.
                                  +1
                                  А если надо будет сгладить границу черного и белого пятен на текстуре? Или резкую тень? И зачем сглаживать, когда объекты имеют одинаковый цвет?
                              0
                              А FXAA не быстрее?
                              Хотя это не realtime, как я понимаю.
                              0
                              А еще лучше — завести буфер глубины, и использовать его подобным образом.
                                +1
                                Можно.
                                Еще можно завести буфер нормалей, чтоб отслеживать острые ребра, как у кубика например.
                                Но использование контраста проще, универсальнее и покрывает гораздо больше ситуаций, таких как резкие границы на текстурах, края теней, тонкие блики, отражения и преломления и т.д.
                    +2
                    Спасибо большое, за наводку на «Head first C».
                      0
                      1. Как определяли терминальный критерий для SAH? Оптимальное разбиение — это понятно, но нужно же определять когда в разделении нет необходимости.
                      2. Как решали проблему «дробления» примитива? При рекурсивном делении мы наталкиваемся на момент, когда разделяющая плоскость может разбить притимив.
                      3. И почему именно kd? :)
                        0
                        1. Относительно того, когда прекращать построение дерева:

                        Допустим, мы пытаемся разбить сцену на две части.
                        Начальная площадь поверхности сцены = S_0 и содержит она N_0 полигонов
                        Допустим — площадь левой части S_L, и содержит она N_L полигонов
                        Площадь правой части S_R, и содержит она N_R полигонов

                        Тогда делаем следующее:

                        1) нормируем площади:
                        S_0_norm = S_0 / S_0 = 1
                        S_L_norm = S_L / S_0
                        S_R_norm = S_R / S_0

                        2) рассчитываем SAH
                        SAH_0 = S_0_norm * N_0
                        SAH_L = S_L_norm * N_L
                        SAH_R = S_R_norm * N_R

                        3) введём «штраф» за разбиение (просто константа, которую я подобрал эмпирически) — SPLIT_PENALTY

                        4) рассчитаем целесообразность разбиения:
                        delta_SAH = (SAH_L + SAH_R + SPLIT_PENALTY) — SAH_0

                        если (delta_SAH < 0) — значит разбиение проводит целесообразно

                        5) ещё, «на всякий случай», я контролирую максимальную глубину дерева (у меня есть константа MAX_TREE_DEPTH)

                        2. «Дробление» примитива
                        Если примитив попадает и в «левую» и в «правую» половину — значит считаем его и там и там увеличиваем значение N_L и N_R)

                        3. Я читал про различные структуры данных для ускорения рендеринга, но kd-дерево для меня показалось наиболее понятным и гибким (хотя, возможно я ошибаюсь)
                          0
                          github.com/lagodiuk/raytracing-render/blob/master/render/src/kdtree.c
                          Здесь, начиная со строки 267, функция для поиска наилучшего разбиения. Там реализация того что я описал (немножко оптимизированная).
                            0
                            Видимо, по константе, я проглядел в коде :)
                            Не знаю, как Вы обрабатываете пересечения, но могу посоветовать для треугольников использовать барицентрический тест, а для пересечения вида луч-плоскость Robust Ray–Box Intersection Algorithm. Должно помочь в ускорении :)

                            И есть над чем поработать, не пробовали использовать VTune для анализа производительности? Несколько минут для 100к элементов — это медлено. Хотя, это уже придирки.
                            Интересная статья, спасибо.

                            Если Вы еще будете работать по этой теме, поищите по таким людям как Havran, Wald. можно найти интересную информацию по GPU рендерингу :)

                            И вместо MAX_SPLITS_OF_VOXEL, можно использовать границы примитивов в текущем voxel.
                              0
                              Спасибо за наводки :)

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

                              1) Допустим, что мы рассекаем сцену плоскостью XY
                              2) Значит, нужно найти соответствующую координату разбиения по оси Z
                              3) У нас есть крайние точки сцены: Zmin и Zmax
                              4) Zdist = Zmax — Zmin
                              5) dZ = Zdist / MAX_SPLITS_OF_VOXEL
                              6)
                              for(z = Zmin; z < Zmax; z += dZ) {
                                       Внутри цикла - разбиваем сцену на 2 части
                                       считаем количество полигонов попавших в разные части сцены
                                       считаем площадь каждой части
                                       считаем SAH
                                   }
                              

                              Шаг 6 можно оптимизировать — для каждой новой итерации не нужно пересчитывать заново какие полигоны куда попали. Но, к сожалению, руки ещё до этого не дошли
                                0
                                Только что получилось ускорить построение дерева :-)
                                Подробности описал в этом комментарии: habrahabr.ru/post/187720/#comment_6580780
                          +2
                          Несколько мыслей:
                          1) Обратите внимение на структуры данных BVH2, BVH4;
                          2) Хорошим источником знаний может стать Embree — оптимизированный рендер от Intel с открытым кодом (там включено Global illumination);
                          3) И, конечно, настольная книга по рендерингу Physically Based Rendering;
                          4) Мне понравилось, как написано словосочетание трёх английских слов «Ray tracing рендер» :)
                          0
                          Еще, для чуть большей реалистичности, можно отдельно трассировать красный / зеленый / синий / и промежуточные между ними цвета, предполагая что для них будут разние коэффициенты преломнения на различных стеклянных поверхностях. (Но «разделять» лучи стоит только при прохождении через полупрозрачные обьекты, естественно).
                            0
                            Спасибо за идею. Тоже думал над этим — должно получится довольно красиво.
                            При аккуратной реализации можно будет даже смоделировать опыт Ньютона по разложению белого света, при прохождении сквозь призму :-)
                            +1
                            «Сцена содержит порядка 100000 полигонов (kd-дерево строилось несколько минут)»
                            Что-то долго у Вас строится дерево. У меня сцена Стэндфорского дракона из ровно 100000 треугольников рендерилась ~0,9 секунды включая время построения дерева. Но у меня было тупое деление пополам, без SAH.
                              0
                              К сожалению да. У меня не очень оптимально реализована процедура построения дерева. Более подробно описал в этом комментарии: habrahabr.ru/post/187720/#comment_6580078
                                0
                                Подумал над вашим комментарием, а вы правы!

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

                                Теперь я пытаюсь отыскать оптимальное разбиение только в 5 точках: для сцены с автомобилем (107364 полигонов) — дерево строится за несколько секунд.

                                Вот этот коммит: github.com/lagodiuk/raytracing-render/commit/3a373e3bbaba25e3d777260e326768b2a4d0ec62

                                Спасибо :-)

                                UPD: Упс, комментарий должен быть на уровень выше
                                  +1
                                  Я уже писал чуть выше, что чуть более эффективный способ — не брать какое-то значение (5 или 100), а использовать границы примитивов. Т.е. если в узле 1000 примитивов, ищим SAH в 1000 различных точках, если их 10, то ищим в 10 точках. А опытным путем выбирать количество разбиений — это все же слишком грубо :) При разбиении по центру, конечно, дерево строиться быстрее, всего-то нужно одно действие O(1).

                                  Тут нужен баланс. Дерево строиться будет медленнее, но трассировка лучей в нем будет быстрее.
                                    0
                                    Теперь понял что имеется ввиду :-) Попробую реализовать.

                                    У меня, кстати, ещё была идея — содеражть дополнительный массив объектов, которые не эффективно хранить в kd-дереве (например скайбокс, или объект, который передвигается по сцене).
                              0
                              Содержимое статьи уже не актуально лет эдак 10 (ибо алгоритм легко расспаралеливается, а соответсвенно переносится на гпу: на GLSL шейдер простенького рейтрейса будет занимать около 20 строк). Да и сам рейтрейсинг не является особо интересным так как физически правильного изображения он не дает, а мощностей требует, и не мало. То ли дело — path tracing — вот это другой разговор.
                                +1
                                Он дает физически корректное изображение. В данном плане он не уступает ни одному из path-tracing алгоритмов, т.к. path-tracing суть частный случай рэйтрейсинга (в рэйтрейсинге вторичных лучей может быть сколько угодно, а в path-tracing строго один). Единственный критерий, по которому их следует сравнивать — это скорость сходимости.
                                Вы, наверное, под термином ray-tracing понимаете только его самый примитивный вариант какой-то.
                                  0
                                  Ray-tracing не аппроксимирует уравнение рендеринга, path-tracing это делает за счет Monte-Carlo сэмплинга случайных направлений с весом BRDF зависящей от материала.
                                    +1
                                    А чем это отличается от ray-tracing? Еще раз повторяю: path-tracing — это raytracing, где вторичный луч только один, за счет чего и получается путь, а не дерево. Что мешает пустить несколько вторичных лучей и взвесить их согласно BSDF (кстати, именно BSDF, если уж мы говорим о реалистичности)?
                                    Если Вы все равно не согласны, то, пожалуйста, объясните тогда, что вы понимаете под термином ray-tracing (огласите кратко алгоритм). Кстати говоря, Вы же выше ссылаетесь на книгу «Physically Based Rendering: From Theory to Implementation», где рассказывается о визуализаторе pbrt (PHYSICALLY BASED RAY-TRACER — обратите внимание на название). И этот самый ray-tracer, гад такой, использует path-tracing на пару с Metropolis light transport. Что же, Matt Pharr и Greg Humphreys не знают, что такое ray-tracing?

                                    Извините, я объединю ответы в один комментарий, т.к. могу отвечать не чаще, чем раз в час.
                                    Господину risenow:
                                    «Даже тени приходится делать отчасти фейковые, что-бы смотрелись более-менее нормально»
                                    Ну ничего себе, это что Вы имеете в виду, можете примеры изоражений привести что ли?

                                    Господа, давайте так: объясните для начала, что вы понимаете под термином ray-tracing, а потом уже будем спорить. А то я вижу, что у нас с вами эти понятия отличаются. Еще лучше, если вы приведете ссылки, где говорится, что path-tracing это не ray-tracing и что ray-tracing не может дать физически-корректного изображения.
                                      0
                                      Для того что-бы получить гладкие не-резкие тени нужно хрен-пойми сколько вторичных лучей(их количество порой может достигать 50 и даже больше) через каждый пиксель пропускать.

                                      Нет, лучше вы скажите с чего вы взяли то path tracing как-то относится к ray-tracing(оно конечно относится, но только самыми базывыми принципами). Да и определение которое Вы дали path trace'у сверху — бред, почитайте мат часть, что-ли.
                                        +1
                                        Я матчасть читал, Вы об этом не перживайте. Всё та же книга, например, лежит у меня сейчас на столе.
                                        «Для того что-бы получить гладкие не-резкие тени нужно хрен-пойми сколько вторичных лучей(их количество порой может достигать 50 и даже больше) через каждый пиксель пропускать.»
                                        Я всё об этот и талдычу: ray-tracing допускает множество вторичных лучей. Где тут принципиальная невозможность сделать area light?
                                        Причем опять же, как работает path-tracing? Для того, чтобы изображение не было шумным, надо выпустить некоторое количество путей из каждого пикселя. Точно такой же трюк можно провернуть и с ray-tracing'ом, чтобы не воротить большое число вторичных лучей.
                                        Кстати говоря, вторичные лучи — это лучи для BSDF, а не для прямого освещения (secondary lighting != direct [area] lighting). Прямое освещение тут вообще самая незначительная проблема; если отбросить глобалку, то ray-tracing с множеством direct-lighting лучей будет намного быстрее сходиться, чем path-tracing. А для глобалки — да, множество вторичных лучей неоправданно, т.к. вторичка вносит меньший вклад, чем первичка, причем чем больше номер отскока, тем меньше, а число лучей растет с геометрической прогрессией. В данном случае path-tracing работает намного более рационально. Именно поэтому ray-tracing с множественными отскоками практически не используется. Но ложность изначального утверждения «физически правильного изображения он не дает» это не отменяет.
                                          0
                                          В природе «гладкие не-резкие тени» наблюдаются по двум причинам:
                                          1) существование не точечных источников света
                                          2) в результате освещения диффузно рассеянным светом — областей геометрической тени

                                          А ещё в природе есть:
                                          1) всяческие каустики
                                          2) свет может рассеиваться в результате проникновения в материал на небольшую глубину с последующим излучением (subsurface scattering)
                                          3) есть частички тумана (или дыма), проходя сквозь которые возникает причудливая игра света (в данном случае используется алгоритм — Ray Marching)

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

                                          Ray tracing является алгоритмом для моделирования базовых явлений геометрической оптики.

                                          Нужна колориметрия? — используйте Path tracing (его можно можно реализовать поверх Ray tracing рендера, т.к. оперирует он теми же абстракциями).

                                          И, кстати, а почему именно Path tracing? Ведь для каждого нового положения камеры — приходится заново рендерить всё изображение.

                                          Как по мне — более интересным вариантом является Ray tracing + Photon mapping. В данном случае, фотоны можно сохранять в kd-дереве — и их не нужно заново трасировать при изменении положения камеры.
                                          0
                                          Не буду спорить, от этого алгоритмы не изменятся, мы просто используем немного разное понимание ray-tracing, и разное толкование терминов. По-сути да, ray-tracing'ом можно назвать все методы где используется трассировка лучей. Я привык понимать этот термин очень узко.
                                      0
                                      Не дает он корректного изображения. Даже тени приходится делать отчасти фейковые, что-бы смотрелись более-менее нормально. Path-tracing — совершенно иной способ рендеринга, имеющий схожесть с рейтрейсом только в в том, что и там и там используется лучи.

                                  Only users with full accounts can post comments. Log in, please.