bitmap encoding

Libraries, utilities, bootloaders...

bitmap encoding

Postby rodot » Thu Mar 20, 2014 1:21 pm

I would like to have your opinion about bitmap encoding. Here is what I suggest:

First byte: width (must be a multiple of 8)
Second byte: heigt (can be any value)
(For now width and height are passe as argument every time, not really handy)
Remaining bytes: raw bitmap

Myndale suggested that we could use a run-length compression algorithm... but I'm not sure that it will really be efficient. The display is only black&white, so one pixel only needs one bit. With color bitmap I understand that it's way more efficient.
In the case of small game sprites, like 8x8 or 16x16, there won't be enough solid-color area, so it will even take more space than raw bitmap.
In the case of large pictures, it might show a little improvement, except if we use dithering then it will take more space. So I don't think that it's worth it.
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: bitmap encoding

Postby adekto » Thu Mar 20, 2014 2:04 pm

i dont know to much about compression but what about repeating patterns
it can be probably much complicated but im just showing on a line by line system
referencing a line that has been in memory befor

Image
1. original
2. color lines show reused lines
3.size of how much is compressed

ofcource this wont work on complexer designs unless u make smaller packet like 4 or 8 pixels
User avatar
adekto
 
Posts: 448
Joined: Tue Feb 25, 2014 9:47 pm
Location: belgium

Re: bitmap encoding

Postby adekto » Sun Mar 23, 2014 12:05 am

i had a little crack at the run-length encoding

but wel somewhere somthing went wrong :p

txt file is the stuff im reading from (origenal gamebuino sprite)
i got it to convert to a single string of 1/0 but then the w/b stuff im not sure how to do that one
Image
User avatar
adekto
 
Posts: 448
Joined: Tue Feb 25, 2014 9:47 pm
Location: belgium

Re: bitmap encoding

Postby hrangan » Sun Mar 23, 2014 12:38 am

Just an idea for smaller sprites, from the wikipedia page,

Run-length encoding can be expressed in multiple ways to accommodate data properties as well as additional compression algorithms. For instance, one popular method encodes run lengths for runs of two or more characters only, using an "escape" symbol to identify runs, or using the character itself as the escape, so that any time a character appears twice it denotes a run. On the previous example, this would give the following:

WW12BWW12BB3WW24BWW14

This would be interpreted as a run of twelve Ws, a B, a run of twelve Ws, a run of three Bs, etc. In data where runs are less frequent, this can significantly improve the compression rate.


Also, why must width be a multiple of 8?
User avatar
hrangan
 
Posts: 58
Joined: Thu Mar 20, 2014 9:35 pm
Location: Bangalore, India

Re: bitmap encoding

Postby adekto » Sun Mar 23, 2014 12:55 am

hrangan wrote:Also, why must width be a multiple of 8?

since we are dealing with bytes i asume its easyer to let the byte run out in our case in a vertical line instead of having every pixel be independent (citation needed)

also i was thinking about an array with intigers up to 255, where ever even numberd array is say black and every uneaven be white (so it togels) just to get the size down
User avatar
adekto
 
Posts: 448
Joined: Tue Feb 25, 2014 9:47 pm
Location: belgium

Re: bitmap encoding

Postby rodot » Sun Mar 23, 2014 10:06 am

A byte is made of 8 bits. A pixel is either black or white, so you can store 1 pixel by bit (8 pixels per byte).
With raw bitmap, every bit set to 1 means black. For example, 00110001 means WWBBWWWB
With run-length compression, we can say that the first bit of the byte is the color, and the remaining bits are the length. For example, 10001100 would mean Black 0001100 == 12 black pixels. Then it takes only 8 bits (one byte) to store 12 black pixel, so the compression is effective. But most of the time, the pixel color change every few pixels (less than 8) so the run-length compression would actually increase the picture size.

The width of the bitmap has to be a multiple of 8 because 8-bit micro-controllers loves multiples of 8. It makes algorithms way simpler and faster. When you have to display 20 sprites simultaneously, you want it to be fast. If you need a 4 pixels wide sprite, you can just surround it with white pixels for it to be 8 pixels wide.
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: bitmap encoding

Postby adekto » Sun Mar 23, 2014 1:41 pm

what about a nible? (half a byte for every Run-length encoded set, making it a max of 15 pixels
also if we have a compiler to this format it can say if the size of the RLE compresion is biger then the normal pixels to go for the normal pixels?
User avatar
adekto
 
Posts: 448
Joined: Tue Feb 25, 2014 9:47 pm
Location: belgium

Re: bitmap encoding

Postby rodot » Sun Mar 23, 2014 1:59 pm

with 2 nible / byte, it will look like:
CLLLCLLL (C:Color L:length). With 3 bits for the length, it would be a maximum length of 8 pixels.
I thought about having both the RAW or RLE compression, but it will increase the library size... seriously, I don't know if it is worth it :/

I did the modification in the library to embed the bitmap size, it's way more handy than passing it by argument every time.
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Re: bitmap encoding

Postby adekto » Sun Mar 23, 2014 2:12 pm

u dont need the collor in in CLLLCLLL since u know the first always is black for example and the next one is white, and if the image has more then 15 pixels it be 11110000 and then i byepass the white once
User avatar
adekto
 
Posts: 448
Joined: Tue Feb 25, 2014 9:47 pm
Location: belgium

Re: bitmap encoding

Postby rodot » Sun Mar 23, 2014 3:13 pm

For now, the default library will only have RAW support, but once again, the project is open source, and if you implement a nice feature, I'll merge it in the core ;)
I changed the bitmaps function, now you no longer have to pass the size and color by argument every time, it's way more convenient:
Code: Select all
gb.display.drawBitmap(x, y, bitmap);
gb.display.drawBitmap(x, y, bitmap, rotation, flip);

Now, let's write a bitmap encoder.
User avatar
rodot
Site Admin
 
Posts: 1290
Joined: Mon Nov 19, 2012 11:54 pm
Location: France

Next

Return to Software Development

Who is online

Users browsing this forum: No registered users and 25 guests

cron