Crazy graphics compression idea

Development
#1

Ok, I hinted at this on Twitter, so I thought I’d explain properly here.

With the Arduboy’s screen, pixels in sprite are one of three options (assuming you’re not doing trying to create any greys):

  1. Black
  2. White
  3. Transparent (that is, the sprite shouldn’t change the colour of the pixel)

The typically way of doing this is to have two bitmaps. Essentially, you are using 2 bits to store each pixel value. But, this is actually inefficient!

Say you draw the first one in white, and then draw the second one over the top in black, the bits correspond to:

Look, we’re encoding black twice! What a waste!

How do you not waste this encoding? (Note, it’s not an extra bit, it’s just an extra option). Well, you have to use it to store part of the next pixel.

Basic Idea

So for 1 pixel there’s 3 options. If we encode that by itself, we need to use 2 bits.

For two pixels, there’s 9 options, but we still need to use 4 bits to encode that (as 3 bits only gives us 8 options).

But for 3 pixels, we have 27 options, which only take 5 bits to store. If we were using 2 bits for a pixel, this would take 6 bits. So suddenly we’re saving space!

I did a little test, and it works out you get about as good as you can get when you store pixels in groups of 5. There are 243 options, which can be stored in 8 bits, and would normally take 10 bits. So you’re compressing the data by 80%.

The other reason why this is good is because to decode the data it’s much easier if it’s takes up exactly one byte.

Encoding / Decoding

Ok, so how do you actually use 8 bits to store 5 lots of 3 options? Well, you encode the data as a base3 number.

I’ll explain how that works with base10. Say we want to store the number 573. First we start off with 5. Then multiply that by 10, and add 7 to get 57. Then we multiply that by 10 and add the 3 to get 573. This process works even if the numbers are in binary.

So to store 212 in base3, we start with 2. Then we multiply that by 3, and add 1 to get 21 (in base3). Then we multiply that by 3, and add 2 to get 212 in base3, which is 23 in decimal. If you did this in a computer, you’d 10111 in binary, which is 23 in decimal and 212 in base3.

To go backwards, you do the opposite. You divide by the base, and the remainder is your next-lowest digit. Then you repeat it by dividing by the base again and taking the remainder.

Caveat

In a processor, dividing/multiplying by 2 is super easy. But dividing by 3 is much slower comparatively. Also, if the code to decode this data is too big, then you won’t actually be saving any space!

But yeah. That’s the idea.

2 Likes
#2

The actual way of having two bitmaps is not that inefficient as most of the time the images are only white and transparent or black and transparent. For example, the hero of Shadow Runner from @JO3RI is just a shadow (doh!):

As you said, the drawback to this method is that you would need an additional sprite (or some added code) if you wanted to make his eyes appear in white when he is on top of a black background. Your technique would be especially useful if you have a game with many layers of sprites.

As an addendum, note that if you have sprites with 4-bit per pixel, you can actually have a palette of 3 colors + transparent which would allow the Arduboy 2 to have color even with the current microcontroller (wink, wink @bateske ;-)):

Untitled_6.png732×228 1.12 KB

#3

I created a 2bit per pixel format with an image converter. It is 00 black 01 gray 10 white and 11 transparent. It works pretty well but the actual drawing function could do with some optimization. I’ll post what I’ve got soon, maybe one of you would be able to optimise it a little. For images up to 16x16 it works quite well, but beyond that you get the gray scale tearing pretty bad.

1 Like
#4

That is actually super interesting. I am looking forward to seeing what you have got!

#5

Nice, @Gaveno ! Yeah using 2 bits to store a grey tone is also a good idea.

This intention for this was in the specific case where you already have some black and white graphics but you’re running out of space. There probably is a better way to compress the data but I this at least has the advantage of being relatively simple to decode. I think the 80% compression could be worth it.

If @bateske’s going to add a colour screen then I think the memory limitations would need to be addressed, but problem is the more stuff you try to put on it the worse the battery life is, or the larger the Arduboy becomes. I’m interested to see what developments get made, but I’m also pretty happy with the current design :smiley:

#6

I’m excited to see what you come up with! I have a game I’m working on that is only using black and white that will probably run into the storage limitation. I hope the processor can handle the decoding process okay.

#7

Any type of compression other than simple 1 bit b/w or 2 bit b/w, transparency bit is probably going to be an order of magnitude (i.e., 10x) slower in real world practice. To make things fast on this hardware you need to read raw bytes from PROGMEM and then push them display buffer with as little transformation as possible. So do simple layers and such you already have several expensive AND/OR/NOT operations per byte… and if you’re rendering at a vertical offset other than 8 then the cost of bit-shifting itself starts to become significant.

I’m referring to heavily used sprites and such here. The only time some type of “compression” might be worth it is for large full-page images… something that you can take your time to decode and render to the display buffer. Then of course you have to look at the size of the “decompression” code compared to the cost of just storing the full resolution images in a simpler format. You might be surprised at the comparison.

#8

For full screen though it’s probably better to just “pretend” to you have 2 bit color (black, white, grey, transparent), store it as 2 bit color, and then RLE compression it - since that type of compression would probably work really well for lots of different types of images and having a “grey” would allow you to easily compress what would otherwise be 01010101 patterns and completely incompressible with RLE.