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

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

Основы анимации и сжатия

Скелетная анимация — довольно простая тема, если забыть о скиннинге. У нас есть концепция скелета, содержащего преобразования костей персонажа. Эти преобразования костей хранятся в иерархическом формате; по сути, они хранятся как дельта между своей глобальной позицией и позицией родителя. Терминология здесь сбивает с толку, потому что в игровом движке локальным часто называют пространство модели/персонажа, а глобальным — мировое пространство. В терминологии анимации локальным называется пространство родителя кости, а глобальным — или пространство персонажа, или мировое пространство, в зависимости от того, есть ли движение корневой кости; но давайте не будем об этом особо беспокоиться. Важно то, что преобразования костей хранятся локально относительно их родителей. Это имеет множество преимуществ, и особенно при смешении (блендинге): если бы при смешении двух поз кости были глобальными, то они бы линейно интерполировались в позиции, что приводило бы к увеличению и уменьшению костей и деформации персонажа. А если использовать дельты, то смешение выполняется от одной разности к другой, поэтому если дельта преобразования для одной кости между двумя позами одинакова, то длина кости остаётся постоянной. Думаю, что проще всего (но не совсем точно) воспринимать это так: использование дельт приводит к «сферическому» движению позиций костей при смешении, а смешение глобальных преобразований приводит к линейному движению позиций костей.

Скелетная анимация — это просто упорядоченный список ключевых кадров с (обычно) постоянной частотой кадров. Ключевой кадр — это поза скелета. Если мы хотим получить позу, находящуюся между ключевыми кадрами, то сэмплируем оба ключевых кадра и выполняем смешение между ними, используя в качестве веса смешения долю времени между ними. На рисунке ниже показана анимация, созданная с частотой 30fps. Анимация имеет в сумме 5 кадров и нам нужно получить позу спустя 0,52 с после начала. Поэтому нам нужно сэмплировать позу в кадре 1 и позу в кадре 2, а потом выполнить смешение между ними с весом смешения примерно 57%.

Пример анимации из 5 кадров и запрос на получение позы в промежуточное время кадра

Имея указанную выше информацию и считая, что память для нас не проблема, идеальным способом хранения анимации было бы последовательное сохранение позы, как показано ниже:

Хранение данных простой анимации

Почему это идеально? Сэмплирование любого ключевого кадра сводится к простой операции memcpy. А сэмплирование промежуточной позы требует двух операций memcpy и одной операции смешения. С точки зрения кэша мы копируем при помощи memcpy два идущих по порядку блока данных, то есть после копирования первого кадра в одном из кэшей уже будет второй кадр. Вы можете сказать: постой-ка, когда мы выполняем смешение, нам нужно смешивать все кости; что, если большая их часть не меняется между кадрами? Разве не лучше будет хранить кости как записи и смешивать только изменившиеся преобразования? Ну, если это реализовать, то потенциально может возникнуть чуть больше промахов кэша при считывании отдельных записей, а затем нужно будет отслеживать, какие преобразования необходимо смешивать, и так далее… Смешение может показаться слишком трудоёмкой работой, но по сути это применение одной инструкции к двум блокам памяти, уже находящимся в кэше. Кроме того, код смешения получается относительно простым, часто это просто набор SIMD-инструкций без ветвления, и современный процессор обработает их за считанные мгновения.

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

Кости имеют постоянную длину
- Персонажи в большинстве игр не растягивают кости, поэтому в пределах одной анимации записи преобразований постоянны.
Мы обычно не изменяем масштаб костей
- Масштаб редко применяется в игровых анимациях. Он довольно активно используется в фильмах и VFX, но совсем мало в играх. Даже когда он используется, обычно применяют одинаковый масштаб.
- На самом деле, в большинстве созданных мной анимаций во время выполнения я пользовался этим фактом и хранил всё преобразование кости в 8 переменных float: 4 на поворот кватерниона, 3 на перемещение и 1 на масштаб. Это значительно снижает размер позы во время выполнения, обеспечивая повышение производительности при смешении и копировании.

С учётом всего этого, если посмотреть на исходный формат данных, то можно увидеть, насколько он неэффективно тратит память. Мы дублируем значения перемещения и масштаба каждой кости, даже если они не изменяются. И ситуация быстро выходит из-под контроля. Обычно аниматоры создают анимации с частотой 30fps, а в играх AAA-уровня в персонаже обычно есть около 100 костей. Исходя из этого объёма информации и формата из 8 float, нам в результате требуется около 3 КБ на позу и 94 КБ на секунду анимации. Величины быстро накапливаются и на некоторых платформах могут запросто забить всю память.

Поэтому давайте поговорим о сжатии; пытаясь сжимать данные, нужно учитывать несколько аспектов:

Коэффициент сжатия
- Насколько нам удалось снизить объём занимаемой памяти
Качество
- Сколько информации мы потеряли из исходных данных
Скорость сжатия
- Сколько времени требуется для сжатия данных
Скорость распаковки
- Насколько медленно выполняется распаковка и считывание данных по сравнению с несжатыми данными.

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

Также чрезвычайно важно заметить, что не стоит недооценивать влияние сжатия анимаций на производительность: в одном из моих предыдущих проектов скорость сэмплирования снизилась примерно на 35%, а также возникли некоторые проблемы с качеством.

Когда мы начинаем работать со сжатием данных анимаций, следует учитывать две основные важные области:

Насколько быстро мы можем сжимать отдельные элементы информации в ключевом кадре (кватернионы, float и т.п.).
Как мы можем сжать последовательность ключевы кадров, чтобы удалить избыточную информацию.

Дискретизация данных

Практически весь этот раздел можно свести к одному принципу: дискретизируйте данные.

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

Дискретизация Float

Когда дело касается дискретизации значений float, то мы стремимся взять это значение float и представить его как integer с использованием меньшего количества бит. Хитрость заключается в том, что integer на самом деле может представлять не исходное число, а значение в дискретном интервале, сопоставленном с непрерывным интервалом. Обычно при этом используется очень простой подход. Для дискретизации значения нам сначала требуется интервал для исходного значения; получив этот интервал, мы нормализуем исходное значение по этому интервалу. Затем это нормализованное значение умножается на максимальное значение, возможное для нужного нам заданного выходного размера в битах. То есть для 16 бит мы умножаем значение на 65535. Потом получившееся значение округляется до ближайшего integer и сохраняется. Это наглядно показано на изображении:

Пример дискретизации 32-битного float в беззнаковый 16-битный integer

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

Я не буду приводить примеров исходного кода, потому что существует достаточно удобная и простая библиотека для выполнения основных операций дискретизации, которая является хорошим источником по этой теме: https://github.com/r-lyeh-archived/quant (я бы сказал, что не стоит использовать её функцию дискретизации кватернионов, но подробнее об этом позже).

Сжатие кватернионов

Сжатие кватернионов — достаточно подробно изученная тема, поэтому я не буду повторять то, что другие люди объяснили лучше. Вот ссылка на пост о сжатии снэпшотов, в котором представлено самое лучшее описание по этой теме: https://gafferongames.com/post/snapshot_compression/.

Однако у меня есть, что сказать по теме. В постах bitsquid, где говорится о сжатии кватернионов, предлагают сжимать кватернион до 32 бит, используя примерно по 10 бит данных на каждую компоненту кватерниона. Именно это делает библиотека Quant, потому что она основана на постах bitsquid. По-моему, такое сжатие слишком велико и в моих тестах оно вызывало сильную тряску. Возможно, авторы использовали менее глубокие иерархии персонажа, но если перемножить 15 с лишним кватернионов из моих примеров анимаций, то совокупная погрешность получается довольно серьёзной. По моему мнению, абсолютным минимумом точности является 48 бит на кватернион.

Уменьшение размера вследствие дискретизации

Прежде чем мы начнём рассматривать различные способы сжатия и расположения записей, давайте посмотрим, какой тип компрессии мы получим, если просто применим дискретизацию в исходной схеме. Мы воспользуемся тем же примером, что и раньше (скелет из 100 костей), поэтому если использовать 48 бит (3 x 16 бит) на кватернион, 48 бит (3×16) на перемещение и 16 бит на масштаб, то в сумме для преобразования кости нам понадобится 14 байт вместо 32 байт. Это 43,75% от исходного размера. То есть для 1 секунды анимации с частотой 30FPS мы снизили объём с примерно 94 КБ до примерно 41 КБ.

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

Сжатие записей

Здесь всё становится очень сложным, особенно когда разработчики начинают пробовать такие приёмы, как уменьшение ключевого кадра, подбор кривых (curve fitting) и т.д. Также на этом этапе мы по-настоящему начинаем снижать качество анимаций.

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

Сохранение данных поз костей как записей

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

Сделав это, мы можем использовать и другие способы дальнейшего снижения занимаемой памяти. Первый — начать отбрасывать кадры. Примечание: для этого не требуется формат записей и этот способ можно применить и в предыдущей схеме. Этот способ работает, но приводит к потере мелких движений в анимации, потому что мы отбрасываем большую часть данных. Этот приём активно использовался на PS3, и иногда нам приходилось опускаться до безумно низких частот сэмплирования, например, до 7 кадров в секунду (обычно для не очень важных анимаций). У меня от этого остались плохие воспоминания, как программист анимаций я чётко вижу потерянные детали и выразительность, но если смотреть с точки зрения системного программиста, то можно сказать, что анимация «почти» такая же, ведь в целом движение сохраняется, но при этом мы экономим много памяти.

Давайте опустим этот подход (по-моему, он слишком деструктивен) и рассмотрим другие возможные варианты. Ещё один популярный подход заключается в создании кривой для каждой записи и выполнении уменьшении ключевых кадров на кривой, т.е. удалении дублируемых ключевых кадров. С точки зрения игровых анимаций, при таком подходе записи перемещения и масштаба великолепно сжимаются, иногда сводясь к одному ключевому кадру. Это решение недеструктивно, но требует распаковки, потому что каждый раз, когда надо получить преобразование, мы должны вычислять кривую, потому что мы больше не можем просто перейти к данным в памяти. Ситуацию можно немного улучшить если вычислять анимации только в одном направлении и хранить состояние сэмплера каждой анимации для каждой кости (т.е. откуда брать вычисление кривой), но за это приходится расплачиваться увеличением объёма памяти и значительным повышением сложности кода. В современных системах анимации мы часто не воспроизводим анимации с начала до конца. Зачастую при определённых смещениях времени они выполняют переходы к новым анимациям благодаря таким вещам, как синхронизированное смешение или согласование фаз. Часто мы сэмплируем отдельные, но не последовательные позы для реализации таких вещей, как смешение прицеливания/взгляда на объект, а часто анимации воспроизводятся в обратном порядке. Поэтому не рекомендую использовать такое решение, оно просто не стоит хлопот, вызванных сложностью и потенциальными багами.

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

Все эти аспекты раскрыты в постах Riot/BitSquid и Николаса (см. ссылки в начале моей статьи). Я не буду подробно о них рассказывать. Вместо этого я расскажу о том, что я решил по поводу сжатия записей…

Я… решил не сжимать записи.

Прежде чем вы начнёте махать руками, позвольте мне объяснить…

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

Такая ситуация возникает для большинства костей примерно в 95% наших анимаций, поэтому в конечном итоге мы можем значительно снизить занимаемую память, абсолютно не теряя при этом в качестве. Это требует работы с точки зрения создания контента (DCC): мы не хотим, чтобы в рабочем процессе создания анимаций у костей возникали незначительные перемещения и изменения масштаба, но подобная выгода стоит лишних затрат.

В нашем примере анимации есть только две записи с перемещением и нет записей с масштабом. Тогда для 1 секунды анимации объём данных снижается с 41 КБ до 18,6 КБ (то есть до 20% от объёма исходных данных). Ситуация становится ещё лучше при увеличении длительности анимации, мы затрачиваем ресурсы только на записи поворотов и динамического перемещения, а затраты на статичные записи остаются постоянными, благодаря чему в длинных анимациях экономия оказывается больше. И нам не приходится испытывать потери качества, вызванные дискретизацией.

С учётом всей этой информации моя окончательная схема данных выглядит так:

Пример схемы сжатых данных анимаций (3 кадра на запись)

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

В дополнение к данным анимаций, хранящимся в одном блоке памяти, у меня также есть параметры сжатия для каждой записи:

Пример параметров сжатия записей из моего движка Kruger

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

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

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

Руководство по сжатию скелетных анимаций