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

Автор оригинала: 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, различные фигуры и трансформации объектов.

Поддержать автора
Поделиться публикацией

Комментарии 29

    +22

    Подобные статьи сильно бьют по моей самооценке. Может для того они и кодят и побеждают чтобы меня унизить? :)

      +31
      Унизить они пытаются друг друга, вы просто под горячую руку попались.
      0
      Всегда впечатляло как эти демосценки при малом весе так загружали систему.
      Круто.
        0
        Сложность вычисления не зависит от размера программы.

        Есть много математических вычислений длинной в 10-20 символов, которые нагрузят процессор до 100% и используют всю доступную оперативную память
          0
          Я это знаю.
          Я это осознаю.
          Но всё равно это вызывает некий диссонанс.
          Подобное было и у Winamp.
          Да я ради этих «вау» музыку слушал.
          image
            0
            Мне лично нетерпится увидить как 256-кубитные квантовые чипы будут за секунды вычислять проблемы, которые за гранью возможностей всех существующих на данный момент супер компьютеров.

            Только представьте, добавление 1-го кубита, увеличивает производительность квантового чипа экспоненциально:

            21 (кубит) = 2 операций / такт
            22 (кубита) = 4 операций / такт
            23 (кубита) = 8 операций / такт
            24 (кубита) = 16 операций / такт

            2128 (кубит) = 340,282,366,920,938,463,463,374,607,431,768,211,456 операций / такт
              +9
              Я уверен, что Windows 12345 будет не высоте, и не даст вам заметить разницу. :)
        0
        Если в сцену добавить пару гигабайт фотореалистичных текстур, загрузка ещё возрастёт.
          +2
          Просто потрясающе. Вспоминаются демки образца 98-го года! Спасибо огромное.
            0
            Кхм, ещё пока ничего круче Chaos Theory не видел. У них кстати открыт код github.com/ConspiracyHu/2012SourcePack
              0
              Но ведь это и не 4кб демо, а 64
              Вот тоже хорошая работа, не такая эффектная, но как по мне — приятнее (на вкус и цвет, конечно)
              www.youtube.com/watch?v=HpAMtE4i8zg
              0
              От всей души поздравляю с победой!
                +2
                Считаю 4k-intro самой интересной дисциплиной, потому что в 1К ничего вызывающего вау-эффект не уместится, а в 64К — уже можно напихать кучу всего, при этом не отвоёвывать каждый байт.
                Но пока что фаворитом считаю Elevated — огромная сцена, построенная всего несколькими шейдерами и упакованная в 4 килобайта. Очень удачная комбинация простой идеи, отличной реализации и потрясающего визуального эффекта.
                  +1
                  У меня взрыв мозга
                    +3
                    Самое дикое что некоторым нынче и 4 гигабайт для такого будет мало
                      0

                      4кб это всего лишь размер исполняемого файла (а к нему еще интерпретатор в виде браузера на сотни мегабайт, но это опустим).
                      Демка выжрала 1 гигабайт видеопамяти, нагрузила GPU на 100% так, что интерфейс стал подлагивать.
                      Пришлось поскорее закрыть, так и не дождался картинки.


                      Так что иногда пусть все ж 4 гига кушает, но работает.

                        0
                        Браузер с яваскриптом ещё фигня, по сравнению с компилятором GLSL в драйвере видеокарты. Тем более что создать openGL окошко можно и без браузера через winapi в несколько сотен байт.
                        Проблема современного софта в том, что даже если будет весить 4Гига, быстрее он этого работать не станет.
                          0
                          И вот к нам уже идёт аппаратный рейтрейсинг.
                        0

                        Объясните пожалуйста, как можно посмотреть это вживую в браузере?


                        На странице работы нет ссылки посмотреть, есть только скачать. Локально не запускается из-за ограничений безопасности. Залил на хост:
                        https://ucarecdn.com/160c5fb6-23c4-4422-bd7a-c2d456e1a890/hbc00017newton_protocol.html


                        Все равно ни в одном браузере не запускается, везде разные ошибки после небольшой прогрузки.

                          0
                          У меня hbc0016 (Core Critical) запускается в Firefox c локального файла.
                          hbc0017 не работает
                            0
                            Там же есть инструкция в архиве. Делаем ярлык на хром с параметрами --disable-web-security -user-data-dir=«C:/Temp» --autoplay-policy=no-user-gesture-required
                            Запускаем этот ярлык и тащим хэтэмээлку в окно с рабочего стола.
                            P.S. При запуске на встройняшке интел, падает драйвер.
                            При первом запуске хром почему то потёр дополнительные параметры ярлыка.
                            +1
                            Это просто фантастика!
                              0
                              Безумству храбрых поём мы песнь…
                                0
                                Классная статья, даже тем, кто не занимается подобного рода вещами, будет интересно прочитать про решения проблем, с которыми пришлось столкнуться автору! Впечатляет!
                                  0
                                  Еще впечатляет процедурная 4k графика — International Shipping и Devour. Обе демки с Revision 2019 и с открытым исходным кодом.
                                    0
                                    вот маньяки,
                                    это они что, подбирают даже константы так, чтобы в них побольше нулей было, которые потом сжимаются лучше?

                                    #define p0d00 0.0000000000f // 0.00f 0x00000000
                                    #define p0d01 0.0100097656f // 0.01f 0x3c240000
                                    #define p0d02 0.0200195313f // 0.02f 0x3ca40000
                                    #define p0d03 0.0300292969f // 0.03f 0x3cf60000
                                    0
                                    Весьма интересуют такого рода вещи. С помощью реймаршинга легко и запросто впилить довольно бодрое 3D в 2D-движок, если он умеет вертеть пикселями. Подскажите, как распаковать код из png?
                                      0
                                      Подскажите, как распаковать код из png?

                                      s/eval/alert/

                                      0
                                      DMA — Chaos Theory 4k (KK remix)
                                      Оригинал конечно лучше, но тоже ничего.

                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                      Самое читаемое