vrijdag 21 augustus 2009

Easy Compression

Thanks to the pretty detailed graphics (sprites of 48x48 with 6 frames of animations drawn from 8 sides) I went over the normal DS RAM limit (4 MB). This isn’t a huge problem, since the DSi has 16 MB ram (4 times more!). However I like to try and keep everything as small as possible. And I was never satisfied with the way I handled the graphics (I was also too lazy to really change anything, until I hit this limit).

I applied a technique that I also use for my voxels. Although recently, I noticed this is also the way John Carmack did store the graphics for Doom.

Basically what I do is, throw out all the transparent pixels of the bitmap (and with transparent I mean the color the game doesn’t draw). This (especially for sprites, which always seem to have a lot of transparent pixels) decreases the size a lot.

I just scan the bitmap map, and store only the pixels that aren’t transparent. I do this using ‘slabs’ or lines. When I find a pixel that isn’t transparent I create a new slab or line. The line will grow (in width) until we hit another transparent pixel.

Here's a sprite animation from the pirate theme world -

At the same time I store all non-transparent pixels in a array.

When I want to draw such a picture in the game. I just loop through the lines and draw them. This way I can figure out where all the non-transparent pixels go on the screen. It’s also faster than my normal approach (since I use to scan over every pixel in the 48x48 bitmap, and then decide if it needed to be drawn).

This is kind of cool, because normally compression means you need to decompress. Which makes things slower instead of faster!

6 opmerkingen:

  1. Erg slim gedaan. Geeft mij ook weer een nieuwe kijk op ruimtebesparing.

  2. That is a common use for RLE (which is what you id) actually. A slightly improved version is to encode the image for a state machine VM that has 'commands' like DRAW_PIXELS, SKIP_PIXELS, NEXT_LINE. Beyond requiring less branches (zero i the CPU has 'movd'-like commands and you use a function table for this -- although depending on the architecture this might be worse due to cache misses, but i'm not sure if the ARM in DS has any cache), it also has the beauty if adding an extra 'command' to handle translucency or other effects (darken, lighten, or even blur - a sprite that has parts that blur the background!) not affecting the rest.

    A more advanced version (which *will* impact your cache if your architecture has one) is to encode the RLEd image directly in machine code skipping the VM entirely.

  3. I didn’t know this is also RLE. To my knowledge you still ‘store’ all the data in RLE but in a shorter way like this ‘WWWBBBBWWBWWWBB’ becomes ‘3W4B2W1B3W2B’. While in my method I delete all the transparent pixels (they don’t exists anymore, after the image went through my tool).

  4. When scanning the compressed image, how do you know when a new 'slab' starts? And how do you determine where the new slab should be rendered horizontally?

  5. @Hugo:
    If you think the data you want to encode as only the mask part, what you encode is 1bit data (0=transparent, 1=opaque). In this case you don't have to specify what follows: just alternate between the two values.

  6. @Kostas:

    I understand, but I'm not doing that!

    I look at it indeed as a mask part. If I find a opaque pixel, I start a new line (or slab) I store the x-value (the start place) and I then increase the width of the line until I hit a transparent pixel.

    So in the end I have no data of transparent pixels.

    So my data isn't alternated between the two values, instead I know where to draw the opaque pixels because I have the x offset value!