Фракталы — использование WebGL

Общее описание сайта и математическая теория здесь; рисование при помощи фоновых потоков выполнения обрисовано здесь.

Основной недостаток рисования фракталов с использованием фоновых потоков (и других средств, использующих центральный процессор) — это низкая скорость работы. Количество потоков выполнения не имеет смысла устанавливать большим, чем количество ядер процессора, а оно даже для самых современных компьютеров вряд ли превышает десяток. Поэтому естественно задуматься о применении для вычислений ресурсов графической платы, тем более что для веб-браузеров существует походящий инструментарий — 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-программы
Схема WebGL-программы

Для взаимодействия между WebGL-программой и основным кодом приложения на JavaScript используются два особых типа переменных GLSL — атрибуты (attribute) и однородные переменные (uniform).

  • Атрибуты — последовательности вещественных и ли целых чисел, подающихся на вход программы и доступные в вершинном шейдере. Чаще всего с помощью атрибутов определяются координаты вершин рисующихся объектов.
  • Однородные переменные используются в вершинном и / или фрагментном шейдере, не изменяясь во время рисования. Помимо вещественных и целых чисел, в роли постоянных могут выступать, например, текстуры. Однородные переменные могут соответствовать произвольным параметрам, влияющим на рисовку (например, параметрам освещения).

Метод взаимодействия между вершинным и фрагментным шейдером определяется типом рисуемых базовых объектов (примитивов). Основные примитивы — точки (для рисования систем частиц), линии (для рисования каркасов) и треугольники (для рисования заполненных фигур и тел). Для взаимодействия шейдеров используется третий вид переменных GLSL — интерполируемые (varying). Эти переменные определяются в вершинном шейдере, интерполируются и подаются на вход фрагментного шейдера. Код вершинного шейдера выполняется заданное программистом количество раз; каждому выполнению соответствует вершина рисуемого объекта и свой набор атрибутов. При рисовании треугольниками каждые три выполнения вершинного шейдера определят грань объекта; пиксели изображения, которые соответствуют этой грани, закрашиваются путем выполнения фрагментного шейдера. Значения varying-переменных линейно интерполируются исходя из трех значений для вершин грани, вычисленных в процессе работы вершинного шейдера.

Система координат WebGL
Система координат WebGL

В качестве выходных данных вершинных шейдеров в WebGL используются трехмерные однородные координаты. Центр системы координат расположен посредине элемента <canvas>; оси x и y направлены вправо и вверх, соответственно. Диапазон отображаемых значений для осей x и y равен [-1, 1] независимо от отношения сторон HTML-элемента. Ось z направлена на наблюдателя; ее назначение — определять, какие точки, рисуемые фрагментными шейдерами, видимы, и какие скрыты другими, более близкими гранями.

Рисование фракталов

Для того, чтобы отобразить фрактал, достаточно нарисовать прямоугольник, занимающий всю видимую плоскость xOy, или эквивалентные два треугольника. В качестве атрибутов, таким образом, достаточно использовать координаты xy вершин этого прямоугольника. На основе этих координат и границ области комплексной плоскости, для которой рисуется фрактал, можно легко вычислить единственную интерполируемую переменную — комплексное число z, для которого вычисляется значение функции P(z, f) в фрагментном шейдере.

Поскольку возможности языка GLSL достаточно ограничены, возникает проблема передачи во фрагментный шейдер функции f, для которой строится фрактал. В отличие от фоновых потоков выполнения, передача функции в виде обратной польской записи чересчур громоздка; легче на основе ОПЗ генерировать кусок шейдера, соответствующий вычислению функции. При этом потребуется определить используемые функции комплексного переменного vec2 c_sinh(vec2 a), vec2 c_cosh(vec2 a), …; это легко делается при помощи стандартных арифметических и тригонометрических функций GLSL.

Зная функцию f, можно вычислить значение P(z, f). Палитру, используемую для визуализации результатов, можно передавать в виде текстуры.

Модификации

В некоторых случаях при рисовании фрактала возникают «дырки» — пиксели, в которых из-за потери точности вычисленное значение функции P(z, f) отличается от истинного. Возникновение «дырок» носит достаточно случайный характер: например, на моем ноутбуке они появляются в Windows 7 в Firefox и Google Chrome, а в Linux их нет ни в Firefox, ни в Chromium.

«Дырки» при рисовании в браузере в Google Chrome
«Дырки» при рисовании (хорошо видны на полном изображении).
Тот же фрактал, нарисованный с помощью фоновых потоков
Тот же фрактал, нарисованный с помощью фоновых потоков

Для устранения этих пикселей можно использовать сглаживание: если значение функции P(z, f) резко отличается от значений для соседних восьми пикселей, вместо значения используется усредненная величина функции по соседям.

Для сглаживания необходимо знать значения функции P(z, f) для всех соседей каждого пикселя. Если вычислять эти величины в фрагментном шейдере, его сложность возрастает в 9 раз; при этом все дополнительные вычисления избыточны. К счастью, в WebGL существует инструмент, позволяющий избавиться от избыточности — рисование в текстуру. При использовании этой техники рисование разбивается на два этапа:

  1. Для каждого пикселя изображения вычисляется значение P(z, f); оно сохраняется в текстуру (например, в альфа-канал). Поскольку сохраняемая величина — целое число, не превышающее 255, при записи не теряется точность.
  2. Полученная текстура используется как uniform-переменная в фрагментном шейдере, который выполняет сглаживание и вывод изображения на экран.

Помимо сглаживания, текстуру можно использовать для перебрасывания значений функции P из графической памяти в оперативную (для этой цели в WebGL есть метод readPixels). Эти значения передаются на сервер для создания иконки фрактала.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *