Pull to refresh

Интро Newton Protocol: что можно уместить в 4 килобайта

Reading time 8 min
Views 21K
Original author: Jerry Ylilammi
image

Недавно я участвовал соревнованиях демосцены Revision 2019 в категории «PC 4k intro», и моё интро выиграло первое место. Я занимался кодингом и графикой, а dixan сочинял музыку. Основное правило соревнования — необходимо создать исполняемый файл или веб-сайт, имеющий размер всего 4096 байта. Это означает, что всё приходится генерировать с помощью математики и алгоритмов; никаким другим способом не получится ужать изображения, видео и аудио в такой крошечный объём памяти. В этой статье я расскажу о конвейере рендеринга своего интро Newton Protocol. Ниже можно посмотреть готовый результат, или нажать сюда, чтобы посмотреть как оно выглядело вживую на Revision, или зайти на pouet, чтобы прокомментировать и скачать участвовавшее в конкурсе интро. О работах конкурентов и об исправлениях можно прочитать здесь.


Очень популярной в дисциплине 4k intro является техника Ray marching distance fields, потому что она позволяет задавать сложные формы всего в нескольких строках кода. Однако недостатком такого подхода является скорость выполнения. Для рендеринга сцены нужно найти точку пересечения лучей со сценой, сначала определить, что вы видите, например, луч из камеры, а затем последующие лучи от объекта к источникам света для вычисления освещения. При работе с ray marching эти пересечения нельзя найти за один шаг, нужно делать много мелких шагов вдоль луча и оценивать в каждой точке все объекты. С другой стороны, при использовании трассировки лучей (ray tracing) можно найти точное пересечение, проверив каждый объект только раз, но при этом очень ограничен набор фигур, которые можно использовать: для вычисления пересечения с лучом нужно иметь формулу для каждого типа.

В этом интро я хотел симулировать очень точное освещение. Так как для этого необходимо было отражать в сцене миллионы лучей, для достижения такого эффекта логичным выбором казалась трассировка лучей. Я ограничился единственной фигурой — сферой, потому что пересечение луча и сферы вычисляется довольно просто. Даже стены в интро на самом деле являются очень большими сферами. Кроме того, это упростило и симуляцию физики; достаточно было учитывать только коллизии между сферами.

Чтобы проиллюстрировать объём кода, помещающийся в 4096 байт, ниже я представил полный исходный код готового интро. Все части, за исключением HTML в конце, закодированы как PNG-изображение, чтобы сжать их в меньший объём. Без этого сжатия код занимал бы объём почти 8900 байт. Часть под названием Synth — это урезанная версия SoundBox. Для упаковки кода в этот минимизированный формат я использовал Google Closure Compiler и Shader Minifier. В конце почти всё сжато в PNG с помощью JsExe. Полный конвейер компиляции можно посмотреть в исходном коде моего предыдущего 4k intro Core Critical, потому что он полностью совпадает с представленным здесь.


Музыка и синтезатор полностью реализованы на Javascript. Часть на WebGL разделена на две части (выделенные в коде зелёным цветом); она настраивает конвейер рендерига. Элементы физики и трассировщика лучей являются шейдерами GLSL. Остальная часть кода закодирована в PNG-изображение, а HTML добавлен в конец получившегося изображения без изменений. Браузер игнорирует данные изображения и выполняет только HTML-код, который, в свою очередь, декодирует PNG обратно в javascript и выполняет его.

Конвейер рендеринга


На рисунке ниже показан конвейер рендеринга. Он состоит из двух частей. Первая часть конвейера — это симулятор физики. В сцене интро содержатся 50 сфер, сталкивающиеся друг с другом внутри комнаты. Сама комната составлена из шести сфер, некоторые из которых меньше других для создания более искривлённых стен. Два вертикальных источника освещения в углах тоже являются сферами, то есть всего в сцене 58 сфер. Вторая часть конвейера — это трассировщик лучей, который рендерит сцену. На представленной ниже схеме показан рендеринг одного кадра в момент времени t. Симуляция физики берёт предыдущий кадр (t-1) и симулирует текущее состояние. Трассировщик лучей берёт текущие позиции и позиции предыдущего кадра (для канала скорости) и рендерит сцену. Затем постобработка комбинирует предыдущие 5 кадров и текущий кадр для снижения искажений и шумов, после чего создаёт готовый результат.


Рендеринг кадра в момент времени t.

Физическая часть довольно проста, в Интернете можно найти множество туториалов по созданию примитивной симуляции для сфер. Позиция, радиус, скорость и масса хранятся в двух текстурах разрешением 1 x 58. Я воспользовался функционалом Webgl 2, позволяющим выполнять рендеринг в несколько render targets, поэтому данные двух текстур записываются одновременно. Этот же функционал используется трассировщиком лучей для создания трёх текстур. Webgl не предоставляет никакого доступа к API трассировки лучей NVidia RTX или DirectX Raytracing (DXR), поэтому всё делается с нуля.

Трассировщик лучей


Сама по себе трассировка лучей — достаточно примитивная техника. Мы выпускаем в сцену луч, он отражается 4 раза, и если попадает в источник света, то цвет отражений накапливается; в противном случае мы получаем чёрный цвет. В 4096 байтах (в которые включены музыка, синтезатор, физика и рендеринг) нет места для создания сложных ускоряющих структур трассировки лучей. Поэтому мы используем метод грубого перебора, то есть проверяем все 57 сфер (передняя стена исключается) для каждого луча, не делая никаких оптимизаций для исключения части сфер. Это значит, что для обеспечения 60 кадров в секунду в разрешении 1080p можно испустить всего 2–6 лучей, или сэмплов на пиксель. Этого и близко недостаточно для создания плавного освещения.


1 сэмпл на пиксель.


6 сэмплов на пиксель.

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

У соседних пикселей должно быть очень схожее освещение, так почему бы не использовать их при вычислении освещения единичного пикселя? Мы не хотим размывать текстуры, только освещение, поэтому нужно рендерить их в отдельных каналах. Также мы не хотим размывать объекты, поэтому нужно учитывать идентификаторы объектов, чтобы знать, какие пиксели можно спокойно размывать. Так как у нас есть отражающие свет объекты и нам нужны чёткие отражения, то недостаточно просто узнать ID первого объекта, с которым столкнётся луч. Я использовал особый случай для чистых отражающих материалов, чтобы также включить в канал идентификаторов объектов ID первых и вторых объектов, видимых в отражениях. В этом случае размытие может сглаживать освещение в объектах в отражениях, в то же время сохраняя границы объектов.


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


Здесь в красном канале содержится ID первого объекта, в зелёном — второго, а в синем — третьего. На практике все они кодируются в одно значение формата float, в котором целая часть хранит идентификаторы объектов, а дробная обозначает шероховатость (roughness): 332211.RR.

Так как в сцене есть объекты с разной шероховатостью (некоторые сферы шероховаты, на других освещение рассеивается, в третьих присутствует зеркальное отражение), я храню шероховатость для управления радиусом размытия. В сцене нет мелких деталей, поэтому я использовал для размытия большое ядро размером 50 x 50 с весами в виде обратных квадратов. Оно не учитывает мировое пространство (это можно было бы реализовать, чтобы получить более точные результаты), потому что на поверхностях расположенных под углом в некоторых направлениях оно размывает бОльшую площадь. Такое размытие создаёт достаточно гладкое изображение, но всё равно хорошо заметны артефакты, особенно в движении.


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

Когда объекты находятся в сцене и снимающая сцену камера медленно движется, освещение в каждом кадре должно оставаться постоянным. Поэтому мы можем выполнять размытие не только в координатах XY экрана; мы можем размывать и во времени. Если предположить, что освещение не слишком меняется за 100 мс, то можно усреднить его для 6 кадров. Но за это временное окно объекты и камера всё равно пройдут какое-то расстояние, поэтому простое вычисление среднего для 6 кадров создаст очень размытое изображение. Однако мы знаем, где находились все объекты и камера в предыдущем карте, поэтому можем вычислить векторы скоростей в экранном пространстве. Это называется временным репроецированием. Если у меня есть пиксель в момент t, то я могу взять скорость этого пикселя и вычислить, где он был в момент t-1, а затем вычислить, где пиксель в моменте t-1 находится в момент t-2, и так далее, назад на 5 кадров. В отличие от размытия в экранном пространстве, я использовал здесь для каждого кадра одинаковый вес, т.е. просто усреднял цвет между всеми кадрами для временного «размытия».


Канал скоростей пикселей, сообщающий, где находился пиксель в последнем кадре на основании движения объекта и камеры.


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

Разумеется, пиксель мог быть и не видим в предыдущем кадре; он мог быть скрыт другим объектом или находиться вне области видимости камеры. В таких случаях мы не можем использовать предыдущую информацию. Эта проверка выполняется отдельно для каждого кадра, поэтому мы получаем от 1 до 6 сэмплов или кадров на пиксель, и используем те из них, которые можно. На рисунке ниже видно, что для медленных объектов это не очень серьёзная проблема.


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


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

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


Готовое изображение.

Артефакты затухания всё равно заметны, потому что я усреднял несколько сэмплов на пиксель, хотя канал идентификатора объекта и скорости брал для первого пересечения. Можно попробовать это исправить и получить сглаживание в отражениях, отбрасывая сэмплы, если они не совпадают с первым, или хотя бы если первое столкновение не совпадает по порядку. На практике же следы почти невидимы, поэтому я не стал заморачиваться их устранением. Границы объектов тоже искажены, потому что каналы скорости и идентификаторов объектов невозможно сгладить. Я рассматривал возможность рендеринга всего изображения в разрешении 2160p с дальнейшим уменьшением масштаба до 1080p, но моя NVidia GTX 980ti не способна на обработку таких разрешений с частотой 60fps, поэтому решил отказаться от этой идеи.

В целом я очень доволен тем, каким получилось интро. Мне удалось втиснуть в него всё, что я задумывал, и несмотря на небольшие баги, конечный результат получился очень качественным. В будущем можно попробовать устранить баги и улучшить сглаживание. Также стоит поэкспериментировать с такими возможностями, как прозрачность, motion blur, различные фигуры и трансформации объектов.

Tags:
Hubs:
If this publication inspired you and you want to support the author, do not hesitate to click on the button
+89
Comments 32
Comments Comments 32

Articles