Ray marching и не только

Давненько я не баловался фракталами, а руки что-то чешутся... Видимо пора сотворить что-то и поделиться с миром ) Но всё меняется, вернее давно поменялось, фракталы уже давно рисуются шейдерами, как правило фрагментными. И то что я когда то делал (ковёр Серпинского, остора Коха и другое - на основе линий) - увы, уже не впечатляет ;) Скрины 3d фракталов впечатляют и завораживают, глядя на некоторые даже не верится, что их сотворил алгоритм.
Для визуализации поверхности, которая не определена полигонами, мы попробуем использовать ray marching (raymarching, марширующий луч, марш луча, ну в общем за точность перевода не ручаюсь), а результат думаю скоро сами увидим )) Важно заметить, что эта техника используется не только для рисования фракталов.

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

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

Чуть ниже приведу пример рабочей функции, вообще много можно их найти на shadertoy просматривая код шейдеров, обычно функция называется что-то вроде rayMarching, castRay, Marching, но встречались варианты и подлиннее (shortestDistanceToSurface). sceneSDF (Signed distance function) ориентированная (знаковая) функция расстояния описывающая нашу сцену, она возвращает положительное число, пока луч не столкнулся с поверхностью, ноль - если точка находится на поверхности и отрицательное число, если мы уже преодолели поверхность и попали внутрь объекта. Хотя на практике используют некое приближение, в данном случае, если дистанция меньше, чем EPSLON, то считается, что луч достиг поверхности.

// Максимальное количество шагов
#define MAX_MARCHING_STEPS 250
// Минимальная и максимальная дистанция
#define MIN_DIST 0.0
#define MAX_DIST 100.0
//
#define EPSILON  0.0001

// eye - позиция наблюдателя
// rayDirection - направление луча
float rayMarching(vec3 eye, vec3 rayDirection)
{
    float depth = MIN_DIST;
    for (int i = 0; i < MAX_MARCHING_STEPS; i++)
    {
        // Ориентированная функция расстояния, нашей сцены
        float dist = sceneSDF(eye + depth * rayDirection);
        // Мы достигли поверхности
        if (dist < EPSILON)
  return depth;
        // Продвигаемся дальше по лучу
        depth += dist;
        // Луч не столкнулся с поверхностью
        if (depth >= MAX_DIST)
            return MAX_DIST;

    }
    return MAX_DIST;
}

Начнём мы не с фракталов, а с фигур попроще  - нарисуем  прямоугольник с закруглёнными краями. Кстати, если вам захочется попробовать другие примитивы, то вот тут есть отличная подборка. Можно также выполнять объединение, пересечение и разность этих примитивов, можно их перемещать, вращать, масштабировать, а так же повторять. Ну чем не полноценные 3D объекты? ))

// Round Box
float udRoundBox( vec3 pos, vec3 b, float r )
{
  return length(max(abs(pos)-b, 0.0))-r;
}

float sceneSDF(vec3 pos)
{
    // Тут может быть много объектов
    // И даже их комбинации (пересечение, объединение и разность)
    return udRoundBox(pos, vec3(.5, .5, 0.2), 0.3);
}

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

vec3 rayDirection(float fieldOfView, vec2 size, vec2 fragCoord)
{
    vec2 xy = fragCoord - size / 2.0;
    float z = size.y / tan(radians(fieldOfView) / 2.0);
    return normalize(vec3(xy, -z));
}

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

// Матрица вида
mat4 viewMatrix(vec3 eye, vec3 center, vec3 up)
{
    // Based on gluLookAt man page
    vec3 f = normalize(center - eye);
    vec3 s = normalize(cross(f, up));
    vec3 u = cross(s, f);
    return mat4(
        vec4(s, 0.0),
        vec4(u, 0.0),
        vec4(-f, 0.0),
        vec4(0.0, 0.0, 0.0, 1)
    );
}

// main он и в шейдере main ))
void main()
{
 vec3 viewDir = rayDirection(45.0, Resolution, gl_FragCoord.xy);
    vec3 eye = Eye; //vec3(8.0, 5.0, 7.0);
    // Переходим к Мировым координатам
    mat4 viewToWorld = viewMatrix(eye, vec3(0.0, 0.0, 0.0), vec3(0.0, 1.0, 0.0));
    // Вычисляем дистанцию
    vec3 worldDir = (viewToWorld * vec4(viewDir, 0.0)).xyz;
    // Запускаем наш луч
    float dist = rayMarching(eye, worldDir);

    if (dist > MAX_DIST - EPSILON)
    {
        // Пустота - не рисуем
        gl_FragColor = vec4(0.0, 0.0, 0.0, 1.0);
  return;
    }

    vec3 color = vec3(1.0, 0.0, 0.0);
    // Рисуем красным
    gl_FragColor = vec4(color, 1.0);
}

Но результат надо признать, не впечатляет. Ах да, вы же ещё не видели - вот он :

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

// Оцениваем нормали
vec3 estimateNormal(vec3 p)
{
    return normalize(vec3(
        sceneSDF(vec3(p.x + EPSILON, p.y, p.z)) - sceneSDF(vec3(p.x - EPSILON, p.y, p.z)),
        sceneSDF(vec3(p.x, p.y + EPSILON, p.z)) - sceneSDF(vec3(p.x, p.y - EPSILON, p.z)),
        sceneSDF(vec3(p.x, p.y, p.z  + EPSILON)) - sceneSDF(vec3(p.x, p.y, p.z - EPSILON))
    ));
}

И в main надо добавить пару строчек, вернее изменить одну и добавить ещё одну ))

// Самая близкая точка вдоль луча
    vec3 p = eye + dist * worldDir;
// Рассчитываем итоговый цвет
    vec3 color =  mix(vec3(1.0, 0.0, 0.0), vec3(0.4, 0.0, 0.0),  estimateNormal(p));

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

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

// Освещение по фонгу
// подробности https://en.wikipedia.org/wiki/Phong_reflection_model#Description
vec3 phongLight(vec3 k_d, vec3 k_s, float shininess, vec3 p, vec3 eye, vec3 lightPos, vec3 lightIntensity)
{
    vec3 N = estimateNormal(p);
    vec3 L = normalize(lightPos - p);
    vec3 V = normalize(eye - p);
    vec3 R = normalize(reflect(-L, N));

    float dotLN = dot(L, N);
    float dotRV = dot(R, V);

    if (dotLN < 0.0) {
        // С этой точки поверхности не видно света
        return vec3(0.0, 0.0, 0.0);
    }

    if (dotRV < 0.0) {
        // Отражение в противоположном направление от зрителя
        // используем  дифузный компонент
        return lightIntensity * (k_d * dotLN);
    }

    //
    return lightIntensity * (k_d * dotLN + k_s * pow(dotRV, shininess));
}

Ну и основную функцию придётся переделать источник света крутится над объектом (за это отвечает Time) :

// main он и в шейдере main ))
void main()
{
 vec3 viewDir = rayDirection(45.0, Resolution, gl_FragCoord.xy);
    vec3 eye = Eye; //vec3(8.0, 5.0, 7.0);
    // Переходим к Мировым координатам
    mat4 viewToWorld = viewMatrix(eye, vec3(0.0, 0.0, 0.0), vec3(0.0, 1.0, 0.0));
    // Вычисляем дистанцию
    vec3 worldDir = (viewToWorld * vec4(viewDir, 0.0)).xyz;
    // Запускаем наш луч
    float dist = rayMarching(eye, worldDir);

    if (dist > MAX_DIST - EPSILON)
        discard; //  Не рисуем

    // Самая близкая точка вдоль луча
    vec3 p = eye + dist * worldDir;

    // Константы для освещения
    const vec3 K_a = vec3(0.2, 0.2, 0.2); // Ambient color
    const vec3 K_d = vec3(0.7, 0.2, 0.2); // Diffuse color
    const vec3 K_s = vec3(1.0, 1.0, 1.0); // Specular color
    const float Shininess = 10.0; //
    const vec3 ambientLight = 0.5 * vec3(1.0, 1.0, 1.0);
    vec3 color = ambientLight * K_a;
    // источник света
    vec3 lightPos = vec3(4.0 * sin(Time),
                          2.0,
                          4.0 * cos(Time));
    vec3 lightIntensity = vec3(0.4, 0.4, 0.4);
    color += phongLight(K_d, K_s, Shininess, p, eye, lightPos, lightIntensity);

    // Рисуем красным
    gl_FragColor = vec4(color, 1.0);
}

А теперь посмотрим результат, на мой взгляд выглядит неплохо )) Хотя от ярко красного цвета я решил уйти, но вы можете поправить это дело изменив константу K_d.

Ну думаю вполне хватит материала, для одной записи. Дальше перейдём к фракталам или сложную сцену попробуем сделать, для эксперимента. Чуть позже залью исходники на github и возможно сделаю вариант на shadertoy, чтобы можно было сразу посмотреть результат )

Демка на shadertoy.
Архив с исходниками для движка Irrlicht (проект под Code::Blocks,  6.63kb)

Ели что не так, то пишите в комментариях ;)

Дополнил:
Нашёл на шейдерстрое сцену со всеми примитивами со странички iquilezles.org
https://www.shadertoy.com/view/Xds3zN