Category Archives: Vector Quantization

Sega CD FMV VQ Analysis

I have amassed quite a collection of Sega CD titles over my years of multimedia hacking. Since it was an early CD-based console, I reasoned that at least some of the games would contain full motion video (FMV). In fact, essentially all Sega CD games fall into one of the following 2 categories:

Standard 16-bit Sega Genesis-type games that were enhanced by a Red Book CD audio soundtrack
Games that were driven entirely by very low-quality FMV

Mad Dog McCree (Sega CD version) -- Mayor's daughter

Screenshot of Mad Dog McCree for the Sega CD, an FMV-driven FPS

Many Sega CD games, particularly those published by Sega itself, contain many large files with the extension .sga. I have never made much headway on understanding any of these files, save for the fact that many of them use sign/magnitude 8-bit PCM audio. As for the video codec, “Cinepak” or “Cinepak for Sega” is often thrown around. I can certify that it is not the stock Cinepak data commonly seen in the early FMV era. Though perhaps the Sega CD console was the proving ground for later Cinepak technologies. A lot of Sega CD FAQs around the internet were apparently plagiarized from each other, which must have originally been plagiarized from Sega marketing material because they all shallowly list one of the system’s graphical capabilities as “Advanced compression scheme.”

Continue reading →

VQ/RoQ Coding Exercise

Once upon a time, a talented developer named Eric Lasota wrote a RoQ encoder named SwitchBlade. He also made a patch to hook it up to FFmpeg. Your job, if you are searching for an entry level task for jumping into FFmpeg development, is to revise that patch for inclusion into the main FFmpeg source tree. All the code is there. I think that the main chores involved will be reformatting the code to use the same style as FFmpeg, and concatenating the source files in a sane manner. You may need to revise some of the code per the guru’s specifications. Email me (email address under links on side bar) for more advice if you would like to take on this task.

Check his projects page to find the project source.

VQ Case Study: Textures

Per my understanding, a lot of 3D hardware operates by allowing the programmer to specify a set of vertices between which the graphics chip draws lines. Then, the programmer can specify that a bitmap needs to be plotted between some of those lines. In 3D graphics parlance, those bitmaps are called textures. More textures make a game prettier, but a graphics card only has so much memory for storing these textures. In order to stretch the video RAM budget, some graphics cards allow for compressing textures using vector quantization.

A specific example of VQ in 3D graphics hardware is the Sega Dreamcast with its PowerVR2 graphics hardware. Textures can be specified in a number of pixel formats including, but not limited to, RGB555, RGB565, and VQ. In the VQ mode, a 256-entry vector codebook is initialized somewhere in video RAM. Each vector is 8 bytes large and specifies a 2×2 block of pixels in either RGB555 or RGB565 (can’t remember which, or it might be configurable). For the texture in video RAM that is specified as VQ, each byte is actually an index into the codebook. Instant 8:1 compression, notwithstanding the 2048-byte codebook overhead which can be negligible depending on how many textures leverage the codebook and how large those textures are.

VQ Case Study: RoQ

RoQ was first developed for the FMV-based adventure game The 11th hour and was later adopted by Id for the Quake III engine and derivative games.

RoQ operates in a YUV 4:2:0 space. However, it was developed for a game released in the late 1994/early 1995 timeframe. Back then, cutting edge video was 640×480 at 256 colors or maybe 64K colors. and it was not feasible to take a large video frame and convert the entire thing from YUV -> RGB 30, 24, or even 15 times per second. However, RoQ’s design solved some of these problems.