Но была и проблема: типичное игровое разрешение того времени — 320 на 200 точек при палитре из 256 цветов, что даёт нам 64 килобайта на кадр или полтора мегабайта на 25 кадров, при скорости чтения с компакт диска в 150 килобайт в секунду. Т.е. видео надо было жать и жать довольно сильно, а сжав, потом надо суметь декодировать, ведь мы помним, компы были слабенькие и декодирование, например, MPEG им было вообще не по силам. Тем не менее производители видео игр успешно решили проблему недостаточной производительности породив заодно множество видео-кодеков и игровых видео-форматов, некоторые из которых могли проигрываться аж 286-м (прописью: двести восемьдесят шестым) процессором.
Так началась эпоха FMV игр (Full Motion Video Games). Я думаю, многие помнят её ярких представителей: Crime Patrol от American Laser Games, Lost Eden, Cyberia, Novastorm и даже Command & Conquer, в который многие играли только ради видеовставок между миссиями. В те времена выглядело это очень круто. Вау! Вау! Ну а мне было интересно, как же они закодировали это видео, в книжках о мультимедиа приводили то же описание проблемы, что и я выше, но ничего внятного о методах сжатия не писали, видимо, авторы в этом мало понимали и пересказывали какие-то сомнительные слухи.
На самом деле, всё оказалось очень просто, методов было всего три штуки и все очень простые.
Но перед тем как мы перейдём к самим методам, были ещё повсеместно использовавшиеся ухищрения. Во-первых, конечно, ни о каких 25 кадрах в секунду не могло быть и речи. Все поголовно резали fps, вплоть до 10 кадров в секунду (интерактивные тиры Americal Laser Games). 12, 14, 15 fps — типичные фрэйм рэйты. Во-вторых, конечно же, разрешение картинки резали почти всегда, ведь если с каждой стороны от кадра отрезать по 10 пикселей (по 3%), то это даст ~15% выигрыша. Ну а если разрешение понизить до 256 на 144 точек, как это сделали разработчики Novastorm, то выигрыш составит практически половину.
И так, смотрите, если взять 256 на 144 точи и 14 кадров в секунду, то это даст нам пол мегабайта несжатого видео вместо полутoра мегабайт, что обнадеживает.
1. Грубая сила и невежество (RLE, LZ)
Был такой формат BFI, что расшифровывалось разработчиками как «Brute Force & Ignorance». К этой группе относятся различные облегченные вариации по мотивам RLE и LZ алгоритмов. Это может показаться удивительным, но зачастую этого было достаточно, ну а если например в динамичной сцене сжатия не хватало, то всегда можно начать пропускать кадры, или же ещё сильнее понизить разрешение картинки в два, а то и в четыре раза (MM). Видео в тирах American Lazer Games, играх серии Wing Commander, игре Lost Eden и других играх студии Cryo закодированы именно так.
Обратите внимание на характерные для Lossy RLE горизонтальные полосы.
2. Векторное квантование (VQ)
Идея простая: возьмем скажем восемь идущих друг за другом кадров и нарежем их все на блоки по 4x2 пикселя, при разрешении картинки в 320 на 156 пикслей это даст нам 50 тысяч 24-х мерных векторов (8 пикселей в блоке, три цветовых компонента у каждого пикселя). Идущие друг за другом кадры весьма вероятно имеют много общего, поэтому среди этих векторов окажется множество близких друг к другу. Далее делим эти вектора на 4096 групп, для каждой группы вычисляем центроид. Из центроидов формируем codebook, ну а кадры записываем в файл в виде цепочек 12-и битных ссылок на codebook. Вместе это нам даёт примерно 13 килобайт на кадр, что в принципе по силам для двухскоростного сидирома.
Примерно такой подход использовался в ранних играх серии Command & Conquer.
Декодирование, очевидно, очень быстрое и дешёвое, но вот качественно закодировать видео данным методом очень непросто. Не у всех, кто использовал VQ, это получилось хорошо. Вот полюбуйтесь на скриншоты игры Creature Shock.
3. Block Truncation Coding (BTC)
Тут опять всё просто, ничего сложного в 90-х не применяли. Чтобы сохранить 256-и цветное изображение нам надо по байту на каждый пиксель. А давайте уменьшим количество цветов, допустим, до двух, теперь на пиксель нужно по биту, мы получили восьмикратное сжатие и картинку кошмарного качества. Что можно с этим сделать? Просто применим данный подход не ко всему изображению целиком, а к небольшим блокам, ведь с большой вероятностью все цвета в рамках достаточно маленького блока близки друг другу. Режем картинку на блоки, скажем, 4 на 4 пикселя и для каждого из них сохраняем два цвета (его персональную палитру) и ещё 16 бит ссылок на эти цвета. Всего 4 байта на блок из 16-и пикселей, т.е. получили 4-х кратное сжатие. Но если вдруг окажется, что двух цветов для данного блока мало, то мы можем сохранить и четыре цвета — это даст нам двукратное сжатие. А можно разделить блок на 4 блока меньшего размера и для каждого из них вычислить по два цвета.
Этот метод был очень популярен, он прост и быстр в кодировании и декодировании, обеспечивает разумное качество, легко реализуем. В игре Novastorm используются блоки 8 на 8, которые могут иметь палитру из 2, 4, 8 цветов. В известной игре Z тоже используется нарезка на блоки по 8 на 8 пикселей и деление их на части при необходимости (JV). В Cyberia — комбинированный подход: используется как деление на меньшие блоки так и палитры разного размера (C93, M95).
Оригинальный BTC, про который можно прочитать в википедии, разработан для сжатия полутоновых изображений, цвета вычисляются таким образом чтоб сохранить среднее, и стандартное отклонение яркости в блоке. Должен заметить, что такой подход даст результаты ужасающего качества. Правильная палитра должна минимизировать сумму квадратов отклонений — вот тогда получается красиво.
Конечно, все использовали межкадровое сжатие в самом его примитивном виде зачастую даже без предсказания движения. Ни о какой коррекции яркости в палитризованых видео не могло быть и речи, поэтому на сценах с затемнением визуально падала частота кадров. Это очень было заметно в роликах самой первой Need For Speed, а я-то думал, что у меня проблемы с моим 4-х скоростным сидиромом. Даже пытался вернуть его в магазин.
Кадр из игры Rebel Assault. Блочность, характерные для VQ повторы блоков. Блоки 4 на 4, преимущественно двухцветные, скорее всего codebook дополнительно закодирован с помощью BTC.
Как только позволили вычислительные мощности, все начали использовать кодеки на основе дискретного косинусного преобразования, а потом и вовсе перешли к видеовставкам на игровом движке, эпоха FMV игр завершилась.
Есть люди, которые исследуют старые видео форматы, реверсинженерят кодеки, бережно собирают и сохраняют эти знания. Очень рекомендую посетить их сайт wiki.multimedia.cx. Масса информации для всех интересующихся вопросами сжатия аудио и видео, в том числе и о современных кодеках.
В статье использованы скриншоты с сайта mobygames.com.
Комментарии (41)
AllexIn
08.04.2017 11:18эпоха FMV игр завершилась
И очень жаль. Упомянутя ваше серия C&C имела просто шикарные видеовставки. И это очень сильно добавляло атмосферы. МОжет поэтому RTS и перестал быть популярным? :)
yannmar
08.04.2017 15:26И не говорите! Вставки были хороши. Но вот в первом варкрафте только интро и было, а игра тоже была весьма играбельной.
MarkusD
08.04.2017 15:57+1По поводу спада популярности RTS есть в сети вот такие мысли (перевод).
AllexIn
08.04.2017 18:50Спасибо.
Интересно.
Но очень печально. Особенность восторог экспертов по поводу будущего RTS с тыщями юнитов…
Печалит полное отсутствие игр с адекватным сюжетом и интересной компаний.
Случайно набрел на Mental Omega. Как глоток свежего воздуха прям.
Alexey2005
08.04.2017 11:24+2Зато современные игры похоже сжатием вообще не заморачиваются. Вот серьёзно, что нужно напихать в игру, чтобы она весила 30Гб, при этом сжимаясь архиватором до 15? А ведь для современных игр 30Гб далеко не предел.
SHVV
08.04.2017 12:18+7Текстуры, текстуры и ещё раз текстуры, много моделей, чуточку анимаций и щепотка кода. Не считая текста.
Карты сейчас большие, оттекстурированы так, что даже если приблизится вплотную к поверхности, она останется достаточно чёткой для Full HD разрешения. А чтоб всё это выглядело красиво, на каждый треугольник надо не одну, а несколько текстур: Albedo, Reflectivity, Glossness, Normal, Ambient, Opacity, Emissive,… Это не считая предрассчитанных карт освещения и Light Prob-ов с HDR-ом.
И это ещё при том, что текстуры таки хранят со сжатием, но достаточно быстрым, чтоб все эти гигабайты можно было загрузить не напрягая игрока.
Сравните это с одной единственной текстурой для игр 90-х с таким низким разрешением, что даже квадраты на них было видно за десяток метров на разрешении 320х200. А карты были гораздо меньше.SHVV
08.04.2017 12:26+2Да, ещё про музыку со звуками забыл. Но их в любом случае гораздо меньше, чем текстур.
perfect_genius
08.04.2017 18:07+2Mortal Kombat — 10 гигов, половина — ролики
Metal Gear Rising — 25 гигов, ролики — на 17 гигов
FINAL FANTASY XIII — 57 гигов, ролики на 30 гигов
Такие же дела у продолжений FF13, у MKX и NieR:Automata…SHVV
08.04.2017 19:13Честно говоря, давно не играл в игры с большим количеством пререндеренных роликов. В последнее время большинство делают ролики на игровом движке. Так что, перечисленные вами экземпляры, скорее исключение, чем правило, ИМХО.
VioletGiraffe
08.04.2017 20:58Mass Effect Andromeda — 50 ГБ, роликов не на дижке очень мало и они короткие. Думаю, всё-таки текстуры.
perfect_genius
08.04.2017 21:57Репак — 37.5 гигов — может как раз пожались ролики на движке? =D
VioletGiraffe
08.04.2017 23:45Надо описание репака смотреть. Обычно же в репаках только lossless-сжатие.
perfect_genius
09.04.2017 10:18Я не саркастировал, действительно предположил так. Да сжатие без потерь там.
VioletGiraffe
09.04.2017 11:03Я тоже не саркастировал :) Ну не в MJPEG же у них ролики, чтоб их можно было без потерь пожать на 30-50%?
AllexIn
08.04.2017 15:02Конечно с сжатием не заморачиваются.
Вернее, заморачиваются, но не так как вы этого ждете.
Данные делают в CPU/GPU Friendly виде. С одной стороны, чтобы они стали меньше, с друго й- чтобына леты их быстро и просто распаковывать.
Естественно, архиватор, который жует сотню мегабайт в секунду совершенно не годитс ядля задачи реалтайм загрузки.
yannmar
08.04.2017 15:33-1Старые fmv игры кстати тоже архиватором раза в два сжимаются, а то и больше. Применявшиеся алгоритмы кодирования адаптировались не под максимальное сжатие, а чтоб получить хоть какое-то сжатие, уложиться в скорость чтения типового сидирома и при этом быстро декодироваться на слабом железе. Такой вот баланс приходилось соблюдать. Например, деревья Хаффмана почти никогда не использовались, скорее всего именно по причине производительности.
Krypt
08.04.2017 16:43Деревья Хаффмана несколько медленнее RLE, но при этом сами по себе довольно бесполезны для сжатия видео. То есть вам придётся потратить процессорное время ещё и на преобразование данных.
yannmar
08.04.2017 17:07Не, я не соглашусь насчёт бесполезности. И кое-где они даже использовались, в уже упоминавшемся smacker-е например и для кодирования видео второй кваки (но тут уже речь не о 286-х или 386-х CPU). Ну и, конечно, по скорости декодирования мало что может потягаться с RLE.
Krypt
08.04.2017 19:20Коды бесполезны для сжатия не преобразованного потока, по сути они просто переназначают коды цветов точек, что даёт сжатие ну может быть до 80% от изначального размера, по крайней мере в моих экспериментах. Что явно не решает задачу уложиться в скорость чтения CD Rom.
С другой стороны коды поверх RLE дают те же самые 80%, но уже относительно потока данных RLE, фактически улучшая общий уровень сжатия.yannmar
08.04.2017 19:24Ну Хаффман, конечно, обычно используют как дополнительный метод. Но минус 20% это очень неплохо, ведь тогда можно поднять частоту кадров или увеличить площадь кадра. Или записать больше видео на диск.
Amomum
08.04.2017 16:47+1А не подскажите, может быть сейчас где-нибудь есть энкодеры/декодеры в эти форматы? Или только самому брать и воспроизводить по описаниям?
Было бы интересно поиграться.yannmar
08.04.2017 17:00ffmpeg много игровых форматов умеет декодировать https://ffmpeg.org/general.html#File-Formats. Для некоторых форматов (например VQA), можно нагуглить сторонние энкодеры. Но сам я ни то ни другое не пробовал
xtala
08.04.2017 21:13Так началась эпоха FMV игр (Full Motion Video Games).
Это было просто ужасно, мне сразу вспоминается рвущий душу визг миксера в глазнице и кровавые ошметки от глаза на советских обоях.
Рассказывайте детям красивые и добрые сказки на ночь. Например как добрый молодец Кармак замутил в кваке офигенные для того времени эффекты освещения, хакнув 3d аскелераторы заранее расчитанными таблицами.yannmar
08.04.2017 21:40+1Извините, я просто из очень бедной семьи. Мои родители не могли позволить себе UltraHD, Core i7 и блюрей в 95-м.
thealfest
08.04.2017 21:41+2кому интересна тема — советую почитать 8088 Domination Post-Mortem
yannmar
09.04.2017 00:16+1Чума! Спасибо! Этот парень знатный читер! Кликабельная ссылка: https://trixter.oldskool.org/2014/06/19/8088-domination-post-mortem-part-1/
Indever2
09.04.2017 16:07Очень интересная статья, даже для меня, человека, который ровным счетом ничего не смыслит в кодировании видео :)
Еще и ностальгия взяла… :)
daggert
09.04.2017 21:34Жаль только что многие писали свои реализации данных алгоритмов сжатия, да еще и чуток меняя контейнер и теперь вскрыть и перекодировать видео не реально…
PS: смотрит с ностальгией на первый Parkan и пытается расковырять его видеовставки.
Nomad1
Обязательно надо упомянуть про Smacker. Он с какого-то года стал стандартом де-факто: блоки 4х4, 256-цветная адаптивная палитра (менялась по ходу воспроизведения) и прочие радости.
yannmar
Ага. Несомненно кодек тогоже класса и предназначения, популярный, но очень неоднозначный.
Nomad1
Некоторые использовали, например Neverhood. Но многие делали свое что-то, либо придерживались стандартных решений, вроде QT контейнера с каким-либо распостраненным кодеком.
Зато после Smacker индустрия уже хорошо подсела на RAD Game Tools (ну и их Miles Sound System) и потому появление Bink восприняли просто с восторгом. Тогда же появились ролики для игр с разрешением выше MCGA, почти без апскейлинга. Да что говорить, список игр с его использованием превышает все разумные пределы. Некоторые проекты даже использовали lossless .BIK файлы вместо покадровой анимации!
Можно сказать, что до появления MPEG в играх этот формат доминировал.
yannmar
Да, всё так. Но это всё применялось для вспомогательных видеовставок (в том числе и в Neverhood), видео уже не было основным элементом игрового процесса, производительность подросла и позволяла в рилтайме рендерить относительно приличную графику.
mistergrim
Использовался в Wetlands, например. Это что сходу вспомнилось.
yannmar
Да, вы правы. Не довелось поиграть.
Halt
Smacker применялся в Starcraft для cut сцен и выглядел весьма неплохо для того времени.