Общее описание сайта и математическая теория здесь; рисование при помощи фоновых потоков выполнения обрисовано здесь.
Основной недостаток рисования фракталов с использованием фоновых потоков (и других средств, использующих центральный процессор) — это низкая скорость работы. Количество потоков выполнения не имеет смысла устанавливать большим, чем количество ядер процессора, а оно даже для самых современных компьютеров вряд ли превышает десяток. Поэтому естественно задуматься о применении для вычислений ресурсов графической платы, тем более что для веб-браузеров существует походящий инструментарий — WebGL.
Использование GPU для рисования фракталов упрощается за счет двух факторов:
- Цвет пикселей изображения, которое необходимо получить, определяется исключительно расположением пикселя. Это значит, что процесс рисования можно эффективно распараллелить без использования особых ухищрений. Поскольку в современных графических платах количество пиксельных конвейеров (то есть модулей для определения цвета пикселей) составляет порядка сотни, фрактал будет генерироваться значительно быстрее, чем при использовании CPU.
- Для вычисления цвета не используются экстраординарные математические понятия; весь процесс сводится к преобразованию пар действительных чисел при помощи базовых функций (exp, log, геометрические и обратные геометрические).
WebGL
WebGL — API для рисования в веб-браузере в 2D и 3D с использованием графического ускорения. Для отображения используется элемент HTML5 <canvas>. Управляющий код WebGL, как и для других браузерных API, пишется на языке программирования JavaScript. По своей сути WebGL — несколько урезанная версия OpenGL ES 2.0, версии библиотеки OpenGL для мобильных устройств, например, смартфонов и планшетов. Технология поддерживается большинством современных браузеров (и даже IE, начиная с версии 11), однако из-за различий в имплементации API на одном и том же компьютере одинаковый код WebGL может приводить к различным изображениям (или, в наихудшем случае, не работать вовсе).
Основы WebGL можно почерпнуть, например, здесь или здесь. Для упрощения работы с WebGL существует много сторонних библиотек, например, Three.js. Для создания фракталов, впрочем, вполне достаточно «голого» API — не нужно рисовать сложных трехмерных тел, использовать анимацию и другие продвинутые возможности.
Интерфейс WebGL интересен в контексте программной инженерии. В ранних версиях OpenGL ES (и обычного OpenGL) для рисования использовались функции, вызываемые в основном коде программы (так называемые fixed functions). В WebGL во главу угла поставлен принцип разделения ответственности: весь код, который выполняется на графическом ускорителе, описывается с помощью шейдеров — программ, написанных на процедурном языке предметной области GLSL (GL scripting language), напоминающем по своему синтаксису C. В WebGL поддерживаются два вида шейдеров:
- вершинные шейдеры (vertex shader), с помощью которых определяется местоположение вершин рисующихся объектов;
- фрагментные шейдеры (fragment shader), которые определяют цвета граней объектов.
Рисование осуществляется за счет WebGL-программ, каждая из которых состоит из одного вершинного и одного фрагментного шейдера. Программы компилируются в машинный код, который выполняется на GPU.
Для взаимодействия между WebGL-программой и основным кодом приложения на JavaScript используются два особых типа переменных GLSL — атрибуты (attribute) и однородные переменные (uniform).
- Атрибуты — последовательности вещественных и ли целых чисел, подающихся на вход программы и доступные в вершинном шейдере. Чаще всего с помощью атрибутов определяются координаты вершин рисующихся объектов.
- Однородные переменные используются в вершинном и / или фрагментном шейдере, не изменяясь во время рисования. Помимо вещественных и целых чисел, в роли постоянных могут выступать, например, текстуры. Однородные переменные могут соответствовать произвольным параметрам, влияющим на рисовку (например, параметрам освещения).
Метод взаимодействия между вершинным и фрагментным шейдером определяется типом рисуемых базовых объектов (примитивов). Основные примитивы — точки (для рисования систем частиц), линии (для рисования каркасов) и треугольники (для рисования заполненных фигур и тел). Для взаимодействия шейдеров используется третий вид переменных GLSL — интерполируемые (varying). Эти переменные определяются в вершинном шейдере, интерполируются и подаются на вход фрагментного шейдера. Код вершинного шейдера выполняется заданное программистом количество раз; каждому выполнению соответствует вершина рисуемого объекта и свой набор атрибутов. При рисовании треугольниками каждые три выполнения вершинного шейдера определят грань объекта; пиксели изображения, которые соответствуют этой грани, закрашиваются путем выполнения фрагментного шейдера. Значения varying-переменных линейно интерполируются исходя из трех значений для вершин грани, вычисленных в процессе работы вершинного шейдера.
В качестве выходных данных вершинных шейдеров в WebGL используются трехмерные однородные координаты. Центр системы координат расположен посредине элемента <canvas>; оси x и y направлены вправо и вверх, соответственно. Диапазон отображаемых значений для осей x и y равен [-1, 1] независимо от отношения сторон HTML-элемента. Ось z направлена на наблюдателя; ее назначение — определять, какие точки, рисуемые фрагментными шейдерами, видимы, и какие скрыты другими, более близкими гранями.
Рисование фракталов
Для того, чтобы отобразить фрактал, достаточно нарисовать прямоугольник, занимающий всю видимую плоскость xOy, или эквивалентные два треугольника. В качестве атрибутов, таким образом, достаточно использовать координаты xy вершин этого прямоугольника. На основе этих координат и границ области комплексной плоскости, для которой рисуется фрактал, можно легко вычислить единственную интерполируемую переменную — комплексное число z, для которого вычисляется значение функции P(z, f) в фрагментном шейдере.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Координаты (x,y) вершины в системе координат WebGL attribute vec2 a_position; // Комплексное число, для которого проводятся вычисления // во фрагментном шейдере varying vec2 v_coordinates; // Сдвиг и масштабирование для преобразования // из системы координат WebGL в координаты комплексной плоскости uniform vec4 u_coordOffsetScale; void main() { v_coordinates = u_coordOffsetScale.xy + u_coordOffsetScale.zw * v_position; gl_Position = vec4(a_position, 0, 1); } |
Поскольку возможности языка GLSL достаточно ограничены, возникает проблема передачи во фрагментный шейдер функции f, для которой строится фрактал. В отличие от фоновых потоков выполнения, передача функции в виде обратной польской записи чересчур громоздка; легче на основе ОПЗ генерировать кусок шейдера, соответствующий вычислению функции. При этом потребуется определить используемые функции комплексного переменного vec2 c_sinh(vec2 a), vec2 c_cosh(vec2 a), …; это легко делается при помощи стандартных арифметических и тригонометрических функций GLSL.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Параметры функции #define MAX_PARAMS 20 uniform vec2 u_params[MAX_PARAMS]; vec2 c_plus(vec2 a, vec2 b) { return a + b; } vec2 c_mul(vec2 a, vec2 b) { return vec2(a[0] * b[0] - a[1] * b[1], a[0] * b[1] + a[1] * b[0]); } // Другие используемые функции комплексного переменного vec2 f(vec2 z) { // f(z) = z*z + c; код вычисления генерируется программно vec2 stack[2]; stack[0] = z; stack[1] = z; stack[0] = c_mul(stack[0], stack[1]); stack[1] = u_params[0]; stack[0] = c_plus(stack[0], stack[1]); return stack[0]; } |
Зная функцию f, можно вычислить значение P(z, f). Палитру, используемую для визуализации результатов, можно передавать в виде текстуры.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Максимальное количество итераций N. // Определено как макрос - это необходимо для использования // как верхней границы в цикле. #define MAX_ITERATIONS 60 // Комплексное число, для которого проводятся вычисления varying vec2 v_coordinates; // Максимальное расстояние D. uniform float u_distance; // Палитра, используемая для рисования. // Имеет размер 128 x 1. uniform sampler2D u_palette; const float INV_PALETTE_WIDTH = 1.0 / 128.0; void main() { vec2 z = v_coordinates; bool isSet = false; // true, когда значение P(z, f) уже определено int nIterations = 0; // P(z, f) for (int i = 1; i <= MAX_ITERATIONS; i++) { if (!isSet) z = f(z); if ((length(z) > u_distance) && !isSet) { nIterations = i; isSet = true; } } float k = float(nIterations) * INV_PALETTE_WIDTH; gl_FragColor = texture2D(u_palette, vec2(k + 0.5 * INV_PALETTE_WIDTH, 0.5)); } |
Модификации
В некоторых случаях при рисовании фрактала возникают «дырки» — пиксели, в которых из-за потери точности вычисленное значение функции P(z, f) отличается от истинного. Возникновение «дырок» носит достаточно случайный характер: например, на моем ноутбуке они появляются в Windows 7 в Firefox и Google Chrome, а в Linux их нет ни в Firefox, ни в Chromium.
Для устранения этих пикселей можно использовать сглаживание: если значение функции P(z, f) резко отличается от значений для соседних восьми пикселей, вместо значения используется усредненная величина функции по соседям.
Для сглаживания необходимо знать значения функции P(z, f) для всех соседей каждого пикселя. Если вычислять эти величины в фрагментном шейдере, его сложность возрастает в 9 раз; при этом все дополнительные вычисления избыточны. К счастью, в WebGL существует инструмент, позволяющий избавиться от избыточности — рисование в текстуру. При использовании этой техники рисование разбивается на два этапа:
- Для каждого пикселя изображения вычисляется значение
P(z, f); оно сохраняется в текстуру (например, в альфа-канал). Поскольку сохраняемая величина — целое число, не превышающее 255, при записи не теряется точность. - Полученная текстура используется как uniform-переменная в фрагментном шейдере, который выполняет сглаживание и вывод изображения на экран.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// Текстура, в которую записываются значения P(z, f) uniform sampler2D u_texture; // Относительный размер пикселя области рисования; // вычисляется как (1 / длина области, 1 / высота) uniform vec2 u_pixelSize; float smoothIfOutlier(vec2 pt) { float val = texture2D(u_texture, pt).a; if (abs(val - float(MAX_ITERATIONS) / 255.0) > 0.001) { // Как правило, "дырки" соответствуют // максимально возможному значению P(z, f). // Все остальные значения можно не сглаживать. return val; } float sum = 0.0; // сумма P(z, f) для соседних точек float nVal = 0.0; // значение P(z, f) для соседней точки int nDiff = 0; // число резко отличающихся соседей vec2 neighborPos; // расположение соседнего пикселя в текстуре neighborPos = pt + vec2(-1.0, -1.0) * u_pixelSize; nVal = texture2D(u_texture, neighborPos).a; sum += nVal; if (abs(nVal - val) > diffThreshold) nDiff++; neighborPos = pt + vec2(-1.0, 0.0) * u_pixelSize; nVal = texture2D(u_texture, neighborPos).a; sum += nVal; if (abs(nVal - val) > diffThreshold) nDiff++; // Вычисления для остальных шести соседей // Точка считается «дыркой», если от нее отличаются // четыре соседних значения (т.е. половина соседей) return (nDiff > 4) ? (sum * 0.125) : val; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// В общем случае для рисования в несколько этапов // можно использовать разные программы. // Для фракталов код вершинного шейдера аналогичен // для обоих этапов, так что можно ввести дополнительную // однородную переменную и обойтись одной программой. uniform int u_phase; void main() { if (u_phase == 0) { int nIterations = // вычисляется, как и в предыдущем случае // Записать нормализованное значение в альфа-канал gl_FragColor = vec4(0.0, 0.0, 0.0, float(nIterations) / 255.0); } else { float k = 255.0 * INV_PALETTE_WIDTH; #ifdef SMOOTHING k *= smoothIfOutlier(v_position); #else // Если сглаживание выключено (например, для отладки), // значение P(z, f) берется непосредственно из текстуры k *= texture2D(u_texture, v_position).a; #endif gl_FragColor = texture2D(u_palette, vec2(k + 0.5 * INV_PALETTE_WIDTH, 0.5)); } } |
Помимо сглаживания, текстуру можно использовать для перебрасывания значений функции P из графической памяти в оперативную (для этой цели в WebGL есть метод readPixels). Эти значения передаются на сервер для создания иконки фрактала.