Поделюсь с вами успешным опытом разработки рендера в браузере большой, постоянно расширяющейся анимационной сцены, состоящей из множества мелких двигающихся объектов, зацикленных в 5 секунд.
Задача
Давайте представим, что перед нами стала задача создать веб-страницу, которая должна рендерить зацикленную растровую анимацию (60 кадров, fps - 12) размером более чем 5000x5000 пикселей и при этом важно её загружать как можно быстро, поддерживать все современные браузеры и моб. устройства, делать изменение масштаба просмотра (zoom in/out).
Анимация в исходном виде разбита на секции размером 1016x812 пикселей и каждая секция хранит 60 png файлов (1 файл на кадр). Исходный размер всех png файлов, которые нужно превратить в анимацию - 1.03 ГБ. Также важно учитывать, что регулярно добавляются новые секции и размер анимации с каждым днем растет.
Анимация содержит сильно детализированную пиксельную рисовку, поэтому важно сохранить достаточно высокое качество картинки.
Итого, у нас 1+ ГБ информации, которую нужно быстро загрузить в браузере и воспроизводить как анимацию с fps=12. Задачу условно можно разделить на 2 взаимосвязанные подзадачи:
как упаковать такой объем информации в приемлемые для скачивания размеры и при этом минимально потерять в качестве (а в идеале сохранить исходное качество);
как рендерить скаченные данные на клиенте.
Поиск решения
Так как анимация уже разбита на секции, то почему бы просто не превратить каждую секцию в некий воспроизводимый браузерами формат и подгружать его по мере приближения viewport браузера к нужной секции во время скролирования? Т.е. по сути на странице будет некая сетка NxM, где в каждой ячейке сетки будет свой элемент с воспроизведением анимации (<img>, <video> или даже <div> с background-image), а на JS мы определяем какие ячейки сейчас видны пользователю (например, с помощью IntersectionObserver) и только их загружаем и воспроизводим. Такая сетка может выглядеть вот так:
С ходу кажется все просто, осталось подобрать формат файла для показа каждой секции. Но встает неприятная проблема - необходимо синхронизировать воспроизведение анимации во всех видимых ячейках. Т.е. если в одной ячейке сейчас будет показываться кадр №20, а в соседней ячейке кадр №19, то вся анимация разрушается и будет виден явный стык между ячейками.
Так как нужна синхронизация, то сразу отпадают все растровые анимационные форматы, воспроизведение которых мы в браузере никак не можем контролировать, а это GIF и APNG.
Остаются только видео форматы, которые мы можем воспроизводить в <video> элементе внутри каждой ячейки и по какому-то триггеру (таймаут и/или действия пользователя) синхронизировать кадры во всех видимых пользователю плеерах.
Современные браузеры поддерживают различные видео форматы, такие как mp4, webm, webp, avif и пр. Остановимся на 2х самых популярных - mp4 (H.264) и webm (VP9). Оба формата хорошо делают сжатие рисованной анимации, можно настраивать частоту ключевых кадров и качество сжатия кадра.
Чтобы браузер мог достаточно быстро синхронизировать видео до нужного нам кадра необходимо иметь частые ключевые кадры (т.н. i-frames). Если у нас будет только 1й кадр ключевым, то в случае синхронизации видео с условно 5го кадра до 45го браузеру придется вычислять разницу в 40 кадров, чтобы подготовить картинку для вывода. Это очень заметно, особенно, когда таких видео несколько нужно синхронизировать. Так как FPS=12, а синхронизацию достаточно делать раз в 5-10 секунд (получено эмпирическим путем), то я выбрал частоту ключевых кадров - 10. Это, в худшем случае, заставит браузер вычислять разницу в 10 кадров. Часто делать ключевые кадры нельзя, так как это значительно увеличивает вес файла.
В чем проблема выбранного способа
Сразу обмолвлюсь, что на таком способе все более-менее успешно работало несколько лет. Было много багов на разных устройствах, все они правились кое-как, где-то костылем, где-то качественным багфиксом. Однако, есть ряд проблем, которые подтолкнули меня заняться разработкой сложного велосипеда - своего формата видео.
Итак, к основным проблемам можно отнести следующее:
Сохранение пиксельной четкости при масштабировании. Это проблема, которую никак не смог решить на рендере через тег
<video>. Тут ни повышение качества видео, ни css свойства типаimage-rendering: pixelatedне помогают. Можно, конечно, загружать видео в хорошем качестве в невидимый контейнер и рендерить его в<canvas>, чтобы на нем уже делать масштабирование с отключеннымimageSmoothingEnabled, но этот способ очень ресурсоемкий оказался.В некоторых браузерах есть лаг зацикленных видео: при возвращении видео к первому кадру воспроизведение ненадолго замирает. Где-то правится костылем, где-то никак не правится. Это сильно ухудшает просмотр анимации, так как каждые 5 секунд сцена ненадолго замирает в одном и том же моменте.
Периодическая синхронизация видео не дает гарантии, что в интервал между синхронизациями не произойдет замедление одного видео относительно другого. Увы, браузеры не гарантируют скорость воспроизведения каждого видео элемента, и даже если вы ничего со страницей делать не будете после, условно, 20-40 секунд одновременного воспроизведения 5 видео элементов, начнутся проблемы: одно видео запнулось на каком-то кадре на долю секунды и в итоге часть анимации общей стало отставать на эту дельту. Проблема рассинхронизации усугубляется на слабых устройствах. Часто синхронизировать нельзя, так как для синхронизации нужно останавливать все видео потоки, проматывать их до нужного кадра и запускать воспроизведение одновременно у всех элементов. Это нетривиальная операция и визуально может быть заметна.
Баги самих браузеров. Например, видео просто останавливается и больше не запускается. При этом никакие действия над
HTMLVideoElementне заставляют браузер восстановить воспроизведение. Этот баг происходит чаще всего на мобильных устройствах, когда переключаешься между вкладками и приложениями. Решения так и не нашел, даже костылем, так как повторяемость не частая и замирают не все видео на странице, а только некоторые. Или, например, свежая проблема в Google Chrome, когда четкость картинки у видео теряется после увеличения и уменьшения обратно видео элемента (однако, в Canary версии хрома уже проблема исправлена).Особенности воспроизведения видео на разных браузерах. Больше всего тут сюрпризов подарил Safari и некоторые его особенности показа видео элементов никак не обойти. Каждый браузер что-то да ограничивает или добавляет в плееры видео. Это сильно усложняет разработку и сопровождение проекта.
Свой видео формат
Чтобы убрать синхронизацию видео потоков, уйти от багов и особенностей <video> элемента, а также повысить качество картинки нужен формат, который можно рендерить в <canvas>. Canvas мы растянем на весь экран и будем полностью контролировать процесс рендера всей анимации. HTMLCanvasElement практически не вызывает проблем с кроссбраузерностью, поэтому баги с разными устройствами почти отпадают.
Прежде всего нужно обозначить что мы хотим добиться от своего формата:
пиксельная четкость такая же, как в оригинальном PNG. Это значит никаких размытий и артефактов не должно быть в изображении каждого кадра;
должна быть одинаковая стоимость прокрутки видео до любого кадра. Т.е. неважно на каком мы сейчас кадре, скачок на любой другой будет одинаково требовать ресурсы. Это нужно для того, чтобы видео, как только оно загрузится, моментально подключилось к рендеру общей сцены с нужного нам кадра;
каждая секция (1016x812) должна упаковываться менее, чем в 10 МБ. В идеале секция должна весить меньше, чем mp4 в наилучшем качестве (crf=1);
видео формат должен иметь превью в начале файла, чтобы во время скачивания файла, получив первые N байт, мы могли начать рендерить статический превью секции и поверх progress bar загрузки.
К проблеме пиксельной четкости можно также отнести особенности кодеков. Например, H.264 при самом лучшем качестве (crf=1) почему-то все равно делает ужасное искажение красных линий на темном фоне:
Как будем упаковывать 1+ ГБ?
Сразу стоит отметить, что приведенный 1ГБ - это в PNG формате, он уже имеет сжатие Deflate. Если посчитать в распакованном виде, то это будет
5000px * 5000px * 3 байта на пиксель * 60 кадров = 4.5 ГБ
Секционирование как и с видео остается, но только размер секции уменьшаем вдвое, с 1016x812, до 508x406. Зачем и почему мы так с видео не делали? С видео чем меньше размер секции, тем больше элементов <video> одновременно на странице и это сильно повышает расход CPU/GPU, страница заметно начнет тормозить на среднестатистическом устройстве. А для рендера в canvas нам важны алгоритмы упаковки данных, и один из таких алгоритмов нуждается в частой адресации внутри файла на конкретный байт повторяющегося фрагмента данных (мы его рассмотрим чуть ниже). Чем меньше размер секции выберем, тем меньше размер файла и мы можем адрес указывать не как 4 байта (uint32), а как 3 байта (uint24), и это хорошо сокращает размер итогового файла.
Раз уж это мы создаем свой формат специально для нашей задачи, то важно учитывать те особенности, которые мы имеем в исходных данных и подбирать алгоритмы упаковки так, чтобы наши особенности помогали в компрессии.
Давайте взглянем на увеличенный фрагмент одного кадра случайной секции
Из этого фрагмента можно вывести следующие 4 особенности графики:
палитра цветов достаточно ограниченная, т.е. тут нет как в обычной фотографии города или природы миллионов разных оттенков цветов, но в то же время цветов куда больше, чем ограничение палитры в 256 цветов, как у GIF формата;
есть области, где часто повторяется один и тот же цвет при чтении пикселей слева направо. Например, голова робота имеет длинные последовательности нескольких оттенков белого и голубого цветов;
есть пиксели, которые визуально очень похожи на соседние пиксели (видно в увеличенном кружке), и если чуть отдалится от экрана, то их не различить;
есть горизонтальные линии чередования пикселей, которые повторяются на разных строках. Например, если в рисунке есть вертикальная линия, то при построчном чтении пикселей мы несколько раз будем читать одну и ту же последовательность цветов, так как фрагменты повторяются.
Ещё одна важная особенность - анимация зациклена в 60 кадров, т.е. все, что происходит в анимации должно вернуться в состояние первого кадра где-то ближе к 59 кадру.
Алгоритм упаковки анимации
Учитывая перечисленные выше особенности и требования к формату алгоритм упаковки получился следующий:
Мы инициируем цикл по всем кадрам секции, их у нас 60 штук. Для каждого кадра выполняем процессы 1-5, а затем полученный массив данных направляем в процессы 6-9.
Шаг 1 - Квантование R, G и B каналов
Это очень популярный подход много где, особенно в оцифровке аналоговых сигналов. Суть его проста: мы разделяем пиксель на составляющие три канала (Red, Green, Blue), и каждый канал делим без остатка на шаг квантования.
Я выбрал шаг квантования - 8. Не просто так, деление на 8 легко заменить смещением числа на 3 бита, что ускоряет процесс обработки огромного числа пикселей (вместо Math.floor(v / 8) * 8 делаем v >> 3 << 3). Также, такой шаг квантования позволяет канал цвета упаковать не в 8 бит, а в 5. Таким образом после квантования с шагом 8 каждый пиксель можно упаковать не в 3 байта, а уже в 2, и при этом 1 бит остается свободным (он нам будет нужен чуть позже). Грубо говоря, у нас было 4.5 ГБ данных, а после квантования цветов размер уменьшился до 3 ГБ.
Визуально результат этого шага будет заметен только опытному глазу и "под микроскопом". На следующем изображении показан фрагмент секции до и после квантования. Немного изменились цвета, например, балка над поездом изменила оттенок.
Но самый большой плюс для нас от квантования - это избавление небольшой девиации яркости каналов, тем самым похожие цвета становятся одним и тем же цветом. Например, цвет rgb(250, 4, 0) и цвет rgb(255, 0, 0) , которые зрительно неразличимы, оба станут цветом rgb(248, 0, 0)
Шаг 2 - Объединение похожих соседних пикселей
В предыдущем шаге мы уже объединили похожие цвета за счет уменьшения палитры в 8 раз, но этого недостаточно. Остаются цвета, которые также визуально очень похожи и находятся рядом друг с другом, но у них достаточно большая разница в каналах, из-за этого после квантования они стали разными цветами. Обычно такие цвета появляются из-за сглаживания линий при рисовании (antialiasing) или при создании плавных переходов цвета (градиенты).
Для детектирования похожих цветов хорошо подойдет алгоритм Delta E (ΔE). Эта функция на вход принимает два цвета, а на выходе получаем коэффициент различия цвета. Если он меньше 1.0, то цвета неразличимы человеческим глазом, если от 1.0 до 2.0, то цвета очень похожи и также почти неразличимы, от 2.0 до 10.0 - очень похожи, но уже различимы, и т.д. до 100.
На следующем изображении показаны примеры пар цветов и вычисленное значение ΔE:
Зная особенности графики, которую мы хотим сравнивать, применим дифференцированный подход:
для оттенков серого мы считаем похожими цвета, если ΔE ≤ 2.0 (т.е. зрительно неразличимые цвета);
для любого цвета с уровнем яркости выше 50% (т.е. светлые оттенки) мы считаем похожими цвета, если ΔE ≤ 3.0;
для любого цвета с уровнем яркости ниже 50% мы считаем похожими цвета, если ΔE ≤ 4.0.
Таким образом чем темнее цвета двух рядом стоящих пикселей, тем выше вероятность, что они будут объединены. Но это не касается оттенков серого, так как эти цвета в данной анимации активно применяются для стен, полов и других объектов (очертания окружающей геометрии), и ухудшение качества сглаживания линий у таких объектов нежелательно.
Этот шаг не делает какую-либо компрессию, но результат его работы улучшает компрессию шага 4 - упаковка подряд идущих пикселей.
Шаг 3 - Вычисление разницы с ключевым кадром
Важный процесс компрессии анимации - не повторять то, что и так уже известно. В упаковке GIF и многих видео форматов есть понятия i-frame - ключевой кадр, и p-frame - кадр, хранящий дельту изменения от ключевого или от предыдущего кадра. В нашем формате не будет сравнения с предыдущим кадром, хоть это дает хорошую компрессию и повышает скорость рендера (так как буфер пикселей предыдущего кадра обычно есть под рукой). Причина отказа - необходимо выполнить требования №2 "должна быть одинаковая стоимость прокрутки видео до любого кадра". Если у нас кадры будут хранить информацию относительно предыдущего кадра, то повторяется проблема, что было у видео форматов mp4 и webm - при переходе с 5го на 45й кадр браузеру нужно будет распаковать и вычислить разницу всех промежуточных кадров, т.е. 40 кадров обработать за раз. Поэтому мы будем иметь только ключевой кадр, и причем только один - самый первый кадр в анимации.
В данном шаге мы сравниваем каждый пиксель текущего кадра с таким же по координате пикселем из первого кадра. Если разницы нет, то мы вместо текущего пикселя вставляем зарезервированный цвет - rgb(0, 0, 0). Если текущий пиксель и так равен такому зарезервированному цвету, то мы его слегка меняем на rgb(0, 0, 1), глаз такой разницы не заметит и при этом у нас высвобождается зарезервированный цвет, который мы можем применять для индикации повторения пикселя из первого кадра.
На следующем изображении показан фрагмент секции из первого кадра, и ниже этот же фрагмент, только уже на 4м кадре с вычисленной разницей. Как видно, мы очень много информации заменили на цвет rgb(0, 0, 0), и при рендере 4го кадра движок отрисовки везде, где будет встречать такой зарезервированный цвет, будет копировать пиксель с такой же координатой из первого кадра.
Шаг 4 - упаковка серии одинаковых пикселей
По сути это вариации алгоритма RLE (Run-Length Encoding), только со спецификой конкретного проекта.
Мы читаем каждые 2 байта (напомню, что после шага 1 у нас пиксели хранятся в 2 байтах) и проверяем, есть ли серии одинаковых подряд идущих пикселей. Если пиксель только один такой, то эти 2 байта никак не меняем. Если же мы зафиксировали серию одинаковых пикселей, то сворачиваем её в 3, 5 или 6 байт в зависимости от длины серии (length):
Как видно из схемы выше, для индикации, что пиксель имеет payload с длиной повторений, мы используем контрольный бит, который у нас освободился после процесса квантования. Движок отрисовки читает 2 байта каждого пикселя, и если видит, что контрольный бит установлен в единицу, то читает дополнительно 1 байт. Если значение этого байта больше 1, значит это длина повторений uint8. Если же он равен 0 или 1, то читает ещё 2 или 3 байта, в которых хранится длина повторений uint16 или uint24 соответственно.
В результате работы этого алгоритма значительно сокращается объем файла. Например, для случайной секции размером 1016x812 после шагов 1-3 размер данных будет:
1016px * 812px * 2 байта * 60 кадров = 98 999 040 ~= 99 MB
После шага 4 размер данных уменьшается до 16 010 969 (~ 16 MB), т.е. уменьшение на 83%. Но все это благодаря подготовке пикселей в шагах 1-3.
Шаг 5 - упаковка повторяющихся последовательностей
Как уже было упомянуто в особенностях графики, у нас имеются повторяющиеся чередования пикселей в разных строках. Даже после упаковки их RLE алгоритмом все равно они остаются одинаковыми. Это избыточность и нам от неё стоит избавиться. К сожалению, готовые алгоритмы типа LZW (используется в GIF), gzip, deflate плохо убирают такую избыточность, поэтому мы напишем свой алгоритм, который будет учитывать особенности нашей задачи.
Итак, алгоритм очень простой, можно даже сказать решение "в лоб" и при этом очень ресурсоемкий в процессе упаковки (требует много RAM и CPU):
В текущем кадре берем каждый пиксель с его payload (это 2, 3, 5 или 6 байт, определяем это описанным в шаге 4 способом).
Ищем такой же пиксель+payload во всех предыдущих кадрах (уже обработанных шагами 1-5).
Если нашли, то пробуем взять следующий пиксель+payload и ищем уже связку из двух пикселей с их payload во всех кадрах.
Цикл повторяется пока мы что-то да находим. Как только мы дошли до длины последовательности пикселей, которую нигде найти не можем, мы фиксируем результаты прошлой удачной итерации поиска. Как результат мы находим в каком предыдущем уже обработанном кадре есть максимальная по длине последовательность пикселей+payload такая же, как в данном.
Если длина найденного фрагмента больше 10 байт, то имеет смысл в текущем кадре заменить фрагмент на ссылку с фиксированным размером 7 байт. Структура ссылки показана на следующем изображении:
Как видно из схемы, для индикации ссылки мы используем 2 байта, которые всегда равны значениям 128 и 32. Это позволяет при распаковке каждого кадра движку рендера не путать эту последовательность байт с обычным зеленым цветом с индикатором наличия payload. Опять же, если в процессе квантования мы встретили цвет rgb(0, 0, 32), то мы слегка меняем его, чтобы использовать этот цвет как зарезервированный для индикации ссылки.
Чтобы лучше понять этот процесс можно глянуть на следующее изображение. В нем показан слева фрагмент секции и справа этот же фрагмент, где красным подсвечены все пиксели, которые были по ссылке зачитаны из других кадров.
А в следующей гифке показано уже в динамике какую часть графики движок рендера читает не из текущего кадра, а по ссылке из другого.
Для сравнения как эта же часть секции выглядит без подсветки повторяющихся фрагментов:
Важно отметить, что здесь нет противоречия с моим же утверждением, что мы не будем обрабатывать разницу с предыдущим кадром. В данном шаге мы ищем повторяющиеся фрагменты бинарных данных, т.е. повторения в не распакованных последовательностях байт. Если движок рендера видит ссылку на повторяющийся фрагмент, он зачитывает нужное количество байт по ссылке из другого кадра и распаковывает их при рендере текущего кадра. Таким образом браузеру не нужно при переходе с 5 на 45 кадр распаковывать все 40 кадров.
Если взять ту же секцию, что мы использовали в шаге 4 и получили уменьшение размера файла с 99 МБ до 16 МБ, и применить к ней шаг 5, то размер файла уменьшится на 33%, до 10.7МБ.
Шаги 6-9 - Финальная упаковка всего в файл
Свои алгоритмы упаковки хорошо, но есть эффективные и популярные алгоритмы сжатия общего назначения, применив которые мы ещё сильнее уменьшим размер файла. Так как мы работаем с браузером, то это либо gzip, либо deflate. Оба они имеют нативную поддержку в js c недавних пор, но для браузеров, которые не имеют пока что Compression Streams API, можно использовать сторонние библиотеки, типа pako.
Можно, конечно, вообще не паковать дополнительно и переложить все это на плечи HTTP транспортировки, применять тот же Brotli, но я решил перестраховаться и паковать/распаковывать файл своей программой.
Итак, для дополнительной компрессии выбираем gzip, так как после ряда тестов он показал лучшие результаты на этих данных.
У нас есть требование, чтобы в момент загрузки файла, когда мы получим первые N байт, мы уже могли начать рендер некой превью секции. Для превью подойдет первый кадр, поэтому мы его отдельно сжимаем gzip (шаг 6).
Далее нам нужно создать небольшой индекс всех кадров внутри файла (шаг 7), чтобы программа чтения файла знала с какого байта и какой длины расположен каждый кадр внутри файла. Индексом будет простой фиксированной длины массив uint32. Индекс не сжимаем, он весит копейки. В индекс также заносим информацию о том, какая позиция первого кадра в компрессии gzip, и без неё. Без неё информация нужна для рендера, а с gzip информация нужна для чтения кадра в момент загрузки файла.
Итоговая структура видео файла будет следующей:
Если для примера взять секцию, которую мы считали в шаге 4 и 5, и выполнить над ней шаги 6-9, то в результате будет файл с размером 5.4 МБ, т.е. ещё 50% сократили относительно шага 5.
Чтобы у вас не осталось мысли, мол, зачем все эти шаги, нужно было сразу gzip на исходные данные и все, приведу расчет упаковки чисто на gzip, отменяя каждый шаг по одному, начиная с конца:
без шага 5, где мы упаковали повторяющиеся фрагменты, gzip вернет 10.6 МБ (т.е. потеряли 5 МБ);
без шагов 4 и 5 gzip вернет уже 11.6 МБ;
без шагов 2-5 - 34.9 МБ;
без всех шагов обработки (т.е. чистые данные rgb пикселей) - 69.7 МБ.
Таким образом gzip хорошо дополняет, но не заменяет процесс упаковки анимации.
Остался один главный вопрос: какой будет финальный размер всех секций после компрессии их этим алгоритмом? После компрессии 1 ГБ png файлов на выходе мы получили 82 МБ. Т.е. компрессия относительно png помогла уменьшить объем информации в 12.5 раз, а относительно сырых данных (4.5ГБ) - в 54 раза. Для сравнения mp4 с crf=19 (среднее качество, нет пиксельной четкости) всех секций весит 45МБ, а mp4 с crf=1 (лучшее качество) - уже 116 МБ. Т.е. наш формат достаточно хорошо сжал при том, что мы смогли сохранить пиксельную четкость и совсем немного исказить цвета.
Как будем рендерить полученный формат?
Одно дело придумать формат, другое - найти способ его быстрого воспроизведения на клиенте. Основная сложность для нас - как распаковывать кадры всех секций, что сейчас видит пользователь, со скоростью 12 кадров в секунду. Казалось бы, всего 12 кадров в секунду, т.е. на 1 кадр у нас 83мс, времени хоть отбавляй. Но мы работаем c JS, это не сверхбыстрый язык, поэтому одновременная распаковка, условно говоря, 5-10 секций размером 508x406, чаще всего не будет успевать в 80мс. Встает самый главный вопрос - как нам ускорить процесс распаковки?
Один из вариантов - использовать WebGL или WebGPU для перевода математики распаковки на плечи видеокарты. Ранее я применял такой подход на JS для других задач, типа GPGPU, однако, именно такой формат данных не представляю как можно распаковать на видео карте.
Другой вариант - WebAssembly. Однако, реализация парсера на Rust->wasm показала такие же результаты по скорости, как реализация такого же алгоритма на чистом JS (спасибо сильнейшей оптимизации движков JS в последние годы). Если делать многопоточный wasm, то разные секции можно направлять в разные потоки, что позволит параллельно распаковывать кадры каждой видимой секции. Но зачем делать сложный многопоточный wasm, когда все можно на простом JS реализовать, ведь уже давно есть замечательные Web Workers!
Именно Web Workers API нам подойдет лучше всего, так как такая реализация не требует знаний дополнительных языков для компиляции wasm. Принцип работы будет простым:
каждая секция создает свой экземпляр Worker и передает в него URL нужного видео файла;
Worker загружает файл через обычный Fetch API, но при этом содержимое файла получает чанками (вот тут подробнее как такое делать). С каждым полученным чанком делаем postMessage в основной тред, чтобы сообщить какой процент файла уже загружен (нужно для прогресса загрузки);
Если мы накопили достаточно чанков, чтобы построить индекс файла (а он идет в начале файла и имеет фиксированную длину), то мы парсим индекс и узнаем позицию и размер в байтах упакованного в gzip первого кадра анимации;
Если мы накопили достаточно чанков для распаковки первого кадра, то зачитываем нужные байты из чанков, делаем ungzip и парсим кадр в массив RGBA (Uint8ClampedArray). Передаем этот массив в основной тред через postMessage, где он будет превращен в ImageBitmap и рендерится под прогрессом загрузки как превью секции.
Загружаем все оставшиеся чанки и сообщаем в основной тред, что загрузка завершена и можно начинать рендерить любой кадр этой секции.
Основной тред каждые 83мс отправляет сигнал во все активные и уже полностью загруженные Worker, чтобы они начали подготовку следующего кадра. Каждый воркер отвечает за свою секцию и внутри себя хранит бинарные данные видео файла своей секции и распакованный в RGBA первый кадр анимации (так как он ключевой).
Как только все Worker завершат подготовку следующего кадра и передадут в основной тред Uint8ClampedArray с RGBA информацией, мы сообщаем рендеру, что все готово для отрисовки следующего кадра.
Ждем следующего вызова requestAnimationFrame и просто делаем отрисовку кадра каждой секции в основной canvas.
Если пользователь скролирует сцену и секция больше не видна, то терминируем Worker, тем самым удаляем все из памяти. Если пользователь вернется обратно к выгруженной секции, то мы повторно создадим Worker и начнем загрузку видео файла, но в этот раз браузер отдаст нам его из disk cache, что моментально позволит отобразить секцию обратно.
Процесс параллельной загрузки секций показан в следующей гифке (стык 4х секций). Как видно, во время загрузки спустя некоторое время появляется превью картинка (это затемненный наш первый кадр). Затем, как только последний байт файла будет загружен, мы моментально подключаем секцию к рендеру с произвольного кадра.
По моим замерам на разных устройствах и браузерах параллельная работа Worker справляется в среднем за 5-20мс, чтобы подготовить кадр у всех видимых секций на экране. Но чем больше экран, тем больше секций, и тем больше нагружается CPU и время подготовки кадра увеличивается. И наоборот, чем меньше экран (а это мобильники и планшеты), тем меньше нужно активных воркеров и CPU на распаковку кадров.
Встает вопрос - а зачем вообще распаковывать налету, не проще ли распаковать все кадры один раз после загрузки и хранить их уже в распакованном виде? Ответ прост - не потянет память вкладки браузера, ведь по сути для 10 активных секций нужно будет выделить
10 секций * 508px * 406px * 4rgba * 60 = 494 995 200 ~= 500 МБ
Если к ним добавить все дополнительные издержки страницы, то получится все 700МБ. Но это только 10 секций, а если экран побольше, то нужно будет уже больше ГБ памяти, а то и больше. В любом случае меня интересовал такой вопрос и на первых же тестах страница падала с ошибкой Out Of Memory. Поэтому для экономии RAM нам нужно в памяти все хранить в упакованном виде, и нагружать CPU для распаковки каждого кадра перед его рендером.
Заключение
Видео форматы mp4 и webm имеют отличную компрессию и при этом достаточно хорошо сохраняют оригинальное качество. Однако, синхронное воспроизведение таких форматов имеет ряд проблем, которые либо не решаются никак, либо решаются очень ненадежными костылями. Также эти форматы плохо подходят для графики, где важно сохранить пикселизацию, особенно при масштабировании видео. Качественным решением проблемы синхронизации и пикселизации может быть замена рендера на canvas. Но для это потребуется разработка своего формата видео, который должен учитывать особенности того контента, что будет рендерится и быть не хуже по качеству сжатия, чем mp4. В частности мы рассмотрели случай рендера рисованной пиксельной анимации, которая хорошо поддается сжатию достаточно простыми алгоритмами. Как результат получили формат, который на выходе имеет приемлемый для быстрого скачивания размер, и с помощью многопоточного JS без особо сильных затрат CPU и RAM может рендерится в канвас.
Комментарии (87)
Aspos
24.06.2022 18:10Когда-то очень давно видел как для сжатия спутниковых снимков использовался фрактальный подход. Там вся соль была в том, что на таких снимках одельные элементы очень часто бывают похожи.
Кодирование требовало очень много времени, распаковка тоже, но зато растровый файл сжимался из ГБ в сотни КБ.
Плюс картинка прекрасно масштабировалась, качество выходной картинки можно было варьировать в завимимости от FPS бюджета.Пример работы на эту тему.
entze
24.06.2022 18:30+1Fractal и Wavelet сжатия были в моде в конце 90-х.
Кажется оба нашли применение в форматах для специфических данных, например wavelet в рентгеновских снимках. Также нашло применение в формате JPEG2000 поддерживаемом в Acrobat PDF.
Tyusha
24.06.2022 19:24+12Налицо ещё одна особенность изображения — его изометрия. Не будет ли оптимальнее отыскивать повторяющиеся пикселы не в горизонтальной строке, а "по диагонали". Возможно корреляция будет выше.
И раз уж "пошла такая пьянка", даже более того, а не ввести ли не косые "диагональные" координаты пикселей для хранения, сжатия и обработки графики. Впрочем это добавляет необходимость пересчëта координат при окончательном выводе в canvas.
horpia Автор
24.06.2022 19:41+16Я тоже думал использовать как-то аксонометрию. Но проблема в том, что тут не чистая изометрия и косые линии сильно дробно вычисляются, т.е. там очень много математики с дробными числами придется делать. С дробными вычислениями на JS проблема может быть в точности, да и ресурсов они будут больше требовать, так как по сути на каждый пиксель мне нужно будет вычислять его координату учитывая углы поворота. Всего этого можно почти не боятся, если перевести рендер на WebGL в фрагментный шейдер, но я так и не смог придумать как с меньшими затратами передавать на карту в виде текстур каждый кадр и раcпаковывать его на сильно ограниченном GLSL. Т.е. я бы хотел использовать эту сильную сторону графики (аксонометрию), но по расчетам получилось, что используя её я могу сильно проиграть в расходе CPU
Alexey2005
24.06.2022 19:35+6Вот только стандартные видеоформаты давно распаковываются аппаратными кодеками, почти не нагружая процессор и не выжирая батарею, а тут у нас будут софтверные распаковка и рендер со всеми их недостатками.
horpia Автор
24.06.2022 19:47+5Все верно, CPU расходуется значительно больше, чем с mp4. Из-за этого я планирую включать рендер на Mp4 по умолчанию на устройствах, где выполняется любое из условий:
слабый интернет
батареи меньше 50%
И то и другое можно узнать из js стандартными API браузера (правда поддержка ещё не полная). Если я вижу, что устройство слабое - включаю старый рендер на mp4, иначе - новый. При этом пользователям всегда будет дана возможность переключать между SD (на Mp4 файлах) и HD (на canvas).
Piterski
25.06.2022 16:01+1А что за api такое для того чтобы узнать слабый интернет, не подскажите?
horpia Автор
25.06.2022 16:09+2https://developer.mozilla.org/ru/docs/Web/API/Network_Information_API
В частности вот так буду принимать решение какой формат загружать пользователю
const isSlowNetwork = navigator?.connection?.downlink < 5;
homm
24.06.2022 19:55+4> Например, H.264 при самом лучшем качестве (crf=1) почему-то все равно делает ужасное искажение красных линий на темном фоне:
Chroma subsampling
homm
24.06.2022 20:05+3> Например, цвет rgb(250, 4, 0) и цвет rgb(255, 0, 0), которые зрительно неразличимы, оба станут цветом rgb(248, 0, 0)
Это очень плохо, 255 должен остаться 255 после квантования.horpia Автор
24.06.2022 20:27Да, согласен. Вся анимация стала чуточку темнее. Я это планировал поправить в рендере на днях, просто при распаковке пикселей буду добавлять +7 к каждому каналу:
r = (r << 3) + 7 g = (g << 3) + 7 b = (b << 3) + 7
orekh
24.06.2022 21:13+2Обычно растягивают либо так: Math.round(v / 31 * 255)) либо так: (v << 3) + (v >> 2). Но я считаю все способы неправильными.
ermouth
26.06.2022 05:20+1Ещё можно на канвас прицепить
filter:brightness(1.028). Но, по-моему, небольшое снижение яркости даже лучше для различимости мелких деталей в светах. Я попробовал поправить яркость, и сразу рельеф на светлых панелях стал менее заметен.За работу глубочайший респект!
Barabashkad
24.06.2022 20:30-8не совсем понял для чего надо синхронизировать отдельные фрагменты ?
почему нельзя кодировать всю картику 5000х5000 ?
почему нельзя передавать комнаду на сервер для передачи нужной видимой области ? и там же делать кропинг и zoom in ?horpia Автор
24.06.2022 20:38+11Ну, во-первых размер всей сцены все время растет, сегодня 5000x5000, через год будет 10000x10000, а через 10 лет страшно представить что будет) Любой знакомый мне формат графики имеет ограничения на максимальный размер картинки, поэтому деление в любом случае рано или поздно потребуется.
Деление на секции нужно для ускорения загрузки и минимизации трафика. Т.е. мы загружаем только то, что видит пользователь и подгружаем постепенно то, к чему пользователь скролирует.
Что-либо налету отрезать на сервере - нереально для такой задачи, речь ведь про анимацию, а не статическую картинку.
Barabashkad
24.06.2022 23:11-17Вы правы все форматы ограничены, в основном до 2^13 = 8192x8192 точек
но какое это имеет значение если вближайшие лет 10 не будет таких экранов ;-)
даже 5К ретина ... раза в 3 меньше :-)
Вы так же делите на области , этот процесс называеться croping достаточно простая операция и не зависящая от размера входной картинки ;-)
кропаете и компресируете ... к тому же можете прооптемизировать и эти операции для нескольких пользователей ... так как при большом спросе навярняка найдутся кто смотрит одно и тоже или почти одно и тоже , оконочателную подгонку можно оставить клиенской части.
в плане компресси вы конечно молодоце что изобрели PNG заного ...
все что вы описали именно так и делаеться в этом стандарте ...
этот формат конечно можно использовать и он так и родился для передачи картинок по сети когда интернет родился ;-)
но с тех пор воды много утекло
компресируетр хоть и без потерь но плохо , в 2-3 раза ... для общего случая, в вашем возможно 5-6 ... но любой мп4, h264,h265 и темболее av1 может и раз в 30-40-50 и качество будет на уровне
к тому же аппоратная поддержка как на серверах так и на клиентах ...
ну и на закуску CRF параметер не совсем подходит для потоковой передачи данныхBarabashkad
26.06.2022 14:22-1ух ты ... аж -13 :-)
аж интересно что так не понравилолсь ? технические детали ? ;-)
BellaLugoshi
26.06.2022 19:18+2Я не могу ставить минусы, но и не люблю когда минусы ставятся просто за мнение, без приведения контраргументов.
Вот мои 5 копеек:
Вы так же делите на области , этот процесс называеться croping достаточно простая операция и не зависящая от размера входной картинки ;-)
Чтобы сделать кроп PNG файла например для правого нижнего угла придётся распаковать всю картинку, потом взять кусок и так Х раз - где тут простота если у вас сложность будет O(N*N)?
в плане компресси вы конечно молодоце что изобрели PNG заного ...все что вы описали именно так и делаеться в этом стандарте ...
В PNG нет анимации совсем, а значит и придуманное в компрессии никак не может копировать PNG, который всего лишь Deflate. Тут же весьма интересный набор эвристик с заточкой под контекст.
но любой мп4, h264,h265 и темболее av1 может и раз в 30-40-50 и качество будет на уровне
Мне кажется вы совсем не читали статью.
Barabashkad
26.06.2022 21:14-1Спасибо за внимание :-)
Чтобы сделать кроп PNG файла например для правого нижнего угла придётся распаковать всю картинку, потом взять кусок и так Х раз - где тут простота если у вас сложность будет O(N*N)?
в статье не указано откуда и как проявляются картинки , где то кто то их генерирует/рисует
но не указано что это PNG, этот формат автор использует как раз для хранения областей.
но это все все не суть важно, а важно что сначала картинка разбиваеться, потом как то сжимаеться и передается и потом показываеться небольшая часть из всего этого ...
выбор видимой области можно производить у клиента и запрашивать с сервера сразу.
разбитие на области это тот же самый cropping только один раз
Я так понимую Х это у вас количество пользователей ...
если да ... то для нескольких пользователей , если их будет немного больше чем областей у автора, будет возможно хуже , но при большом количестве пользователей будет много повторений или перекрытий по 90%,
что можно с оптимизировать делая кроп один раз для многих пользователей
а окончательную подгонку производить уже на клиентеВ PNG нет анимации совсем, а значит и придуманное в компрессии никак не может копировать PNG, который всего лишь Deflate. Тут же весьма интересный набор эвристик с заточкой под контекст.
PNG имеет нескольки уровней компресси и да нулевой действительно только deflat, но 1,2,3 включают как раз вычесление похожости соседей и стандарт и оговаривает 3 разных способа
* вычитание строк
* вычитание столбцов
* вычисление среднего из соседей и вычинание
что принципе по блок схеме приведенного алгоритма блок номер 2
а Deflat это аналог блока номер 4
но да, квантования PNG не поддерживает и вычитание соедних кадров ...
эти подходы используют MPEGи ну значит добавим еще изобретение и их тоже ;-)
кстати ... квантование у автора ... подозрительно напоминает RGB15 ;-)Мне кажется вы совсем не читали статью.
конечно ... автору не совсем понравились цветовые артефакты вносимые компресией
с потерями, но вместо того что бы разобраться как MPEGами пользоваться придумал свой способ, ну что ж респект :-)
Кстати, если уж так и не получилось найти параметры которые устраивают по качеству
и, как кто то уже упоминал, YUV 4:4:4 имею ограниченую поддержку
можно кодировать R,G,B как отдельные Gray картинки теме же стандартыми кодэками как независимые потоки,могло бы получиться очень даже хорошоhorpia Автор
26.06.2022 21:24+3ещё раз напомню основную причину ухода со стандартных видео-форматов - мне нужна пиксельная четкость (при масштабировании) и уход с синхронизации. Ни один формат этого не может позволить в браузере, поэтому создан свой с рендером в канвас. Вот тут https://floor796.com/?render=2 попробуйте зумом увеличить, будет пиксельная четкость, такого не добиться от mp4 или любого другого формата.
Повторюсь, что-либо перекладывать на сервер - не вариант. У меня бесплатный проект, я не могу позволить купить огромные вычислительные мощности и огромный канал, чтобы переложить кропинг/рендеринг с клиента на сервер. Как известно, клиентов в разы больше серверов, поэтому такие вещи нужно переводить на выполнение у клиента, а не на сервере.
Добавлю, я стараюсь не велосипедить, но когда безвыходная ситуация, то велосипед - это решение.
Barabashkad
26.06.2022 21:36Вы делите картинку на фиксированные заранее известные области большого размера это уже кропинг, которые потом нужно синхронизировать, вместо этого можно делать маленький кропинг специально для каждого пользователя пользователя и нужда в синхронизации отпадает.
Использование стандартных формат позволяет использовать аппаратное ускорение на сервере что сэкономит оплату процесорного времени, так же как и уменьшение трафика
То есть остается «пиксельная четкость» и если я правильно понял конкретно цветная
И вот тут возможно правильное использование кодеков может помочь
horpia Автор
26.06.2022 21:47+1вместо этого можно делать маленький кропинг специально для каждого пользователя
На сервере? Если пользователь сдвинул сцену на +1px, то мне у сервера запрашивать новый кропинг под размер его экрана. Вы понимаете какая должна быть ширина канала у пользователя, и я уже молчу какая у сервера для того, чтобы налету без задержек все это делать. Вы открывали проект, смотрели вообще о чем речь?))
так же как и уменьшение трафика
С CPU согласен, а вот с трафиком нет. В статье я показал, что мой формат лучше сжимает без видимой потери качества, чем mp4 (h264): 116 МБ mp4 против 82МБ на моем формате. Однако сейчас я свой формат переключил с gzip на Brotli и в итоге вместо 82 МБ стало 57МБ. Т.е. в 2 раза лучше компрессия, чем у Mp4 (crf=1) и сопоставимая компрессия с crf=19 (45МБ).
И вот тут возможно правильное использование кодеков может помочь
Дело не в кодеках, дело в самой отрисовке. Нельзя зумить video элемент без размытия в браузерах. Ну и любой любой кодек будет все равно вносить искажения, так как ни один кодек не заточен под такую задачу, как у меня. По крайней мере ни один, что поддерживают браузеры.
Barabashkad
26.06.2022 23:51-1Конечно прекрассно представляю как должно и может работать со сдвигом хоть на пиксел хоть на 2 , именно так работают облачные игровые платформы у NVIDIA, Microsoft , Amazon ....
И проэкт ваш открывал ...
искал где же нужно разбиение на области ... ненашел :-)
ваше решение - скачивать огромный файл на клиента и играть его из кеша ?
правильно ? и подгружать области по мере надобности при сдвигах ...
то есть 5 секунд (60 кадров по 12 в секунду) вы жмете секцию до 16МБ или в 2МБ в секунду такого трафика вполне достаточно что бы качество мпега было достаточное и в итоге не требовало загруски всех 80 или 50 МБ ...
зачем вам иметь у клиента все 5000х5000 точек если показываете в конкретный момент нааамного меньше ?
ну а если правильно найти параметры кодека так и в пол мегабайта можно уложиться ....
Если пользователь не сдинулся - можно начать играть с начала , вся анимация точно так же в кэше
если сдвинулся, запросить с сервера с какого нужно кадра , и он пришлет дельту
причем я уверен что она будет маленькой при сдвигах на пиксель ...
но да все это не совсем стандартное использывание кодековhorpia Автор
26.06.2022 23:59Зачем скачивать все сразу? При открытии скачивается только те секции, что видит пользователь. При этом серев вообще не работает, все отдается с CDN.
зачем вам иметь у клиента все 5000х5000 точек если показываете в конкретный момент нааамного меньше ?
Ещё раз повторюсь, показывается только конкретно те секции, что попадают во viewport браузера. Все остальные секции не загружены и ждут, когда до них пользователь проскролирует
Barabashkad
27.06.2022 00:09-2Так а я о чем
Зачем еще бить на секции ?
Сжимать только то что видит пользователь
Один канвас один файл Никакой синхронизации
Можно отлично сжать и cdn точно так же закэширует
С переходами немного подшаманить и все ….
horpia Автор
27.06.2022 00:25+1Ещё раз... Если пользователь сдвинет на 1px сцену, если я правильно понял вас, мне нужно будет запросить с сервера новый видео файл, который будет кропить с новых координат. Верно? Если так, то это самоубийство для сервера, простите) Это какие мне мощности нужно будет резервировать на сервере, чтобы выдерживать slash-dot эффекты, которые у меня часто. Эта статься - один из примеров причины слэшдот эффекта. Да и CDN очень дорогой, с секционированием у меня условно 100МБ кеша нужно, а с тем, что вы предлагаете там не хватит и пару терабайт.
Я с вами в корень не согласен, что нужно что-либо переносить на сервер.
Barabashkad
27.06.2022 00:44Ну в общем да именно запросить новый файл
Но ведь можно не на каждый пиксел ;-)
Можно с самого начала запросить чуть больше видимой области и маленькие движения это перекроет
А если сделать привязку к каким то определенным позициям получиться что много пользователей будут запрашивать одну и туже область, а значит и cdn тут поможет.
Я конечно упустил что у вас всего 60 кадров и что можно всеее приготовить зарание, но поняв это стал еще сеньше понимать зачем вам несколько canvas ? Которые вы хотели синхронизировать …
Разбейти вашу анимацию на области скажем в 1.5 раза больше чем обычно видимая область.
Сначала разбейте от начала, а потом со сдвигом по обеим осям на половину от размера области. Получиться перекрытие . Каждую сожмите (к этому сейчас вернемся) …
Теперь прорисовка, разве нельзя декодировать не на канвас а в невидимый буфер ?
В худшем случае вам надо декодировать 4 области и скомпоновать конечную картинку.
Ну и на счет сжатии
Во сколько раз у вас получилось ужать ? Если отсчитывать от RGB по 3 байта на точку ?
Я уверен что можно сжать в 50 раз без видимых и серьезных искажений ….
horpia Автор
27.06.2022 00:51Во сколько раз у вас получилось ужать ? Если отсчитывать от RGB по 3 байта на точку ?
В исходном виде - 4.5 ГБ (если RGB брать по 3 байта на пиксель), в упакованном моем формате - 57 МБ (это уже на Brotli, который сегодня применил). Сжатие в 79 раз без искажений, только квантование цветов слегка палитру сократило, но глазу незаметно.
Разбейти вашу анимацию на области скажем в 1.5 раза больше чем обычно видимая область.
Т.е. уже секционирование (разбитие) - это норм? )) Размер секции выбран так, чтобы на мобильных экранах было всего 2-3 секции во viewport. Экраны сильной разные, это могут быть мобильники, планшеты, ПК, поэтому нет какого-то среднего значения. Размер секции я выбрал такой, чтобы компрессия была наиболее оптимальной, про это в статье написано:
Чем меньше размер секции выберем, тем меньше размер файла и мы можем адрес указывать не как 4 байта (uint32), а как 3 байта (uint24), и это хорошо сокращает размер итогового файла.
Barabashkad
27.06.2022 01:02У если ваш метод смог в 80 раз
Значит стандартные видео кодеки смогут еще :-)
разбитие изначально было допустимо, для каждого пользователя
Разбивать можно и просто но стандартным значениям, скажем 1920х1080 как hd видео, его все телефоны аппаратно точно поддерживают. Можно и 4к .
А вот с адресами секций я уже действительно потерял вас
Как десяток чисел существенно влияют на сжатие ?
horpia Автор
27.06.2022 01:08+1Значит стандартные видео кодеки смогут еще :-)
не смогут с сохранением такого же качества, как у меня :P Если не верите, то докажите, иначе получается вы критикуете приводя ложные аргументы, типа "стандартные видео кодеки смогут еще". Если не заинтересованы доказать мне мою неправоту и несостоятельность моего формата фактами какими-то, то предлагаю завершить этот увлекательны тред :D Если же вы знаете какой формат может лучше моего подойти мне - подскажите какой, буду очень признателен и в статье в UPD укажу на вас, мол, вы предложили вариант получше.
А вот с адресами секций я уже действительно потерял вас
Могу только ещё раз призвать прочесть статью, там все рассказывается, что за адресация. Даже с рисунком схемы адресации.
Barabashkad
27.06.2022 01:29-1И как вам «доказать»
Вы дадите исходную анимацию ?;-)
Вы указали только один параметр кодека , возможно если обратить внимание и на другие получится другой результат
П.с. Перечитал вдоль и поперек …. Не нашел почему так важны размеры секций для лучшего сжатия … :-)
Но если и важны , значит вам есть куда стремиться
horpia Автор
27.06.2022 01:42П.с. Перечитал вдоль и поперек …. Не нашел почему так важны размеры секций для лучшего сжатия … :-)
Если размер секции будет большой, для ссылки внутри файла нужно будет применять uint32, это 4 байта на адрес. Например, если секция 1000*1000, то максимальный размер файла (если брать 2 байта на пиксель после квантования):
1000 * 1000 * 2 * 60 кадров = 120 000 000
Для того, чтобы ссылаться на любой байт этого файла нужно адрес uint32.
Для хранения адреса в 3 байтах вместо 4 нужен размер файла меньше 2^24 = 16777216.
Если взять мой размер секции, то это
508 * 406 * 2 * 60 = 24749760
Видно, что мой размер секции больше, чем uint24, но не на много. Я взял по максимум, в реальности после RLE упаковки такой размер уже не будет и адреса все будут укладываться в uint24. Тем самым сотни тысяч повторений внутри файла будут ссылаться используя адреса из 3 байт, вместо адресов из 4. Надеюсь доступно рассказал)
Вы дадите исходную анимацию ?;-)
Без проблем. Одна доступна и по сети. Вы займетесь поиском формата, который лучше моего сожмет? Если да, то я расскажу как формировать URL для скачивания 2.2 ГБ png файлов.
Barabashkad
27.06.2022 01:50-1А зачем нужна нужна абсолютная адресация ?
Ни один из известных мне форматов так не делает ;-)
Иди естественный порядок и ненужна адресация
Или фиксированные сдвиги
Или относительные и переменная длина кодирования сдвига
Но все это другая темя
Я не собираюсь искать формат
Он и так известен вернее 3
Mpeg4
H264
H265
Я сразу выберу 264 И всего лишь подберу правильные параметры :-)
ваш пример кажется вывески, которая замылилась возьму как точку сравнения
Так что давайте ссылку , можно в личку
horpia Автор
27.06.2022 02:17+1А зачем нужна нужна абсолютная адресация ?
Ну так ведь повторяющиеся фрагменты (в который раз уточняю, вы читали статью?). Мы ищем по всем предыдущим кадрам есть ли где-то повторение фрагмента.
Так что давайте ссылку
Загружаем файл https://floor796.com/data/matrix.json
В нем массив объектов матрицы сцен. В каждом объекте есть поле preview. В нем адрес до jpg файла превью сцены. Удаляем из адреса имя файла и получаем что-то типа такого:
scene/t0l2/b1l3/fin/В этом каталоге лежат 60 png файлов этой секции. Формат имени файла - frame_%02d.png . Например
https://floor796.com/data/scene/t0r0/t4r0/fin/frame_06.png
В итоге если вы пройдете по всем объектам матрицы и скачаете все png файлы, должно быть 2.2 ГБ. Ну а дальше нужно сделать что-то, что будет лучше моего формата работать в баузерах. Буду признателен, если сможете что-то лучше предложить, чем мой велосипед ) Однако очень сомневаюсь, так как текущий формат весит 57МБ и позволяет зумить насколько угодно сохраняя пиксельную четкость.
Он и так известен вернее 3 - H265
На всякий случай проверяйте вот такой сайт перед выбором формата, так как не все поддерживается https://caniuse.com/?search=H265
wataru
27.06.2022 11:22+1Значит стандартные видео кодеки смогут еще :-)
Нет, потому что "стандартные" (поддерживаемые всеми браузерами) видо кодеки используют пиксельный формат с субсамплингом в хрома-плоскости (информация о цвете храниться с половинным разрешением). Только всякие 10-бит форматы этим не страдают, но это совсем не "стандартные" в данной предметной области кодеки.
Поэтому эти видео кодеки поставленную задачу вообще решить не могут. Сжатие может быть лучше, но всегда с недопустимой потерей качества.
Это как сжатие в /dev/null: Работает сильно круче любого алгоритма, только одно маленькое условие задачи нарушает — распаковка не для всех файлов работает.
glazzkoff
24.06.2022 20:58+1Смотрели ли вы в сторону сжатия алгоритмом zstd вместо gzip? Так как у него лучше параметры сжатия а самое главное время распаковки намного меньше, мне кажется это идеальный вариант для такой задачи.
Просто я недавно натыкался на проект zstd-wasm.
horpia Автор
24.06.2022 21:04+1неа, не смотрел) Спасибо за наводку, попробую его применить вместо gzip.
RegIon
24.06.2022 21:01+1gzip потоковый декодер есть в хроме.
можно заюзать его сразу, без pako.
https://developer.mozilla.org/en-US/docs/Web/API/CompressionStream
(про WASM я начал писать, но увидел потом что было сравнение и решил удалить)horpia Автор
24.06.2022 21:10+2да-да, так я его и заюзал. Пако как "полифил"
RegIon
24.06.2022 21:15А почему тогда сразу не присылать в бразуер чанки GZIP обжатые на стороне сервера с заголовком Compression, чтобы браузер их распаковывал пока они летят?
Тогда можно заюзать brotli, а не gzip, у него больше степень сжатия на это все.
И формально у вас кадр 100mb, так как пожатый brotil - 10mb по сети, и на js все равно прилетает 100mb.
Просто непонятно почему не отдали? Он должен сделать распаковку, и сделает ее всяко эффективнее.
(опять дубляж, но просто непонятно почему не решились)horpia Автор
24.06.2022 21:25+2Этот вариант рассматривал. Особого проигрыша в том, что я распаковываю на стороне клиента, не увидел. Стандартным API браузера или даже pako скорость распаковки gzip очень высокая. Но проблема появляется в хранении, бэкапах и CDN кеше. Если я буду хранить их в распакованном виде, то будет требовать всего больше: диска, кеша CDN, времени копирования бэкапов. Поэтому мне выгодно для роста хранить все уже сразу в сжатом виде.
Тем не менее я ещё не до конца уверен, что в будущем буду использовать gzip, так как уже даже в этих комментах мне посоветовали zstd попробовать. Возможно ещё замерю Brotli, если выигрыш будет большой, то тогда закрою глаза на проблемы с хранением больших файлов и переключу все на компрессию HTTP трафика)
RegIon
24.06.2022 21:28+1Зачем?
Настройте nginx static compression и храните их прям пожатые.
https://docs.nginx.com/nginx/admin-guide/web-server/compression/
Те они уже будут пожаты лежать.
Многие публичные сервера автоматически ресурсы типа filename.extension.gzip/br отправляют с заголовкомhorpia Автор
24.06.2022 21:36Интересно, спасибо) Если буду переключать на Brotli, то попробую nginx static compression. Хотя CDN все равно будет пережимать, и на кеш CDN это не повлияет вероятно.
orekh
24.06.2022 21:22+1Интересно было бы посмотреть как с этим пиксельартом справился бы QOI. Вроде бы он тоже почти RLE и также дополнительно хорошо сжимается стандартными brotli или gzip.
AnthonyMikh
26.06.2022 02:26Учитывая, что у автора ещё и сжатие за счёт повторяющихся последовательностей пикселей, которое добавили из-за недостаточной эффективности RLE — скорее всего, так себе покажет
RegIon
24.06.2022 21:23+1Все же продолжу про WASM.
С WASM + SIMD вы бы получили более быстрый холодный старт и более мелкий рантайм.
Да, используя SIMD нужно ногу сломать чтобы правильно векторизовать это все (так как не все могут вычислять 4 команды враз), но так как у вас RGBa, то все векторные операции с ним можно сделать в 4 раза быстрее из-за одной операции.
Пока бинариен (это то что есть wasm-opt) не умеет (или уже умеет?) сам векторизовать операции такого типа.
Я вижу у вас есть как <<, так и +*/.
Ну и не хочется Rust/C++, есть всегда:
https://www.assemblyscript.org/
Как раз сравнение генерации фрактала (без SIMD):
https://colineberhardt.github.io/wasm-mandelbrot/#WebAssembly
(но на производительных девайсах разница небольшая)horpia Автор
24.06.2022 21:27+1Спасибо за совет) Как вариант для улучшения попробую рассмотреть. Я изначально думал только на wasm все реализовать и делить потоки на нем, но что-то меня сильно отпугнула сложность реализации многопоточности rust wasm, решил оставить на потом) Т.е. сама многопоточность на rust - не проблема, но, как я понял из статей, реализация её для wasm уже не так просто. Но в rust я новичок, так что многого не знаю.
alex1478
24.06.2022 22:37+2Как я понимаю у вас нет возможности уменьшить сцену, чтобы видеть больше "комнат" на экране, во всяком случае у меня не получилось на телефоне. Планируете ли вы такую возможность добавить?
horpia Автор
24.06.2022 22:50в новом движке рендера (про который статья), я сделал 3 уровня масштабирования: 200%, 100%, и 70%. Могу ещё 50% сделать для мобильников (где экран небольшой), но для больших экранов слишком мелкий масштаб сильно повышает расход CPU, поэтому там только до 70% можно будет уменьшать.
Но если вы откроете https://floor796.com без параметра render=2, то там запустится старый движок рендера, он на mp4 и там масштаб можно уменьшать до 50%. Зато нельзя его увеличивать выше 100%, так как будет размытие (то, что я хотел исправить, разрабатывая свой формат).
alex1478
25.06.2022 15:14Нельзя ли заранее склеить уменьшенные до нужного масштаба сцены и отдавать их? То есть не просчитывать масштабирование на клиенте с кучей чанков, а в зависимости от выбранного масштаба загружать сцены, где уже 4 сцены объединены в один чанк и уменьшены в размере в два раза и тд для каждого варианта масштабирования. По тому же принципу, как это сделано на картах (Яндекс карты и тп)
horpia Автор
25.06.2022 15:20+1Да-да, думал такое сделать) Возможно в будущем именно так и сделаю уменьшение меньше 70%. Сейчас просто особо смысла нет делать сильное уменьшение, как в Гугл или Яндекс картах, блоков ещё не так много пока что
Barabashkad
26.06.2022 23:57-1ну .... на склеивание и уменьшение вы согласны на сервере ? ;-)
horpia Автор
27.06.2022 00:19+1конечно нет) Самое нелепое, что может быть, это перекидывать вычисления зума с клиента на сервер. То, что можно вычислять на клиентских машинах выгоднее на них и вычислять.
Однако в данном треде речь про подготовку видео файлов (своего формата) с заранее уменьшенной картинкой. Это как mipmap в рендеринге 3d. Подготовка делается не налету (как вы предлагали в другом треде), а 1 раз после изменения чего-либо на сцене, т.е. всего пару раз в неделю такое происходит.
Barabashkad
27.06.2022 00:24Ок
Но не важно надету или нет вы идете к решению что ненужна постоянная дележка на области а лучше делить по точке просмотра
И как это сделать для всех вариантов ?
horpia Автор
27.06.2022 00:28+2я как мог объяснил вам) Да и в статье все в целом изложено что да как. Извините, как-то лучше не могу изложить.
Делить нужно на секции, как примерно я и сделал. Так работают, например, гугл карты. Такой способ единственно верный. То, что предлагаете вы - просто расход ресурсов сервера и канала в пустую, и, как результат, сильное замедление загрузки и сильные лаги при скролировании сцены.
ShashkovS
25.06.2022 08:54Включите в браузере «версия для пк» или что-то такое. Почему-то мобильные браузеры не дают сделать сайт мелким.
Mapaxa864
25.06.2022 05:47+8Обожаю гигантские детализированные пиксельартные работы. А тут еще и с анимацией!
Потрясающий проект!
Желаю успехов и развития!
ScratchBoom
25.06.2022 09:40+3Отличная работа. Сколько времени разработки занял переход на новый формат?
horpia Автор
25.06.2022 10:02+3На удивление 1 неделю всего. Но это, наверное, 3я или 4я попытка уже. В течение последних 2 лет я все время хотел уйти с рендера на mp4 и пробовал разные варианты, все были неудачными. И вот пару недель назад ещё одна попытка перейти на canvas оказалась успешной)
Koval97
25.06.2022 11:41Я думал танцы с костылями надумают разобраться как работают анимации в простых видеоиграх, тем более раз делаете идейного наследника Club Control ("Клубные замарочки") - адаптировать их зацикленную анимацию под WebGL, и сделать первую полноценную браузерную игру, а тут...
horpia Автор
25.06.2022 15:08+8но технология видеоигр никак не подходит для такой задачи. Тут нет повторений, каждый объект уникален. По сути если бы это была игра, то пришлось бы каждый объект отдельно хранить в виде спрайтов и рендерить отдельно. У меня в исходниках все так и хранится, каждый объект - отдельный файл. Вся анимация состоит из уже более чем 480 объектов, в сумме они имеют 3900 слоев, и каждый слой имеет от 1 до 60 спрайтов. В исходном виде это весит все 15.1 ГБ (КАРЛ!) чисто в PNG формате (не путать с 2.2ГБ, про которые я в статье писал, они уже после склейки всех слоев). В прошлом я разрабатывал много игр 2d и пока что не понимаю какой именно опыт разработки видеоигр позволит 15ГБ загрузить в браузере и показывать как анимацию быстрее, чем склейка всего этого в видео форматы и просто воспроизводить их. В идеале я бы хотел воспроизводить на фрагментном шейдере, но, увы, ограничения GLSL не позволяют написать программу распаковки сильно сжатого формата, только простое сжатие можно распаковывать на GLSL, а это где-то всего 30% будет сжатие. В этой статье я рассказал как построить сжатие без видимой потери качества на 96% и почти без ощутимых последствий рендерить на CPU.
DanShaders
25.06.2022 12:26+2Шаг 5 можно делать за линейное время, например, с помощью суффиксного автомата (возможно, есть и более простые способы это сделать).
Упрощённый пример (для каждого суффикса исходной строки найти наибольший префикс, который полностью встречается раньше суффикса): https://godbolt.org/z/eeM4sccdM
horpia Автор
25.06.2022 12:33Интересно) Я пока что ускорил шаг 5 созданием простого двумерного инвертированного индекса всех пикселей во всех предыдущих кадрах. Т.е. с помощью такого индекса можно для двух подряд идущих пикселей найти все позиции во всех предыдущих кадрах, тем самым поиск очень ускоряется. Но индекс такой требует очень много памяти, правда это не проблема, ведь упаковку сцен запускаю не часто, где-то пару раз в неделю.
DanShaders
25.06.2022 12:47Да, тут тоже будет проблема с памятью. В частности, текущая версия использует 1024*вес строки памяти, но можно дооптимизировать константу до ~10.
И конечно, без данных нельзя предсказать будет ли вообще моё решение работать быстрее вашего)
wataru
25.06.2022 15:26+3Например, H.264 при самом лучшем качестве (crf=1) почему-то все равно делает ужасное искажение красных линий на темном фоне:
Это потому что видео чаще всего кодируется в YUV 4:2:0 пиксельном формате: яркость (luma) закодирована в оригинальном разрешении, а вот цвет (chroma) — с половинным разрешением. Это как в mp3 выбрасываются неразличимые ухом звуки, так и во всех современных видео кодеках выбрасываются невидимые (по идее) глазу детали. Если пошаманить с пиксельным форматом, то искажение исчезнет. Всякие High444p h264 профили не уменьшают нигде разрешение. Но вот эти профили не во всех браузерах поддерживаются, насколько я знаю.
wilerat
26.06.2022 09:19+2Пару месяцев назад, на реддите, происходил масштабный эвент вроде боёв за пиксели.
То есть заходя по ссылке, пользователь попадал на холст, на котором он мог изменить цвет одного пикселя раз в 5 минут.
И самое интересное было, что отрисовка происходила в реальном времени, рендерилась быстро, даже на телефонах. И можно было просто наблюдать за изменениями пикселей.Визуально было чем то похоже на вашу текущую анимацию.
Как это выглядело для пользователя, ну например можно тут посмотреть
https://youtu.be/Tl9jS8r5mjQ?t=617Как это работало, есть небольшая статья (и возможно где то можно ещё найти)
https://www.redditinc.com/blog/how-we-built-rplace/Показалось, что ваша отрисовка пиксельной анимации как то перекликается с этим, и, возможно, можно сделать отрисовку на канвасе отдельных пикселей.
Ну или просто подчерпнуть что-то из той статьи.
raamid
Очень интересно. А можно ли где-то посмотреть результат?
horpia Автор
я боюсь как бы за рекламу не сочли) это бесплатный проект, так что вот ссылка на новый рендер с мои форматом видео и канвасом https://floor796.com/?render=2 , а просто по ссылке https://floor796.com/ пока что открывается формат прошлый, на mp4 файлах.
Weron2
Супер! Очень круто, я даже пасхалку нашел)
Xobotun
Да там всё из пасхалок состоит! :D
Или вы какую-то прямо пасхально пасхальную нашли? Даже интересно.
horpia Автор
пока что 2 интерактивные пасхалки есть. Обе обвел кружком)
Xobotun
Race-796 есть в чейнджлоге, а вот hev-charger действительно пасхалист. Спасибо, что сделали указатель, откуда были взяты персонажи: некоторых я узнаю, а с некоторыми частями культуры познакомиться не довелось.
Кстати, я не думаю, что сделаю что-то морально плохое, поделившись ссылкой, верно?
werton
Круто, а "HA-Men" это опечатка или так и задумано? Еще "Mem реклама-мака" ссылается на удаленное видео.
horpia Автор
Спасибо! HA-Men поправил на HE-Man, это была опечатка)
И мем из рекламы мака заменил на другое видео
GeneAYak
такое рекламировать не только не стыдно, но и почетно
thatsme
Офигенно! За последние пол года, лучшая статья. Отличная работа. Респект. Добавил в закладки.
Veber
Да, раньше качественных статей было вагон. Вот думаю даже сделать подборку лучших за год с 2009 по 2019, чтобы было что достойное почитать.
SergeiMinaev
Это охрененно! И статья огонь и результат.