WebGL-калейдоскоп, ч.1
Захотелось сделать рисовалку калейдоскопа в виде HTML-страницы. Вдруг. Причём, более-менее честную, на основе трассировки лучей. Здесь я попробую описать всё «с нуля». В качестве графического API выбран WebGL2 (но объяснять в подробностях я не буду, иначе получится слишком длинный текст). По сути, основная работа будет выполняться в фрагментном (пиксельном) шейдере.
Начну с описания геометрии. Я решил ограничиться конфигурацией зеркал в виде треугольной призмы. Основание такой призмы — равносторонний треугольник, вписанный в круг радиуса два. Соответственно, круг, вписанный в треугольник, имеет радиус, равный единице. Ось зрения направлена параллельно сторонам призмы через центры вписанных в основания кругов. Экран (прямоугольник, в котором формируется картинка) вписываем во вписанный в треугольник единичный круг. Ось зрения проходит через центр (точку пересечения диагоналей) экрана.
На схеме красным условно показан луч, выпущенный из камеры через некоторую точку на экране и испытывающий одно отражение от зеркальной стенки призмы до попадания на заднюю стенку калейдоскопа. Камера сдвинута на расстояние f от экрана, задняя стенка — на расстояние L. Таким образом, начало координат находится в центре экрана, а наш базис имеет левую ориентацию: ось 0x направлена вправо, ось 0y — вверх, ось 0z — вперёд. В рассматриваемой задаче ориентация базиса никакой роли не играет.
Фрагментный шейдер выполняется для каждого пикселя и получает координаты этого пикселя относительно нижнего левого угла (вертикальная ось направлена вверх) в виде предопределённой переменной gl_FragCoord (там ещё есть z-координата и величина 1/w в качестве четвёртой координаты, но здесь они нам не нужны). Координаты принимают значения от 0.5 до W−0.5 (по горизонтали) или до H−0.5 (по вертикали), где W и H суть размеры экрана в пикселях (разрешение), изменяясь с шагом 1.
В координатах нашей схемы это должно отображаться в прямоугольник с фиксированной диагональю длины два. Итак, требуется вывести нормировочный коэффициент. Поскольку длина диагонали в пикселях есть sqrt(W2 + H2), то надо отцентрированные координаты (когда вычли (W/2, H/2), чтобы переместить начало координат в центр экрана) умножать на 2/sqrt(W2 + H2). Наш фрагментный шейдер должен получать эти значения извне (в виде юниформов — глобальных констант, значения которых задаются внешним кодом):
// Половина разрешения канваса по горизонтали и вертикали,
// т.е. (0.5*W, 0.5*H), где W и H -- разрешение канваса.
uniform vec2 u_half_resolution;
// Коэффициент, на который надо домножить координаты пикселя,
// чтобы вписать их в единичный круг.
// Вычисляется как 2 / sqrt(W*W + H*H).
uniform float u_resolution_scale;
void main()
{
vec2 screen_position =
u_resolution_scale * (gl_FragCoord.xy - u_half_resolution);
// TODO: написать всё остальное.
Заметим, что луч света проходит одно и то же расстояние вдоль оси 0z, независимо от количества отражений. Таким образом, задачу определения координат пересечения луча с задней стенкой можно свести к двумерной задаче отражений луча в равностороннем треугольнике.
Для начала, вычислим длину луча в трёхмерном пространстве. Очевидно, это (L + f)/cos(α), где α — угол между лучом и осью зрения. Соответственно, в проекции на треугольник луч будет иметь длину (L + f) tg(α). Найти этот угол не сложно: имеем прямоугольный треугольник, образованный точками с координатами (0, 0, -f), (0, 0, 0) и (x, y, 0), где (x, y) — координаты screen_position, полученные на предыдущем этапе. Противолежащий катет равен sqrt(x2 + y2), прилежащий катет — f, соответственно, tg(α) = sqrt(x2 + y2)/f. Итак, длина проекции луча равна (L/f + 1) sqrt(x2 + y2). Коэффициент (L/f + 1) есть константа, её тоже следует передавать в шейдер в виде юниформа.
// Половина разрешения канваса по горизонтали и вертикали, т.е.
// (0.5*W, 0.5*H), где W и H -- разрешение канваса.
uniform vec2 u_half_resolution;
// Коэффициент, на который надо домножить координаты пикселя,
// чтобы вписать их в единичный круг.
// Вычисляется как 2 / sqrt(W*W + H*H).
uniform float u_resolution_scale;
// Отношение длины зеркал к расстоянию до камеры + 1.
uniform float u_length_to_focus_ratio_plus_one;
void main()
{
vec2 screen_position =
u_resolution_scale * (gl_FragCoord.xy - u_half_resolution);
float max_ray_length =
u_length_to_focus_ratio_plus_one * length(screen_position);
// TODO: написать всё остальное.
По построению, наш луч обязательно должен пересечься либо с задней стенкой, либо отразиться от одного из зеркал. Отражение будем проверять, вычисляя точки пересечения луча с прямыми, проведёнными через стороны треугольника (уже в плоскости 0xy). В случае наличия отражения вычисляется новая точка начала луча и отражённое направление, далее весь процесс повторяется.
Итак, есть луч, заданный параметрически: p(s) = R + rs, s ≥ 0, пусть |r| = 1. Есть прямая, проходящая через точку A, имеющую единичную нормаль n. Чтобы найти точку пересечения, нужно подставить параметрическое выражение точки на луче в уравнение прямой: (p — A)·n = 0, где · обозначает скалярное произведение. Итак,
(R + rs − A)·n = 0,
(r·n)s = (A − R)·n,
s = ((A − R)·n) / (r·n).
Не имеет смысла вычислять s, если r·n ≥ 0 (пусть нормали «смотрят» внутрь треугольника). А раз должно получиться s > 0, то должно выполняться и (A − R)·n < 0. Из s, полученных для сторон треугольника, удовлетворяющих указанным условиям, выберем минимальное, т. е. дающее первое пересечение. По построению, эта точка будет лежать на треугольнике. Подставив s в p(s), получим новое значение R (положение точки на зеркале в проекции). Чтобы получить новое значение r следует отразить старое r, используя нормаль того зеркала, на которое мы попали (ну вы поняли, угол падения равен углу отражения). Для этого в GLSL даже есть специальная функция reflect.
Так как у нас три стороны, для каждой из них нужно задать свои значения A и n. Поскольку единичный круг касается всех трёх сторон треугольника, то в качестве точек A можно выбрать точки касания. Заодно автоматически получим n = −A. Итак, n0 = (0, 1), n1 = (-sqrt(3)/2, -1/2), n2 = (sqrt(3)/2, -1/2).
Если n = −A, то s = −(1 + R·n) / (r·n).
Я напишу функцию intersect, которая принимает R (ray_start), r (ray_dir), возвращает следующее значение R (точку на зеркале), следующее значение r (через параметр reflected_dir) и длину отрезка от старого R до нового R (length). Написана она без изощрений. Возможно, это можно как-то оптимизировать, но не к спеху.
// Нормали к сторонам правильного треугольника,
// описанного вокруг единичного круга.
const vec2 n0 = vec2(0., 1.);
const vec2 n1 = -0.5 * vec2(+sqrt(3.), 1.);
const vec2 n2 = -0.5 * vec2(-sqrt(3.), 1.);
// Найти ближайшее отражение луча от зеркал.
// ray_start начало луча
// ray_dir единичный вектор направления луча
// reflected_dir отражённый вектор направления луча
// length расстояние между началом луча и точкой отражения
// @return точка отражения луча
vec2 intersect(
in vec2 ray_start,
in vec2 ray_dir,
out vec2 reflected_dir,
out float length)
{
float divisor0 = dot(ray_dir, n0);
float divisor1 = dot(ray_dir, n1);
float divisor2 = dot(ray_dir, n2);
float dividend0 = -1.0 - dot(ray_start, n0);
float dividend1 = -1.0 - dot(ray_start, n1);
float dividend2 = -1.0 - dot(ray_start, n2);
vec2 n = n0;
length = 100.;
if (divisor0 < 0. && dividend0 < 0.)
{
length = dividend0 / divisor0;
}
if (divisor1 < 0. && dividend1 < 0.)
{
float s = dividend1 / divisor1;
if (s < length)
{
length = s;
n = n1;
}
}
if (divisor2 < 0. && dividend2 < 0.)
{
float s = dividend2 / divisor2;
if (s < length)
{
length = s;
n = n2;
}
}
reflected_dir = reflect(ray_dir, n);
return ray_start + ray_dir * length;
}
Теперь напишем до конца функцию main фрагментного шейдера. Пусть на каждом отражении яркость луча понижается умножением на коэффициент затухания (attenuation_factor). Сделаем его константой:
// Коэффициент затухания на каждом отражении.
const float attenuation_factor = 15. / 16.;
// Максимальное допустимое затухание.
const float attenuation_threshold = 1. / 256.;
Поскольку на практике почти везде используется 8 бит на канал, то при затухании в 256 раз итоговый цвет пикселя будет чёрным, поэтому зададим соответствующую константу attenuation_threshold.
Имеем цикл, вычисляющий пересечения либо до достижения заданной длины луча, либо до достижения предельного затухания.
// Трассировка луча.
// Накопленная длина.
float accumulated_length = 0.0;
// Затухание.
float attenuation = 1.0;
// Начальная точка луча и
// результирующая точка после цикла.
vec2 ray_start = vec2(0., 0.);
// Направление луча.
vec2 ray_dir = normalize(screen_position);
do
{
// Длина следующего отрезка.
float segment_length;
// Отражённое направление луча.
vec2 new_ray_dir;
// Новое начало (на зеркале) луча.
vec2 new_ray_start = intersect(
ray_start, ray_dir, new_ray_dir, segment_length);
// Остаток длины луча.
float remaining_length = max_ray_length - accumulated_length;
// Если луч закончился до пересечения,
// то он попал на заднюю стенку.
if (remaining_length <= segment_length)
{
ray_start += remaining_length * ray_dir;
break;
}
// Подготовить следующую итерацию.
accumulated_length += segment_length;
ray_start = new_ray_start;
ray_dir = normalize(new_ray_dir);
attenuation *= attenuation_factor;
} while (attenuation > attenuation_threshold);
После цикла значения координат луча на задней стенке калейдоскопа находятся в переменной ray_start. В данный момент я не готов реализовать имитацию осколков цветного стекла, вместо этого я буду рисовать банальный белый круг на чёрном фоне. Координаты центра круга буду задавать юниформом u_center_offset. Затухание буду применять только к зелёному каналу.
ray_start -= u_center_offset;
if (attenuation > attenuation_threshold
&& dot(ray_start, ray_start) <= 1.0)
o_color = vec4(1., attenuation, 1., 1.);
else
o_color = vec4(0., 0., 0., 1.);
// конец main.
}
// Дополнительные объявления в начале шейдера:
// out vec4 o_color;
//// Сдвиг центра круга (временно).
// uniform vec2 u_center_offset;
Теперь опишу всё остальное. Начнём с каркаса HTML-файла:
<!DOCTYPE html>
<html style="width: 100%; height: 100%; margin: 0;">
<head>
<meta charset="utf-8" />
<title>Калейдоскоп-v1</title>
</head>
<body style="position: relative; width: 100%; height: 100%; margin: 0;">
<canvas id="picto" style="position: absolute; display: inline-block; overflow: clip;">
</canvas>
<script>
// ...
</script>
</body>
</html>
Всё, что есть на странице — объект canvas, растянутый на всё окно браузера. Обратите внимание на стилевые опции. На практике может быть трудно избежать каких-нибудь дефектов, например, появления полос прокрутки.
Теперь опишем содержимое скрипта. Его текст условно разбит на секции:
- константы;
- состояние системы;
- инициализация;
- обработчики событий;
- вспомогательные функции.
Константы содержат определения f и L:
// Расстояние от камеры до экрана по умолчанию.
const DEFAULT_FOCUS = 0.75;
// Длина калейдоскопа
// (расстояние от экрана до пластинки, длина зеркальной призмы).
const DEFAULT_LENGTH = 5.0;
а также тексты шейдеров. Фрагментный шейдер почти полностью дан выше, а вот вершинный шейдер приведём здесь. Он очень простой, и ничего не делает, поскольку мы будем отображать на экран квадрат [-1, 1]×[-1, 1]:
// Вершинный шейдер.
const VERTEX_SHADER_SOURCE = `#version 300 es
in vec4 a_position;
void main()
{
gl_Position = a_position;
}
`;
// Фрагментный шейдер.
const FRAGMENT_SHADER_SOURCE = `#version 300 es
precision highp float;
// и так далее ...
`;
Состояние системы пока задаётся лишь положением центра круга. Я также сделал переменными длину зеркал и расстояние до камеры:
// Расстояние от камеры до экрана.
let curFocus = DEFAULT_FOCUS;
// Длина зеркал.
let curLength = DEFAULT_LENGTH;
// Сдвиг центра круга.
let curXoffset = 0;
let curYoffset = 0;
Вспомогательных функций пока две: компиляция шейдера createShader, принимающая тип шейдера (вершинный или фрагментный) и исходный текст шейдера, и компоновка программы createProgram из скомпилированных вершинного и фрагментного шейдеров. В случае ошибок выводится окно с сообщением. Первоначальный код этих функций был потырен где-то в Интернете. Возможно, тут.
// Функция компиляции шейдера.
function createShader(type, source)
{
const shader = gl.createShader(type);
gl.shaderSource(shader, source);
gl.compileShader(shader);
const success = gl.getShaderParameter(shader, gl.COMPILE_STATUS);
if (success)
return shader;
alert(gl.getShaderInfoLog(shader));
gl.deleteShader(shader);
}
// Функция компоновки шейдеров в единую программу:
function createProgram(vertexShader, fragmentShader)
{
const program = gl.createProgram();
gl.attachShader(program, vertexShader);
gl.attachShader(program, fragmentShader);
gl.linkProgram(program);
const success = gl.getProgramParameter(program, gl.LINK_STATUS);
if (success)
return program;
alert(gl.getProgramInfoLog(program));
gl.deleteProgram(program);
}
Для простоты я не стал размещать инициализацию в отдельной функции.
Вначале выполним пару действий, помогающих избавиться от назойлевых полос прокрутки:
document.body.scrollTop = 0;
document.body.style.overflow = 'hidden';
Теперь получим объект канваса и создадим контекст WebGL2 (тот самый объект gl, который я уже невозбранно использовал выше во вспомогательных функциях):
const picto = document.getElementById("picto");
const gl = picto.getContext("webgl2");
if (!gl)
alert("Невозможно создать контекст WebGL2.");
Для работы нашей программы нет нужды в тесте глубины и блендинге, поэтому выключим их:
gl.disable(gl.DEPTH_TEST);
gl.disable(gl.BLEND);
Создадим нашу программу и выберем её в качестве текущей для объекта gl (чтобы шейдеры запускались при отрисовке примитива):
// Скомпилировать шейдеры и создать программу.
const vertexShader
= createShader(gl.VERTEX_SHADER, VERTEX_SHADER_SOURCE);
const fragmentShader
= createShader(gl.FRAGMENT_SHADER, FRAGMENT_SHADER_SOURCE);
const program
= createProgram(vertexShader, fragmentShader);
// Программа у нас будет одна,
// поэтому привяжем её один раз в инициализации.
gl.useProgram(program);
Получим дескрипторы параметров шейдеров (атрибута вершинного шейдера и юниформов фрагментного шейдера). Атрибут вершинного шейдера соответствует потоку входных данных, в нашем случае это — координаты вершин:
// Получить объект атрибута вершинного шейдера (входные данные).
const aPositionLocation
= gl.getAttribLocation(program, "a_position");
// Получить юниформы пиксельного шейдера.
const uHalfResolutionLocation
= gl.getUniformLocation(program, "u_half_resolution");
const uResolutionScaleLocation
= gl.getUniformLocation(program, "u_resolution_scale");
const uLengthToFocusRatioPlusOne
= gl.getUniformLocation(program, "u_length_to_focus_ratio_plus_one");
const uCenterOffset
= gl.getUniformLocation(program, "u_center_offset");
Теперь создадим буфер, в котором будут лежать координаты вершин квадрата. Отмечу, что поскольку мы подаём эти координаты на выход вершинного шейдера, то они заданы в «клиповом пространстве», что есть кубик [−1, 1]3. Поэтому квадрат с углами (−1, −1) ‒ (1, 1) точно соответствует экрану.
// Создать буфер на 4 вершины (на весь экран).
const positionBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, positionBuffer);
// Заполнить буфер данными (координаты вершин).
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array([
-1, -1,
+1, -1,
-1, +1,
+1, +1,
]), gl.STATIC_DRAW);
Связывание буферов в набор потоков данных для вершинного шейдера (каждый поток соответствует своему атрибуту) выполняется с помощью объекта массива вершин (vertex array object, VAO):
// Использовать наш буфер в качестве вершинного (источник данных для вершинного шейдера).
const vao = gl.createVertexArray();
gl.bindVertexArray(vao);
// Включить наш атрибут (переменную a_position).
gl.enableVertexAttribArray(aPositionLocation);
// Передать контексту информацию о формате буфера:
gl.vertexAttribPointer(
aPositionLocation,
2, // количество компонент вектора (по умолчанию дополняются y=0, z=0, w=1);
gl.FLOAT, // формат компоненты;
false, // нормализация вкл/выкл;
0, // шаг между элементами (0 == использовать размер);
0 // положение начала в буфере.
);
В конце инициализации назначаем обработчики событий (их код будет представлен далее) и рисуем первую картинку:
// Перерисовывать на каждом изменении размеров окна.
window.onresize = repaint;
// Реакция на нажатие клавиши.
document.addEventListener('keydown', keyDown, false);
// Первая картинка.
repaint();
Теперь код обработчика нажатия клавиш. Стрелки перемещают круг, кнопки w/s изменяют длину зеркал. Добавлять кнопки для изменения расстояния до камеры не стал, поскольку картинка зависит лишь от отношения L/f. В принципе, можно вообще положить f = 1 и немного упростить программу.
// Функция-обработчик нажатия клавиши
function keyDown(event)
{
const ARROW_STEP = 0.0625;
switch (event.key)
{
case 'ArrowLeft':
curXoffset -= ARROW_STEP;
break;
case 'ArrowRight':
curXoffset += ARROW_STEP;
break;
case 'ArrowUp':
curYoffset += ARROW_STEP;
break;
case 'ArrowDown':
curYoffset -= ARROW_STEP;
break;
case 'w': case 'W':
curLength *= 1.25;
break;
case 's': case 'S':
curLength /= 1.25;
break;
default:
// Ignore.
return;
}
repaint();
}
Наконец, функция repaint. Данная функция ничего не принимает и не возвращает. Так как она должна обрабатывать событие изменения размеров окна, то начнём с получения этих размеров и назначения их контексту:
// Разрешение окна.
const screenWidth = window.innerWidth;
const screenHeight = window.innerHeight;
// Нормировочный коэффициент.
const screenScale = 2.0 / Math.hypot(screenWidth, screenHeight);
// Канвас во всё окно.
gl.canvas.width = screenWidth;
gl.canvas.height = screenHeight;
gl.viewport(0, 0, screenWidth, screenHeight);
Я не сбрасываю содержимое буфера кадра (gl.clear), поскольку при каждой перерисовке и так заполняю его полностью заново попиксельно. Требуется задать значения всех юниформов, поскольку состояние системы могло измениться:
// Задать значения юниформам:
gl.uniform2f(uHalfResolutionLocation,
0.5 * screenWidth, 0.5 * screenHeight);
gl.uniform1f(uResolutionScaleLocation,
screenScale);
gl.uniform1f(uLengthToFocusRatioPlusOne,
curLength / curFocus + 1.0);
gl.uniform2f(uCenterOffset,
curXoffset, curYoffset);
После чего остаётся лишь запустить растеризацию и дождаться завершения рендеринга:
// Выполнить растеризацию (подать треугольники).
gl.drawArrays(
gl.TRIANGLE_STRIP, // тип примитива (полоса из треугольников);
0, // сдвиг начала примитива;
4 // количество вершин.
);
gl.finish();
Всё целиком можно наблюдать здесь.
Надеюсь, что продолжение последует. Ещё надеюсь, что мои рассуждения не содержат каких-то жёстких ошибок, а то получающаяся картинка внушает некоторые подозрения…
UPD: мои подозрения не были напрасны: я забыл строчку, добавляющую segment_length к accumulated_length. Теперь это исправлено. Старый вариант с ошибкой тут.
Удаление из файла повторяющихся строк с сохранением порядка
Программа принимает текст построчно через стандартный поток ввода и выводит результат в стандартный поток вывода. Строки выводятся только один раз (когда встречаются впервые). Эту задачу очень просто решить, используя стандартную библиотеку C++. Данное решение даже можно считать эффективным при условии наличия достаточного количества оперативной памяти.
#include <string> #include <unordered_set> #include <iostream> int main() { using namespace std; ios::sync_with_stdio(false); unordered_set<string> lines; for (string line; getline(cin, line);) if (lines.insert(line).second) cout << line << '\n'; return 0; }