Useless RLE?

I've been programming a tool to compile all bitmaps for my games into one huge resource file that is pre-loaded into the game. I really need some type of compression scheme to get these beasties down to a manageable size.

I've attempted RLE or VRLE (variable run length encoding). Essentially it's this. There is no RLE 'token' - if a symbol repeats itself you simply turn RLE on and begin to count how many times it repeats, shut it off when the symbols no longer match, and write out the value.

So:

AAAAABCDDDDC

becomes

AA3BCDD2C

Problem is that RLE works great for palletized textures, but not for pure 32-bit textures. Here's why. In order for symbols to repeat in a 32-bit texture file you either have to have a shade of white or by some odd chance the symbols between colors repeat. I can only think of a couple of instances where this might be true, so I'm not sure that RLE will do much for me.

Let's say we have the following filtered pixels in RGBA format:

0,126,32,100
1,127,31,99
2,125,30,98

As you can see RLE won't do anything for this sequence. Yet this is how most 32-bit images will look in memory. The color values are not that far apart which produces very nice transitions between color shades. I just don't think RLE is the answer here.

Any ideas?

One idea I have is to try to create a palette so to say of colors. This would require iterating through the entire picture and counting the number of unique colors and placing them in a palette table. Then I could write out the palette entries for the actual data. At decode time you would look up the palette number retrieved from the data chunk, and get the actual RGBA color values from the palette chunk. However...I'm not sure this would compress anything. It might even make the file bigger.

I'm open to suggestions.

One problem with your RLE scheme is that if the run is greater then 9 in length, it will confuse the decoder.

Why not just put everything in PNG and then grab a PNG decoder, unless you plan on making money from it which is a different story.

The run length is in hexadecimal so if run length mode is on and we have this:

AAFF


This denotes two bytes:

AA and FF.

My run length encoding scheme will treat AA as an RLE set flag. The FF denotes that 256 more bytes with value of AA follow.

Another option is to try run length encoding on bits.
It's far more likely that bits will repeat.

I suggest PNG too , back in my past as Gm programmer I learned a normal PNG sprite costs like just 1kb

How bout Huffman compression?

Are you trying to minimize the disk space your game uses or the size of the distributed package? You could just put your fate in the hands of "zip" and rely on uncompressed data to be compressed in your distributed package.

I'm reading about Huffman but I'm afraid I don't quite understand it.

Perhaps I'll separate the bmp into chunks like this:

Header chunk
Red RLE chunk
Blue RLE chunk
Green RLE chunk
Alpha RLE chunk

Alpha will be last so that I can simply add an alpha channel to the image if I so desire. Of course this will require that I rewrite the entire file.

Here is my setup so far:

I've got 2 headers.

The first header is the global file header and states how many bitmaps are in the file and stores some various other housekeeping variables.

After the file header is the first chunk header. The chunk header simply stores the width and height of the image as well as the chunk size in bytes.

After the chunk header is the chunk data.

So the file looks like this:

Fileheader
...
ChunkHeader
...
ChunkData - RAW RGB values
...
ChunkHeader
...
ChunkData - RAW RGB values
...

With the new setup it will prob look like this:

.Fileheader
...
.ChunkHeader
...
...ChunkData
.....Red RLE data
.....Green RLE data
.....Blue RLE data
.....Alpha RLE data
ChunkHeader
...

Bubba, there was a compression contest a while back. I think XSquared mentioned he had a fully functioning huffman entry. Might be worth a look..
http://cboard.cprogramming.com/showt...threadid=41393

btw: i think your RLE will perform better by grouping colours as you suggest.

Bubba doesn't know something (Huffman)? There is a god... :p

Plenty of resources around for it, but some people find it hard to visualise. I actually "wrote" a bitmap on paper using 0-9 (Drew a sort of skyscraper out of it) and wrote the trees down as I went along before moving smoothly to implementation. :cool:

As you've pretty much said, RLE doesn't really work for non-palettized images because of the variation, although you will get better results with your planar suggestion.

Note that JPEG and PNG both use Huffman and RLE.

Yep I'm pretty upfront about something if I don't understand it and I've looked at Huffman compression and I sort of understand it, but not enough to begin coding it.

Bubba, why do you want to reinvent the wheel?
If you're doing this for learning/fun, then please disregard my comment :)

>>Perhaps I'll separate the bmp into chunks like this:

That might work better, but if the texture is just a little complex I don't think you'll gain anything.

Quote:

---

Originally Posted by SMurf

Note that JPEG and PNG both use Huffman and RLE.

---

There is more to it (lots of math). JPEG uses discrete cosine-transform and JPEG 2000 uses wavelets.

I don't want to re-invent the wheel...but I don't know how to use the 'wheel' that's already been invented.

Quote:

---

Originally Posted by Sang-drax

There is more to it (lots of math). JPEG uses discrete cosine-transform and JPEG 2000 uses wavelets.

---

Yes, I've got a book behind me that I fished out of the university library (They have USEFUL books! :eek: ) on JPEG. Trying to write a decoder, but the committee decided to name some of the coefficients after electrical terms. They really go out of their way to make these standards easy to understand, don't they? :rolleyes:

Don't worry about it, Bubba. Just get your hands dirty and it'll all become clear. Small fish.

Well I appreciate the vote of confidence and I guess I don't understand simply due to a lack of exposure, but it looks very complex.

I understand the tree structure but I don't understand how that is going to reduce the actual symbol size. Then I also looked at the dictionary thing and it sort of makes sense, but coding it does not sound like fun.

Yet another area for me to conquer on my quest to be a great game programmer. Does this quest ever end? Do I ever finally 'arrive' at my destination or do I have to keep trudging along....:)

j/k

:D

There is so much to coding a game engine and nice GUI tools to use to make the data the engine reads. I never knew how complex this stuff was. My code base for XSpace alone is now over 100 pages long. I would give you a line count except MSVC keeps flagging an error (one that doesn't make sense at all) when I attempt to do a line count.

100+ pages and I haven't even touched multiplayer, scripting, AI, vertex/pixel shaders, effect files, etc, etc. And you guys seem to love the screenshots from my game so far, but I want more. The lighting just sucks and I need to load all my models from disk, not create them - even for the planets. There is so much left to do.

For those of you that keep asking everyone here to post code on how to program simple games and then go on to list some very involved and advanced game programming concepts like multiplayer, sound, etc. - You have no idea how involved this stuff is. We could never just tell you how to do it and I really don't think there is one right way or one wrong way to do it. Sometimes it makes my head spin. But with everyone waiting for the beta release it does give me a lot to live up to - I aim to please and I hope I do.

The bad part is that video technology is changing so fast that I really need to get XSpace into the vertex and pixel shader realm to even come close to retail quality. I can do it but I really need some hard-core dedicated game programmers that know their stuff.

This probably belongs on the recruiting board but oh well:

Please if you are dead serious about game programming, have an interest in space shooter/exploration/storyline-based games, and this is a must -> Have 5 to 10 years of experience in C/C++, COM, Direct3D, OpenGL, 3D mathematics and algorithms, LOD systems, and/or sound design/editing/programming - please let me know. I need you.

Quote:

---

Originally Posted by SMurf

Trying to write a decoder

---

Sounds really interesting. Let us know when/if you make any progress. I'd be willing to help, but I have too much to do right now.

One project I thought of yesterday would be to use wavelets to compress movies. Think of each pixel in a movie as a point in 3D-space (x,y,t) and compress every pixel at the same time with 3D-wavelets, instead of compressing frame by frame. Would this work? Can it be done in reasonable time?
EDIT:
http://www.google.com/search?num=100...eo+compression

Quote:

---

Originally Posted by Bubba

I don't want to re-invent the wheel...but I don't know how to use the 'wheel' that's already been invented.

---

Then encode your images as JPEG or PNG and use existing loaders. You seem to have enough to do already. :)
You won't come close to the compression of JPEG with Huffman trees.

You most likely will want to use PNG over JPEG, mainly because A) it's lossless, and B) it has built-in support for alpha-channels. And with respect to my Huffman code, yes, it works, but the code is horribly ugly, and most likely quite inefficient. Another compression algorithm you could look into (assuming you don't use PNG/JPEG), is LZW. If the compression ratios of both of those two algoritms individually are not good enough, you could just stack them. The best way to stack them would be to use LZW to compress the file once, and the Huffman to compress the file again. Unfortunately, I haven't tested either on raw BMP files, so I can't give you any pertinent data in that regard.

I still stand by the "who cares about disk space! as long as your distributed package is small (ala zip) your ok"

Bubba, about your request for help. Im very tempted to give it a try but i dont think it would work out. We have a lot of the same interests and goals but we use very different mediums to achieve them. I prefer using open source libraries whenver i can, and i havnt booted into windows in months. I also strongly dislike coding in Hungarian style, and your project (i assume) is already entirely written that way! My free time is also sparse at best... id hate to commit to something only to drop it because i dont have the time.

The problem of LOD with spherical meshes interests me though. Ill do a little reading and if i end up implementing anything id be more than happy to contribute it :)

Quote:

---

Originally Posted by Perspective

I still stand by the "who cares about disk space! as long as your distributed package is small (ala zip) your ok"

---

If you don't compress your images with anything other than zip, the distributed package won't be very small.

I agree with you though, disk space is almost free and nowadays most people have a fast internet connection to download large files with.

>>If you don't compress your images with anything other than zip, the distributed package won't be very small.

yeah, your probably right. I was thinking about it from the opposite side... zipping a compressed image won't really make it smaller.