On FMV games video compression

Back in the day I’ve stumbled on a post called Archaic Video Compression Algorithms of FMV Games Era (in Russian) giving a concise review of VGA era video. For a long time I wanted to discuss it but I lost the link to it and managed to locate it just recently.

For those unable to read Russian here’s a gist of it: all the variety of those formats used just three methods to compress video, those methods being lossless redundancy removal via RLE or LZ77-based method (Huffman codes not employed), vector quantisation, and block truncation coding. Inter-frame compression was rather primitive, often without any motion predictions; fade-ins/outs were not handled either. And later, when computers became powerful enough, everybody switched to DCT coding and later to in-engine animation.

It is a very good first approximation but as a person who looked into several formats myself and even documented a couple of them, I have something to add or correct.

First of all, ‘archaic’ means something not merely old but also not in common use—and that does not apply neither to LZ77 (which is still the base of most of the practical compressors and archivers; and there’s WebP using its variant in lossless mode) nor vector quantisation (even if it’s mostly employed in texture compression nowadays).

Second, I consider block truncation coding to be a specialised form of vector quantisation for a case of two colours per block. And considering that the input data could be palettised already it’s more likely the encoder searched for the most fitting two colours in the palette instead of generating two RGB triplets and handing it all to the palettisation process.

Third, I’d argue that back in the day codecs did not need sub-pixel motion compensation and motion vectors were often not needed since you could simply code an offset in LZ77 compression. And some of the codecs allowed copying data from either already decoded parts of the current frame or some not yet touched part (or any part in some cases) of the previous frame. This archaic method of copying from already decoded part of the frame is present in AV1 for example (under IntraBC name).

Fourth, I think that recursive block division deserves to be mentioned there.

A minor nit would be that even if very few codecs supported explicit fading, a lot of them had support for palette change event (partial or full). Yet it mostly depended on people developing the format and the encoder for it how well it was handled.

So in my opinion the final list of the techniques most FMV games of the VGA period used should look like this:

  • lossless data compression with RLE or LZ77-based method
  • vector quantisation—both whole tiles and inside single tile;
  • recursive block splitting (either horizontal/vertical or as a quadtree);
  • and fullpel motion compensation usually done by skipping pixels, blocks, or reusing some already decoded region.

And typical video codec of that era should look like one of those two:

  1. line-based codec employing RLE, probably with skips for inter-frames and optional LZ77 compressing of whole frame data afterwards (or extending LZ77 approach to work with the forward data in the buffer as well);
  2. tile-based codec usually working with 4×4 tiles, employing vector quantisation to paint the tile with 1-8 colours, sometimes sub-dividing tile for better detail preservation, sometimes having a dictionary of tile configurations, sometimes even employing block-based motion compensation; those codecs usually employ 1-4 byte opcodes to code the tile type of whole sequences of tiles of the same type.

Of course there are deviations from those two schemes but the majority of game codecs of that era should follow either of those two designs.

Later, as the original article said, those codecs were supplanted by DCT-based ones (I’ve seen the ones based on MJPEG and MPEG-1/2; and there’s hybrid Bink). On the other hand, DCT-based Bink2 is still in use.


Overall, if you look at game formats section in the wiki you’ll see a lot of various formats and many of them are built on a handful of the idea described above while still being quite different from each other. Originality lies not only in the methods employed but also in how you combine them together. And the modern codecs are the example of how different organisations build essentially the same codec using slightly different methods. MPEG-5 LCEVC was a nice change though.

3 Responses to “On FMV games video compression”

  1. Thanks for the memories! I was actually thinking about all this same stuff recently as an offshoot of a Discord discussion about whether there was ever Indeo acceleration hardware. This got me to thinking about the parallel evolution of algorithms for low-end PCs vs. the transform-based MPEG lineage.

    I started thinking that this history should be summarized and written about for posterity. Thanks for handling it.

  2. e71 says:

    This is relevant:

    https://www.youtube.com/watch?v=IehwV2K60r8

    Remember the Sonic 3d blast on the Saturn that had the TrueMotion 1 Codec? Well, they also made a Genesis version of the same game. Since the Genesis cartridges didn’t have enough space for a TrueMotion video, they had to pick a different FMV and use some compression tricks to store it, like one described here
    In this one, they used RNC, which is a compression algorithm that is offshoot of LZ.

    The codecs all being similar remind me of how Intel and AMD would steal each other’s CPU implementations and while both companies knew they didnt do anything about it.

  3. Kostya says:

    Interesting.

    RNC is rather famous compressor used to pack various game resources (like deflate) but mostly not on IBM PC. Reduced resolution was a common trick as well.

    As for Intel vs. AMD situation, they both were founded by engineers from Fairchild and initially Intel supported AMD as the second supplier of x86 CPUs for IBM PCs. Later though while their CPUs looked the same they were quite different internally as they were designed by different engineers with different views. To the point that current 64-bit x86 CPU ISA was designed by AMD (Intel wanted to replace with Itanic but the demand for x86 legacy support was stronger and AMD won). Still, it’s frenemies working on the implementation of the common ISA standard instead of competitors trying to make the same but slightly different codec.

Leave a Reply