VQ Compression

If you have any questions on programming, this is the place to ask them, whether you're a newbie or an experienced programmer. Discussion on programming in general is also welcome. We will help you with programming homework, but we will not do your work for you! Any porting requests must be made in Developmental Ideas.
Post Reply
BlackAura
DC Developer
DC Developer
Posts: 9951
Joined: Sun Dec 30, 2001 9:02 am
Has liked: 0
Been liked: 0

VQ Compression

Post by BlackAura » Wed Jul 13, 2005 9:16 am

I've been looking into using VQ compression for some stuff. There's a couple of things I'd like to know though.

First, does anyone know how I can decode a VQ compressed texture in software? Basically, I'd like to be able to view VQ compressed textures on a PC, and load them into OpenGL textures to use on a PC version if no uncompressed (or even S3TC compressed) textures are available. I don't particularly want to write a VQ decoder from scratch (so working source is preferable), but even a description of how to go about decoding the things would be useful.

Second, and less importantly (since I can probably figure this out by trial and error when I get the time to do so), does anyone know how mipmapping is supposed to work on the Dreamcast? For example, how many mip levels are required, where are they placed in video memory, and is there anything special that needs to be done to enable them?
BlackAura
DC Developer
DC Developer
Posts: 9951
Joined: Sun Dec 30, 2001 9:02 am
Has liked: 0
Been liked: 0

Post by BlackAura » Sun Jul 17, 2005 2:50 am

Never mind. I've worked most of it out. Just in case anyone wants this information...

I found some code to read PVR images, which contained VQ decompression stuff. The format is a little weird (2048 bytes of codebook, followed by one byte of padding, and then the VQ compressed data), and appears to be in the format the hardware expects. The KMG VQ encoder produces the same format, with a slightly different image header strapped to the front of it. The code in question was actually from Pike, the scripting language the DreamSNES guys used to build their installer. Specifically, it has PVR texture support as part of the standard distribution (the Image module). Chances are that one of them (probably PB) contributed it.

For mip maps, it appears that the mip levels are stored directly after the main texture, in decreasing order of size. Each mip level is half the size (width and height) of the previous one, as with just about every other implementation of mip mapping. Every possible mip level, down to 2x2, is used.

Looking at a few Dreamcast games (especially Sonic Adventure 2), that appears consistent. If you look carefully at SA2 (or not so carefully - like the final Sonic vs Shadow bit), you can see around six or seven mip levels on each texture, which would put them around 256x256.

I'm also amazed at how well it works - in all but the most pathological cases, it works almost seamlessly (if you know exactly what you're looking for, and where to look, you can occasionally spot it). It seems to switch to a lower mip level only when it needs to. On the switch, the texture is half it's original size, so the bilinear filtered texture looks almost identical to the mip map.

A 256x256 16-bit image comes out at 128KB uncompressed, and 18KB compressed. With mipmaps, that's just over 23KB compressed, or 168KB uncompressed. I need to play around with it a little bit more, but I can see quite a few potential uses for this thing.

Oh yes... The officially stated 5:1 compression ratio is a little misleading. It's comparing an uncompressed 16-bit texture with no mip levels to a compressed texture with full mip levels. If you're not using mip mapping, it's more like 8:1 (with an additional 2K codebook stuck on the beginning of the texture).

That also goes part of the way toward explaining how Quake 3 is actually able to run on the Dreamcast, while Quake 1 struggles so much. I'm around 99% certain that I could build a working Quake 3 level viewer, complete with all special effects, lighting, and so on, without requiring significant modifications to the data, and with roughly the same performance and image quality as the official port. It'd be even easier if I had access to the Q3 source code. Basically, VQ compressing most of the level textures and being careful about exactly which resources are loaded at any time would do the trick.

Shame that getting Q1 or Q2 running isn't so easy. It's almost trivial to run out of memory with these things. Q1 running in software mode isn't too bad. It has an annoying tendency to load far more resources than it actually needs, but it works. GLQuake is just wasteful, and Quake 2 suffers the dual problems of having more data than Quake 1, while only being a bit more efficient than GLQuake (because it assumes that it's running on a PC with virtual memory, so unused data will get swapped to disk if needed). They're also optimized for old video hardware, which bears far less resemblance to what's in the Dreamcast than the hardware Q3 was designed to run on.
User avatar
Quzar
Dream Coder
Dream Coder
Posts: 7486
Joined: Wed Jul 31, 2002 12:14 am
Location: Miami, FL
Has liked: 0
Been liked: 3 times
Contact:

Post by Quzar » Mon Jul 18, 2005 12:09 pm

Well, in case you aren't subscribed to the dcdev mailing list, you question was recently answered there by Simon Fenny (pvr) and it is slightly different from your findings.
dcsteve2005 wrote:
>
> Nobody has been able to answer this on the dcemu forums for the dc
> programmer known as BlackAura, and im trying to help him get the
> information he needs.
>
> "I've been looking into using VQ compression for some stuff. There's
> a couple of things I'd like to know though.
>
> First, does anyone know how I can decode a VQ compressed texture in
> software? Basically, I'd like to be able to view VQ compressed
> textures on a PC, and load them into OpenGL textures to use on a PC
> version if no uncompressed (or even S3TC compressed) textures are
> available. I don't particularly want to write a VQ decoder from
> scratch (so working source is preferable), but even a description of
> how to go about decoding the things would be useful.

I think I might be able to assist a bit here :-). Decoding in SW is quite simple.

For the "standard" 2bpp VQ mode, the VQ codebook (aka palette) consists of (up to**) 256 entries, each of which contains 4 texels arranged as a 2x2 block. The texel colours (for the entire texture) are specified using one of the 16bpp texture formats (eg 565 or 4444).

The texture data then consists of an 8 bit index per 2x2 pixel group, arranged in the usual UV Twiddled (technically "Morton") order.

All MIP levels of the SAME texture use the same shared codebook, but each texture has its own codebook.

I can't remember what happens for the 1x1 MIPmap level (I'd have to go and search through my old compressor code).

I don't think anyone used the 1bpp VQ mode so I won't describe that.


**I say "up to" because you can do a hack so that unused portions of the codebook could overlap into other memory/texture space.

>
> Second, and less importantly (since I can probably figure this out
> by trial and error when I get the time to do so), does anyone know
> how mipmapping is supposed to work on the Dreamcast? For example,
> how many mip levels are required, where are they placed in video
> memory, and is there anything special that needs to be done to
> enable them?"
When MIP mapping you require all MIP levels.

Note: FOR PERFORMANCE REASONS always do MIP mapping unless you can guarantee the texture will always be displayed at 1:1 resolution or will be magnified.

Simon

>
"When you post fewer lines of text than your signature, consider not posting at all." - A Wise Man
BlackAura
DC Developer
DC Developer
Posts: 9951
Joined: Sun Dec 30, 2001 9:02 am
Has liked: 0
Been liked: 0

Post by BlackAura » Tue Jul 19, 2005 12:39 am

Actually, that's pretty much the same as my findings. Just slightly more detailed. And helpful too - it explains what the codebook actually does.

The codebook is indeed 256 entries. Each entry contains 8 bytes (4 16-bit texels), so the total size is 2048 bytes. That explaination of how to decode the things makes a lot more sense than the source code I've found, and is much more helpful in understanding how VQ compression actually works, and how to decode it.

As far as I can see, there isn't a 1x1 mip level. The KMG VQ encoder doesn't produce one, neither does the PVR VQ encoder I found laying around on the 'net somewhere, and the PVR files I've examined don't appear to have a 1x1 mip level either.

One thing I did notice though - the mip levels are actually stored in reverse, starting from 2x2 and going up to the full size.
Simon Fenny wrote:Note: FOR PERFORMANCE REASONS always do MIP mapping unless you can guarantee the texture will always be displayed at 1:1 resolution or will be magnified.
Yeah, that's what I'd assumed. Lower resolution texture, uses less memory bandwidth, and shouldn't require as many calculations to actually draw.

Oh yeah... I suppose I should probably subscribe to the dcdev list again. I was subscribed before, but I changed my email address and didn't bother changing it over or anything.
Post Reply