Создание 1k/4k intro для Linux, часть 4

в 5:47, , рубрики: demoscene, distance fields, glsl, OpenGL, raymarching, sizecoding, Анимация и 3D графика, Демосцена, ненормальное программирование, метки: , , , , , ,

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

Что же всё-таки можно нарисовать с помощью всего двух треугольников? Квадрат? Фрактал? Полёт сквозь мегатонной мощности взрыв в центре города? Есть ли предел безумию, где заканчивается реальность и начинается явь? Как правильно ухаживать за лучами, чем их кормить и обо что отражать вы узнаете во внезапном продолжении цикла статей про демомейкинг!

Создание 1k/4k intro для Linux, часть 4

Введение

Для удобства прототипирования предлагаю пользоваться shadertoy.com, ссылки с примерами будут вести туда же. Таким образом даже пользователи альтернативных операционных систем могут погрузиться во всё это замечательное, что тут будет.
Да, под виндовс WebGL, которым мы будем неявно пользоваться, все почему-то любят реализовывать через ANGLE, который наркоман и знаменит своим запарыванием сложных шейдеров. Поэтому рекомендую включить нативный OpenGL (в хроме: --use-gl=desktop при запуске), иначе после третьего-четвёртого примера у вас всё взорвётся и едва ли будет соответствовать обсуждаемому.
И да, нужны довольно мощные современные видеокарты, что-нибудь уровня GTX 4xx или HD 6xxx как минимум (и ни в коем случае не Intel, что смеяться), иначе будет диафильм.

Введение-2

Не буду вдаваться в подробности, что такое шейдеры, откуда они и почему — это тема для отдельного цикла статей, которого не будет, лол — достаточно только понять, что нам предстоит на си-подобном синтаксисе записывать в переменную gl_FragColor цвет текущего пикселя в зависимости от его координат gl_FragCoord (в пикселях) и времени iGlobalTime (это специфика шейдертоя, в стандарте GLSL ничего про время, естественно, нет).
В GLSL помимо всего прочего есть векторные и матричные типы vecN, matN и стандартная библиотека всяких математических и не очень функций. Хреф для любознательных (GL ES потому что шейдертой это WebGL, который унаследован от OpenGL ES 2.0).

Realtime raytracing

Делать предлагаю то, что ещё лет 10-15 назад считалось недостижимой мечтой — трассировку лучей в реальном времени. Современные виедеокарты настолько чудовищно производительны, что да.
Основная идея — для того, чтобы определить цвет пикселя на экране, пускаем из него луч и ищем, в какой объект он упрётся, после чего используя знания об объекте и точке пересечения каким-то образом рассчитываем освещённость и формируем искомый цвет.
Как можно определить, пересекает ли луч определённый объект, и если да, то в какой точке? Можно, например, выписать уравнения пересечения луча с нужным объектом и решить их аналитически. Нетрудно обнаружить, что этот метод очень быстро становится довольно громоздким для чего бы то ни было сложнее сферы или плоскости. Это не годится, мы хотим рисовать высадку стаи кошачьих на Марс, поэтому воспользуемся другим методом, а именно сферическую трассировку функций расстояния.

From me to you

Функция расстояния — это функция R3->R, возвращающая расстояние до ближайшей геометрии для каждой точки пространства. На практике писать такие функции даже для простых фигур проще, чем аналитическое пересечение. Например:

  • Шар: length(at) - R
  • Плоскость: dot(at,N) - D
  • Параллелепипед: length(max(abs(at)-size), 0.))
  • Цилиндр (Y): length(at.xz) - R

Кроме этого, пользуясь такими функциями легко делать конструктивную геометрию:

  • Объединение: min(f, g)
  • Пересечение: max(f, g)*
  • Вычитание: max(f, -g)*

И трансформации — достаточно преобразовать входной семплирующий вектор at:

  • Перенос: at-vec3(pos)
  • Поворот и прочее: at*mat3(<матрица поворота или другой трансформации>) (для масштабирования надо иметь ввиду, что возвращенное расстояние нужно отмасштабировать назад)

* — не строгие ф-и расстояния, оценка

Сферическая трассировка

Как же находить пересечение луча с такой функцией? Одно простое и элегантное решение — сферическая трассировка. Алгоритм следующий:

  1. Начинаем луч в направлении D из точки O.
  2. Получаем d, равное значению функции в точке O
  3. Сдвигаем точку O в направлении D на расстояние d
  4. Если d больше некоего выбранного порогового значения, возвращаемся к п.2
  5. Текущая точка O — и есть искомое пересечение с заданной точностью, выходим

Создание 1k/4k intro для Linux, часть 4

На GLSL простая функция трассировки выглядит так:

float trace(vec3 O, vec3 D) {
	float L = 0.;
	for (int i = 0; i < MAX_STEPS; ++i) {
		fload t = world(O + D*L);
		L += d;
		if (d < EPSILON) break;
	}
	return L;
}

Итого, простой марчер для сферы радиусом 1 в начале координат выглядит, например, вот так (визуализация пройденного расстояния):

// константы, которые мы наверняка будем настраивать
#define MAX_STEPS 32
#define EPSILON .001

// функция расстояния для нашего маленького уютного виртуального мира
float world(vec3 a) {
	return length(a) - 1.; // сфера радиусом 1 в центре
}

// функция трассировки луча из точки O в нормализованном направлении D. возвращает пройденное расстояние
float trace(vec3 O, vec3 D) {
	float L = 0.; // пройденное расстояние
	for (int i = 0; i < MAX_STEPS; ++i) { // для MAX_STEPS шагов
		float d = world(O + D*L); // получаем расстояние до ближайшей геометрии
		L += d; // шагаем на это расстояние
		if (d < EPSILON*L) break; // если оно меньше порогового значения, выходим
	}
	return L; // возвращаем пройденное расстояние
}

void main(void) {
	// нормализуем экранные координаты к [-1., 1.]
	vec2 uv = gl_FragCoord.xy / iResolution.xy * 2. - 1.;

	// исправляем соотношение сторон экрана
	uv.x *= iResolution.x / iResolution.y;
	
	// точка начала
	vec3 O = vec3(0., 0., 3.);

	// смотрим в отрицательном по оси z направлении; -2. имеет смысл тангенса угла обзора или что-то такое
	vec3 D = normalize(vec3(uv, -2.));
	
	// вычисляем пройденный путь
	float path = trace(O, D);
	
	// записываем цвет, пропорциональный проёденному расстоянию
	gl_FragColor = vec4(path * .2);
}

Создание 1k/4k intro для Linux, часть 4

Сфера наша подозрительно висит в воздухе, поэтому давайте положим её на плоскость, например:

float world(vec3 a) {
	return min(length(a) - 1., a.y + 1.);
}

Создание 1k/4k intro для Linux, часть 4

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

vec3 enlight(vec3 at, vec3 normal, vec3 diffuse, vec3 l_color, vec3 l_pos) {
	// направление на источник света из текущей точки
	vec3 l_dir = l_pos - at;
	// цвет = произведение цветов источника и поверхности
	// освещенность = косинус угла (=скалярное произведение нормализованных векторов)
	// поделить на квадрат расстояния до источника света (=скалярное произведение с собой)
	// ну и надо не забывать про то, что отрицательный косинус просто не будет давать света
	return diffuse * l_color * max(0.,dot(normal,normalize(l_dir))) / dot(l_dir, l_dir);
}

Нормаль получить просто — это всего-лишь градиент нашей функции расстояния:

vec3 wnormal(vec3 a) {
	vec2 e = vec2(.001, 0.);
	float w = world(a);
	return normalize(vec3(
		world(a+e.xyy) - w,
		world(a+e.yxy) - w,
		world(a+e.yyx) - w));
}

Результат:
Создание 1k/4k intro для Linux, часть 4

Чего-то не хватает, не так ли? Сфера всё равно будто висит, да и темновато как-то.
Для того, чтобы глазкам было совсем реалистично и приятно, надо добавить две штуки: тень и подстаканную тень.

Сперва, добавим ambeint-освещение, просто добавив к color что-нибудь вроде vec3(.1) или .2, по-вкусу.
Подстаканная тень, она же ambient occlusion — это приближение эффекта из реального мира, когда поверхность оказывается частично заслонена от фотонов, летящих со всех сторон, а не только от источника света.
В реалтайм тридэ графике существует множество способов получения схожего эффекта разной степени упоротости. В используемой технике каноническим подходом является эксплуатация scene-space данных о близости геометрии — делаем несколько шагов вдоль нормали и определяем, насколько близко что бы то ни было, что могло бы нас затенить. Это довольно немытый хак (как, в общем-то, и всё, что мы вообще делаем на этой планете), но он выглядит довольно ок.
Вот код:

// коэффициент подстаканной тени
float occlusion(vec3 at, vec3 normal) {
	// изначально считаем, что затенения вообще нет
	float b = 0.;
	// делаем четыре шага
	for (int i = 1; i <= 4; ++i) {
		// с промежутком .06 -- этот параметр можно тюнить
		float L = .06 * float(i);
		float d = world(at + normal * L);
		// добавляем к коэффициенту ограниченную разницу расстояний между пройденным и минимальным
		b += max(0., L - d);
	}
	// коэффициент больше 1 не имеет смысла
	return min(b, 1.);
}

Обычная тень делается ещё проще — мы просто пускаем луч из точки в источник света и смотрим, не упёрлись ли во что по пути.

if (trace(at, normalize(l_dir), EPSILON*2.) < length(l_dir)) return vec3(0.);

Обратите внимание на то, что ровно из той точки начинать нельзя, надо отступить чуть-чуть (домашнее задание: почему?)

И напоследок залепим туда чернющий туман, чтобы фон с ambient-освещением не сливался:

color = mix(color, vec3(0.), smoothstep(0.,20.,path));

Итого:
Создание 1k/4k intro для Linux, часть 4

Материальные ценности

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

struct material_t {
	vec3 diffuse;
	float specular;
};

Разделим наш мир на функции, возвращающие геометрию отдельных материалов и напишем следующую функцию:

// возвращаем материал для указанной точки
material_t wmaterial(vec3 a) {
	// начинаем с материала шара
	material_t m = material_t(vec3(.5, .56, 1.), 200.);
	float closest = s_ball(a);
	
	// проверяем следующий объект сцены -- пол
	float sample = s_floor(a);
	// если он оказался ближе
	if (sample < closest) {
		// запоминаем как ближайший
		closest = sample;
		// выставляем его материал -- диффузная шахматрная доска
		m.diffuse = vec3(1.-mod(floor(a.x)+floor(a.z), 2.));
		m.specular = 0.;
	}
	return m;
}

Теперь достаточно в функции освещения заиспользовать материал, а не константу цвета.
Последним штрихом добавим блики. Вообще, спекулярные блики — это тоже костыль-костыль, попытка симуляции реального эффекта отражения света от металлов (по-честному физически это делать сложно — там начинаются всякие BRDF, уравнения рендеринга, шатание луча по Метрополису и прочая тяжеловесная академическая графика, которую я не понимаю), поэтому существует стопка различных методов приближения этого эффекта. Здесь мы воспользуемся нормализованным методом Блинн-Фонга, который сводится к косинусу угла между нормалью и полувектором между наблюдателем и источником света. Спекулярные блики физически не зависят от диффузного цвета материала.
Долго ли, коротко ли, вот код:

if (m.specular > 0.) {
	// пользуемся, блин, фонгом -- строим срединный вектор между камерой и источником
	vec3 h = normalize(normalize(l_dir) + normalize(eye-at));
	// БДЫЩ и нормализация в конце
	color += l_color * pow(max(0.,dot(normal,h)), m.specular) * (m.specular + 8.) / 25.;
}

Итого:
Создание 1k/4k intro для Linux, часть 4

Как об стенку горох

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

// суммарный цвет пикселя со всеми сложенными отражениями
vec3 result_color = vec3(0.);

// вес текущего луча
float k_reflectivity = 1.;

for (int i = 0; i < MAX_REFLECTIONS; ++i) {
	// вычисляем пройденный путь
	float path = trace(O, D, 0.);
	
	// если ни на что не наткнулись, закругляемся
	if (path < 0.) break;
	
	// точка, в которую пришли	
	vec3 pos = O + D * path;
	vec3 nor = wnormal(pos);

	// материал в текущей точке
	material_t mat = wmaterial(pos);

	// освещение окружения
	vec3 color = .15 * (1. - occlusion(pos, nor)) * mat.diffuse;

	// освещение из источника
	color += enlight(pos, nor, O, mat, vec3(1., 1.5, 2.), vec3(2.*cos(t), 2., 2.*sin(t)));
	color += enlight(pos, nor, O, mat, vec3(2., 1.5, 1.), vec3(2.*sin(t*.6), 3., 2.*cos(t*.6)));

	// как-бы туман
	color = mix(color, vec3(0.), smoothstep(0.,20.,path));
	
	// добавим текущий цвет к суммарному
	result_color += k_reflectivity * color;
	
	// получим коэффициент следующего луча
	k_reflectivity *= mat.reflectivity;
	
	// выйдем, если вклад будет слишком мал
	if (k_reflectivity < .1) break;
	
	// отразим луч и начнем с текущей позиции
	D = normalize(reflect(D, nor));
	O = pos + D * EPSILON*2.;
}

Внесём ещё всякие добавления в сцену, и вот как нарисовать сыча:
Создание 1k/4k intro для Linux, часть 4

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

Но сперва следует сделать небольшое отступление в мир беспорядка.

Теория хаоса

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

float hash(float x) { return fract(sin(x)*48737.3213); }

где 48737.3213 — это просто случайное число, которое я только что вслепую котом набрал на цифровой клавиатуре. Ребята в интернетах любят копипастить определённое число и таскать его за собой всюду, но объяснения этому я не встречал.
Шум от vec2 можно получить таким образом:

float hash(vec2 x) { return hash(dot(x,vec2(71.,313.))); }

Эти функции, как ясно из названия — как-бы хеш от входного числа, и при малейшем изменении этого самого числа, их значение меняется значительно. Для наших целей же нам нужно иметь функцию, значение которой меняется более плавно. Есть несколько способов построения таких функций, которые можно основать на хешах, основные из них — perlin noise, value noise, simplex noise.

В интернете в этом сезоне модно ошибаться насчет шума Перлина и считать его сложением нескольких октав шумов. Многооктавный шум, или фрактальный шум — это совершенно отдельная техника, которая может основываться не только на шуме Перлина, но и на любом другом. Шум Перлина же построен на том, что мы берём N-мерную сеточку и расставляем в её узлах случайные нормализованные градиенты (= просто нормализованные случайные вектора), после чего для каждой точки пространства мы можем определить, в каком объёме сетки находимся, посчитать скалярное произведение со всеми узлами и N-линейно интерполировать между этими произведениями. Линейную интерполяцию можно заменить на более сложную, например, делающую гладкой вторую производную результирующего шума, если вам это зачем-нибудь нужно. Вот это шум Перлина. Он громоздкий и крутой. После этой двухминутки ликбеза вы теперь тоже можете смеяться над всеми остальными и задирать нос:
Создание 1k/4k intro для Linux, часть 4

Симплексный и Перлина шумы мы здесь не будем использовать из-за их чрезмерной вычислительной сложности. Для наших скромных целей порабощения вселенной достаточно value noise — берём случайные значеия в узлах сетки и интерполируем между ними, вот так:

// гладкий value noise
float noise(vec2 x) {
	// F - левый нижний узел сетки, f - вес пра
	vec2 F = floor(x), f = fract(x);
	// пятисекундка удобства
	vec2 e = vec2(1.,0.);
	
	// сглаживание
	f *= f * (3. - 2. * f);
	
	// билинейная интерполяция
	return mix(
		mix(hash(F+e.yy), hash(F+e.xy), f.x),
		mix(hash(F+e.yx), hash(F+e.xx), f.x), f.y);
}

Теперь пресловутый фрактальный шум получается простым суммированием нескольких октав:

// фрактальный шум
float fnoise(vec2 x) {
	// сдвинем из избыточно регулярного начала координат
	x += vec2(10.);
	// сложим октавы
	return .5 * noise(x)
		+ .25 * noise(x*1.97)
		+ .125 * noise(x*4.04)
		+ .0625 * noise(x*8.17)
		;
}

Итого, получаем такое визуальное представление шума:
Создание 1k/4k intro для Linux, часть 4
(секретный бонус-трек-2)

Разрушая всё

Пользуясь таким источником случайности, можно сделать всё, что угодно. Например, нарисовать город.
Основная идея: побьём пространство на кварталы-секторы, и для каждого сектора, пользуясь его номером-координатами, будем извлекать из хаоса параметры строения — размеры, этажность, тип.
Точно так же можно подсветить, например, окна — в зависимости от высот и положения берём случайное число и на его основе решаем, включен свет в данном «окне» или нет.
Положение камеры, звёздное небо — это всё тоже достаётся из коробки со случайными значениями.
В общем, я на самом деле уже просто устал писать этот скудноватый текст. Скорее всего даже больше, чем вы устали его читать. Поэтому давайте просто посмотрим на ????? PROFIT и ляжем спать уже наконец!

Внимание, слайд-шоу на ваших видеокартах:
Создание 1k/4k intro для Linux, часть 4

Заключение

Осталось теперь это хозяйство минифицировать — убрать немногочисленные комментарии, сократить названия переменных и функций, убрать пробелы, переводы строк, привести к тому виду, в котором наш фреймворк из второй части ожидает (вставить наши переменные вместо шейдертоевских) и можно релизить. Ну то есть нельзя, потому что это всё равно полная безвкусица и нужен дизайнер, который бы всё время бил программистов по рукам.
В общем, это домашнее задание — сделать этот шейдер запускаемым и посмотреть, сколько байт весит elf с ним. Моя предварительная оценка — 2..2.5Кб.

А, и последнее: по странному стечению обстоятельств я буду внезапно сегодня (Пн, 21.10.2013) про это же самое чуть подробнее рассказывать в НГУ (Новосибирском Государственном Университете) вечером в 19:30 в ауд. 223 нового спорткомплекса. Можете не приходить, потому что вы уже всё знаете, лол. Ну то есть наоборот — приходите — полайвкодим!

В предыдущих сериях: синтез музыки на языке программирования си.
В следующих сериях: unbiased path tracing полигональной геометрии в реальном времени на OpenCL, наверное.

Автор: w23

Источник

Поделиться

* - обязательные к заполнению поля