Когда я учился на CS в WUT, мне недавно в рамках моего курса графики было поручено создать клиппер, заполнитель и световой симулятор. Требования были следующие:

  • Пользователь может создавать и преобразовывать многоугольники. Внутри многоугольников отображается контент.
  • Пользователь может вырезать два многоугольника с помощью алгоритма Сазерленда-Ходжмана.
  • Фоновая текстура, карта высот и карта нормалей могут быть установлены пользователем.
  • Цвет света выбирается пользователем.
  • Источник света либо постоянен для каждой точки изображения, либо кружит где-то «над» экраном.
  • Расчет индивидуальных цветов пикселей предполагается производить в нашем коде (без использования библиотеки для штриховки).

Язык программирования и технология, используемые для разработки этого приложения, не были выбраны заранее, поэтому я решил использовать Javascript, поскольку это был мой предпочтительный язык, и на нем я выполнял предыдущие задачи из этого курса.

Вот результат, если вы хотите поиграть с ним: https://gelio.github.io/polygon-clipper/

Назначение текстур

Давайте сначала узнаем, для чего нужны изображения и цвета, указанные в требованиях.

Фоновая текстура

Это довольно просто. Он содержит базовое изображение, которое будет отображаться.

Карта нормалей

Карта нормалей определяет все выпуклости и форму текстуры фона. Каждый пиксель - это нормальный вектор (вектор, перпендикулярный поверхности).

Применение карты нормалей к изображениям придает им трехмерный вид.

Карта высот

Карта высот похожа на карту нормалей, но на ее основе мы можем немного исказить векторы нормалей.

Карта высот представлена ​​в оттенках серого, потому что все компоненты цвета пикселя одинаковы. Он определяет высоту этой точки на изображении. Чем ярче точка, тем она выше по сравнению с другими близлежащими точками.

Положение источника света

Одним из требований этой задачи было то, что источник света должен был кружить «над» экраном (по положительной оси Z). Точное уравнение для положения источника света не было дано, поэтому я придумал следующее:

Альфа- и бета-версиями можно свободно управлять. Чем выше альфа, тем выше источник света. Бета заставляет источник света двигаться горизонтально по кругу.

Изменяя альфа и бета в каждом кадре, я получал трехмерную спираль. Альфа была зажата между 20 ° и 70 °, тогда как бета сделала полный круг.

Заполнение только внутренней части полигонов

Я применил алгоритм рендеринга строки развертки с использованием таблицы Active Edge и сортировки вершин каждого многоугольника, чтобы определить, какие позиции следует заполнить для каждой строки развертки.

Более подробную информацию об этом алгоритме вы можете найти здесь.

Рендеринг в потоке пользовательского интерфейса

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

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

Я получал около 5 кадров в секунду при перетаскивании вершины многоугольника, что приводило к новому рендерингу при каждом движении мыши. Имейте в виду, что это просто копирование цветов с одного ImageData на другой.

Добавление WebWorker

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

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

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

Потребление памяти

Перед реализацией алгоритма финального заполнения я посмотрел на потребление памяти моим приложением.

Каждому кадру я выделил новый ImageData (800x600), который должен заполнить рабочий. Затем он был передан обратно в основной поток для отображения.

Примерно каждые 9 кадров включается сборщик мусора, очищающий неиспользуемые буферы. Я подумал: зачем каждый раз выделять новую память, если я могу использовать два буфера и просто менять их местами (по сути, двойная буферизация)?

К моему большому удивлению, это оказалось медленнее, чем каждый раз выделять новую память. Причина заключалась в очистке предыдущего растрового изображения перед новым кадром, что было сделано перед заполнением его новыми данными.

Моя следующая идея заключалась в том, чтобы иметь двух рабочих: уборщика и разливщика. Они будут работать с 3 буферами. После того, как рамка была отображена на холсте, она была отправлена ​​клининговому работнику. Когда он возвращается с чистым растровым изображением, он был отправлен исполнителю заполнения, который заполняет его и отправляет обратно в основной поток для отображения.

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

Я решил отказаться от этого подхода и остановиться на более простом наполнителе worker.

Еще одна идея улучшения

Одна из идей повышения производительности - разделить заполняющие полигоны между несколькими рабочими, при этом номер рабочего i отвечает за y % n == i строку развертки, где y - координата y строки развертки. Использование этого с обычным ImageData, вероятно, не приведет к ожидаемому ускорению, так как в конечном итоге результаты каждого рабочего процесса должны быть объединены в одно окончательное растровое изображение.

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

Имейте в виду, что SharedArrayBuffer не так широко поддерживается, как обычные ArrayBuffer и WebWorkers.

Формула окончательного цвета пикселя

Чтобы этот пост не был длиннее, чем необходимо, вот Gist, содержащий функции, вычисляющие окончательный цвет пикселя. Он основан на ламбертовской отражательной способности. Более подробная информация доступна в этом замечательном учебнике OpenGL по затенению и картированию нормалей.

Вывод

Создание таких нестандартных проектов, как этот, дает больше возможностей учиться и придумывать собственные решения проблем. Вот мои ключевые выводы:

  • выполнение вычислений в WebWorker намного быстрее, чем в потоке пользовательского интерфейса
  • передача ArrayBuffer намного эффективнее, чем его копирование
  • кажущееся более эффективным решение может не закончиться одним - важно проверять идеи

Я предоставлю ссылку на мой репозиторий GitHub с кодом, как только сдам проект.