Как мы уложили компьютерный мультик в 8 кБ

В ноябре 2022 года мы задали себе задачку: можно ли запрограммировать анимацию, воспроизводимую в режиме реального времени, как обычный короткий мультик, но с условием, что файл должен быть не больше 8 килобайт. При этом цель считалась бы достигнутой, если бы у нас получилась нормальная графика, анимация, режиссёрская и операторская работа, а ещё подходящая музыка. Да, 8 килобайт — на секундочку, в два с лишним раза меньше этого поста. Мы не представляли, насколько это вообще возможно, так что оставалось только попробовать.

В апреле 2023 года, спустя несколько месяцев работы, мы, наконец, выкатили ленту Барашек и цветок. Можете сами скачать ее или проследить на YouTube ход выполнения программы.

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

Обзор

Результат нашей работы — это исполняемый файл Windows. Это единственный.exe‑файл, генерирующий всё. Для него не требуется никаких ресурсных файлов и не требуется иных зависимостей кроме как для Windows и для скачивания свежих драйверов.

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

• Все визуальные элементы вычисляются в режиме реального времени на графическом процессоре с использованием шейдеров GLSL. В частности, это касается информации о хронометраже, настроек камеры и т. д.

• Рендеринг выполняется методом обхода лучей (ray marching).

• Шейдеры минифицируются при помощи моего собственного инструмента Shader Minifier.

• Музыку мы написали при помощи OpenMPT и синтезатора 4klang, который генерирует ассемблерный файл для воспроизведения музыки. Инструменты описываются процедурно, а список нот просто архивируется.

• Код написан на C++ при помощи Visual Studio 2022.

• Чтобы сразу было проще с флагами компилятора и инициализацией, мы воспользовались фреймворком Leviathan.

• Готовый продукт был дополнительно ужат при помощи Crinkler.

С чего всё начиналось

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

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

Кстати, кажется, отлично влезает в 8 кб! Как думаешь, ты бы взялся? Я всегда мечтал выкатить в прод нечто подобное, но вот всё сижу и жду «хорошую и оригинальную идею».

Я сразу загорелся этим проектом, так как хотел наделать ещё демок с развёртыванием сюжета и анимацией. В то же время, я видел вызов в том, чтобы сделать что‑то целостное размером 8 кБ: обычно я нацеливаюсь на 64 кБ, а это совершенно иной мир, там действуют иные правила и возникают свои сложности. Что касается музыки, работу композитора я мог доверить старому доброму CyborgJeff. Анатоль поднаторел в разработке под 4 кБ. Если он в деле, то сильно возрастают шансы на успех всей затеи. Так и началось наше сотрудничество. Я сильно сомневался, удастся ли уместить проект в 8 кБ, но, как говорится, «не попробуешь — не узнаешь», верно?

Почему именно 8 кБ? В демосцене предлагается множество категорий размеров, и варианты с 4 кБ и 64 кБ очень распространены. Мне всегда нравились приёмы, используемые в роликах-заставках по 4 кБ (такой ролик – это, по сути, демка, объём которой жёстко ограничивается), но такой формат всегда кажется слишком ограниченным и не подходит для полноценного сюжета. Revision, самый мощный демократизатор в мире, несколько лет назад ввёл в игру и 8-килобайтные демки, так что как раз выпала возможность их потестировать.

Отображение миров в двух треугольниках

Если вы знакомы с демосценой, то уже знаете, как это делается, поскольку такой подход считается стандартным с 2008 года. Рисуем треугольник (вернее, два треугольника), так, чтобы он(и) накрывал(и) весь экран. Затем выполняем программу, работающую на графическом процессоре (она называется «шейдер») — применяем шейдер к прямоугольнику, для этого используется язык GLSL. Программа вычислит цвета для каждого пикселя и каждого кадра. Нам понадобится всего лишь функция, принимающая на вход координаты (и время), а возвращающая цвет. Просто, правда?

И вот большой вопрос: как написать функцию, которая нарисует нам барашка?

Давайте разделим эту задачу на две части:

1. Представить сцену в виде поля расстояния со знаком.

2. Методом обхода лучей преобразовать поля расстояний в пиксели.

Поля расстояний со знаком (SDF)

Поле расстояния — это функция, вычисляющая дистанцию от точки в пространстве до ближайшего объекта. Для каждой точки в пространстве требуется определить, насколько она удалена от объекта. Если точка находится на поверхности объекта, то эта функция должна вернуть 0. Это «знаковая» функция — то есть, она будет возвращать отрицательные значения для точек, расположенных внутри объекта.

В самых элементарных случаях написать такую функцию не составляет труда. Например, расстояние между точкой и сферой вычисляется тривиально. Для куба такая операция также выполняется в паре строк кода (подробнее см. в статье The SDF of a Box). Уже документированы такие функции и по многим другим простым объёмным фигурам. Иниго Квилез собрал приятную коллекцию простых фигур для многократного использования, другая замечательная библиотека также предоставляется группой Mercury, которая занимается разработкой демок.

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

Как только подготовите инструментарий со всеми нужными кирпичиками, работа пойдёт играючи, как будто вы собираете объект или сцену из кубиков лего. Следовательно, можно нарисовать барашка, сложив его из простых фигур (например, конусов и сфер) и объединив их. Тело и шерсть зададим в виде шумовой 3D‑функции.

Наша следующая задача — отобразить функцию расстояния на экране.

Обход лучей

Чтобы нарисовать на экране 3D-сцену, воспользуемся обходом лучей (raymarching). Это техника рендеринга, при которой поля расстояний со знаком применяются для отслеживания лучей в 3D‑сцене. В отличие от традиционной трассировки лучей, где математически вычисляется точка пересечения, обход лучей — это прослеживание траектории луча. По SDF можно определить, как далеко можно пройти по лучу, не столкнувшись с одним из объектов сцены. После этого можно вернуться к началу луча и вычислить новое расстояние. Эту операцию мы повторяем до тех пор, пока расстояние не станет равным нулю (или не будет к нему стремиться).

На следующей картинке представим, что луч начинается в камере. Камера направлена в определённую сторону. Через много итераций мы найдём точку пересечения луча с правой стеной.

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

Чтобы лучше разобраться в технических деталях, рекомендую для начала почитать туториал «Ray Marching and Signed Distance Functions». Если же вы тем более располагаете временем, то ещё лучше посмотреть видео Live Coding «Greek Temple» — это отличный углублённый пример с подробными объяснениями.

Режиссура

Предположим, вам нужно изложить сюжет, но у вас всего один персонаж, нет ни голоса, ни записанного текста, и этот персонаж только анимируется. Он может ходить (но не может поворачивать!), двигать головой и водить глазами. Сможете ли вы рассказать историю и передать эмоции, располагая лишь таким инструментарием?

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

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

Мы стремились, чтобы наш нарратив нашёл отклик у зрителя, мы воспользовались сюжетными приёмами, например, некоторой избыточностью для расстановки акцентов. Например, чтобы показать заинтересованность барашка, мы воспользовались мультипликационными 2D‑эффектами, ускоряли ему ход, подчеркнули виляние хвостиком, покачивание головой, а также добавили драматические нотки в музыку. Благодаря всем этим приёмам, история у нас получилась довольно эмоциональной.

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

Процесс разработки

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

Учитывая всю эту неопределённость, каждую константу мы подбирали в несколько итераций. Для скорости и, соответственно, для оперативной обратной связи удобно использовать шейдеры: мы перекомпилируем их во время выполнения, и вся графика обновляется не более чем за секунду.

Также нам требовалось реализовать плеер: механизм, который позволял бы контролировать время воспроизведения при помощи команд «пауза» и «ещё раз». Эти элементы оказались просто бесценными при работе с анимацией и управлении камерой, так как результаты можно было бы просматривать сразу после горячей перезагрузки шейдера. Кроме того, было никак не обойтись без саундтрека, поэтому требовалось идеально синхронизировать анимацию с музыкой. Наши первые прототипы мы спроектировали в Shadertoy, но позже перешли на KodeLife, и, наконец, перебазировали код в наш собственный проект (написанный на C++ при помощи небольшого фреймворка под названием Leviathan).

Музыка

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

В качестве композитора я пригласил моего друга Киборгджеффа (Cyborgjeff), который умеет обращаться с демосценой, а его музыкальный стиль созвучен нашим представлениям. Он решил воспользоваться синтезатором 4klang — впечатляющая программка, разработанная Gopher. 4klang идёт в комплекте с плагином, который можно подключать к любой музыкальной программе, и ещё в нём есть кнопка экспорта, при нажатии на которую генерируется файл на ассемблере. После этого файл компилируется и связывается с демкой. При запуске демки синтез звука выполняется в отдельном потоке, звук процедурно генерируется и подаётся на звуковую карту.

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

Мы изучили вывод 4klang, чтобы понять, как эта программа упаковывает данные. Киборгджефф, посоветовавшись с Gopher, смог за несколько итераций уменьшить музыкальный компонент. Мы внесли в музыку множество корректировок:

• Сократили количество инструментов с 16 до 13.

• Переписали финальную тему так, чтобы новый вариант совпадал по темпу со всей остальной музыкой.

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

Так мы смогли сэкономить немного места за счёт музыки, сохранив при этом её общую структуру и минимально потеряв в качестве. Если вы хотите подробнее разобраться, что было сделано с музыкой, почитайте об этом отдельный пост, который написал Киборгджефф: 8000 octets, un mouton et une fleur.

Анимация и синхронизация

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

Демка состоит примерно из 25 «снимков с камеры», созданных вручную. Создавая снимок, мы описываем, как каждый из 18 параметров (например, положение объекта, состояние барашка, положение камеры, фокусное расстояние, объект, на который направлена камера) изменяется с течением времени.

Например, всего в одной строке кода мы описываем положение камеры в момент снимка:

camPos = vec3(22., 2., time*0.6-10.);

Получаем линейное преобразование. Здесь «time» — это время, истекшее с нулевого момента снимка, так что можно без труда вставлять, удалять или корректировать снимок, не затрагивая остальную часть демки. Абсолютных значений времени мы избегаем, чтобы было удобнее поддерживать код.

Небольшое предостережение насчёт линейных интерполяций: при всём удобстве они зачастую выглядят плохо или механистично. Часто применяется функция smoothstep, при помощи которой создаётся более гладкая и естественная анимация. Smoothstep — это S‑образная плавная интерполяция, позволяющая сглаживать углы и избегать резких рывков при движении.

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

Текстуры и материалы

В традиционном рендеринговом движке текстуры — это 2D‑изображения, накладываемые на 3D‑модель. При работе с текстурами возникает следующая сложность: как вычислить координаты текстур и отобразить каждый пиксель текстуры на 3D‑поверхность. Поскольку мы пользуемся обходом лучей, рассчитать координаты текстур не так просто. Вместо этого будем вычислять 3D‑текстуры на лету. Как только движок обхода лучей найдёт в 3D положение той точки, которую требуется отобразить, мы передадим её 3D‑координаты соответствующей текстурной функции.

Поговорим о дорожных знаках. При помощи математических функций вычисляем треугольник или квадрат, которые будут ограничивать знак. Изображение внутри знака подготавливается комбинацией нескольких функций. Например, знак «пункт питания» создаётся из четырёх чёрных овалов, а белые фигуры добавляются для отрисовки зубчиков.

Чтобы визуализации получились интереснее, мы хотели добавить не только текстуры, но и отличающиеся материалы. Переменные в уравнении освещения зависят от материала. Например, копыта барашка по‑своему отражают свет (для этого используются коэффициенты Френеля).

Глаза

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

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

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

Сверх того мы создали рельеф окружения (environment mapping). Такой приём часто используется в видеоиграх: чтобы не приходилось в режиме реального времени вычислять точные отражения в рамках сцены, можно посмотреть в текстуру (имитирующую окружение). Как правило, окружение картируют для оптимизации кода, поскольку текстура может в упрощённом виде представлять окружающую среду. Мы поступили прямо наоборот: окружение у нас идеально белое, но мы детализировали его при помощи текстур, причём одни детали мы добавили, а другие сымитировали.

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

Постобработка

Когда всё готово, приступаем к постобработке — это последние визуальные штрихи, помогающие конкретизировать настроение.

Несмотря на то, насколько малозаметен данный этап, постобработка помогает повысить качество картинки и задать тональность истории. Мы использовали:

• цветовой грейдинг;

• гамма‑коррекцию;

• немного виньетирования;

• наконец, два прохода FXAA‑фильтра, чтобы избежать наслоения (но вы бы его всё равно не заметили, если бы посмотрели только кадры с YouTube)

Кроме того, некоторые эффекты мы реализовали именно на этапе постобработки — например, звёздочки в глазах у барашка или заключительный кадр. Они были сделаны в чистом 2D и в 3D‑мире не существуют.

Наконец, мы поэкспериментировали и с другими альтернативными стилями. На каком‑то этапе мы старались добиться эстетики старых мультиков, и поэтому реализовали обнаружение контуров (чтобы сильнее казалось, что картинка отрисована вручную) с монохромным рендерингом, зернистостью и шумами. Получилось вот что:

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

Сжатие

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

Без магии не обойтись, и отчасти она обеспечивается при помощи Crinkler. Это инструмент для сжатия данных, специально предназначенный для работы с демосценой и вводными заставками размером от 1 кБ до 8 кБ. Поскольку исполняемый файл должен быть самоизвлекаемым, Crinkler включает в сборку небольшой фрагмент очень толкового кода на ассемблере, который и распаковывает остаток исполняемого файла. Он оптимизирован под минимальный размер за счёт других вещей: алгоритм сжатия выполняется достаточно долго, декомпрессия идёт относительно медленно и сильно расходует оперативную память (сотни мегабайт).

Crinkler — впечатляющий инструмент, но и он не всесилен. У нас в совокупности набралось aж 42 кБ шейдерного исходного кода, и нам оставалось сделать последний шаг, чтобы уместить его в наш бинарник.

Минификация

Поскольку код шейдеров включается в окончательную версию бинарника, нам требовалось как можно сильнее уменьшить этот код. Можно было бы минифицировать код и вручную, но в таком случае могли бы возникнуть проблемы с его поддержкой. Чтобы наш проект увенчался успехом, было критически важно добиться высокой скорости итераций, абстрагировавшись от низкоуровневых оптимизаций. Словом, нам требовался инструмент для минификации шейдеров.

Я сам написал такой инструмент, Shader Minifier, занимался им в качестве сайд‑проекта с 2011 года. Он удаляет ненужные пробелы и комментарии, переименует переменные, и ещё на многое способен. Мой инструмент минификации шейдеров несколько лет оставался самым популярным из себе подобных во всей демосцене, но для наших целей он был недостаточен. В 8-килобайтной заставке гораздо больше кода, чем в 4-килобайтной, и из‑за такого увеличения кода возникают специфические проблемы.

Я на месяц приостановил работу над демкой, чтобы добавить в Shader Minifier все те фичи, которых нам не хватало. Притом, что написать элементарный минификатор не составляет труда, для качественной минификации требуется создавать целый компилятор, который будет превращать исходный код на одном языке в код на другом. Примерно так работает Closure Compiler.

Полный список преобразований, поддерживаемых Shader Minifier, получается довольно длинным, так что перечислю несколько избранных:

• Переименование функций и переменных;

• Втягивание переменных;

• Вычисление арифметических операций над константами;

• Втягивание функций;

• Удаление мёртвого кода;

• Слияние объявлений.

Благодаря таким преобразованиям удаётся уменьшить размер вывода, но этого недостаточно. Необходимо убедиться, что вывод будет хорошо поддаваться сжатию. Это сложная проблема: что делать, если в результате преобразования сам код немного уменьшится, но в заархивированном виде станет больше, чем был бы без такой оптимизации? Поэтому на каждой итерации демки необходимо постоянно отслеживать, каков размер кода в сжатом виде.

Нововведения, которые я добавил в Shader Minifier, позволили ужать заархивированный бинарник ещё на 600 байт. Чтобы было проще проводить ревью и отслеживать, что именно попадает в окончательную комплектацию бинарника, мы храним минифицированный вывод в репозитории. Оказалось, такая практика помогает подыскивать новые варианты оптимизации. В конце концов, после минификации и сжатия шейдерный код в 42 кБ умещается примерно в 5 кБ, поэтому у нас остаётся достаточно места и на всю музыку, и на код C++.

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

Заключение

Как видите, за подготовкой этой демки нам довелось задействовать множество продвинутых и увлекательных приёмов. Но мы не изобретали её с нуля. Мы опирались на то, что было сделано до нас. Невероятно, какой объём подготовительной работы и исследований уже был проделан за нас — от методов обхода лучей до создания специального софта для генерации музыки и до алгоритмов сжатия. Надеюсь, новые возможности, добавленные в минификатор шейдеров, в будущем помогут с созданием демок и кому‑то из наших коллег. В категории на 8 кБ работать интереснее, чем в категории на 4 кБ, и возможности там шире; хочется, чтобы она стала популярнее.

P. S. Для сравнения: в тексте этого перевода более 24 000 символов, так что он занял бы более 24 кБ.