Useless RLE?

This is a discussion on Useless RLE? within the Game Programming forums, part of the General Programming Boards category; I've been programming a tool to compile all bitmaps for my games into one huge resource file that is pre-loaded ...

  1. #1
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598

    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.

  2. #2
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    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.

  3. #3
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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.
    Last edited by VirtualAce; 03-07-2005 at 09:44 AM.

  4. #4
    email for MystWind avatar MystWind's Avatar
    Join Date
    Feb 2005
    Location
    Holland , The Hague
    Posts
    88
    I suggest PNG too , back in my past as Gm programmer I learned a normal PNG sprite costs like just 1kb
    PLay MystWind beta , within two years

  5. #5
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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
    ...

  7. #7
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    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..
    NOTICE: New contest (finally)

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

  8. #8
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    Bubba doesn't know something (Huffman)? There is a god...

    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.

    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.

  9. #9
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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.

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  11. #11
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    I don't want to re-invent the wheel...but I don't know how to use the 'wheel' that's already been invented.

  12. #12
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,266
    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! ) 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?

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

  13. #13
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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



    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.
    Last edited by VirtualAce; 03-08-2005 at 08:11 AM.

  14. #14
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    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.
    Last edited by Sang-drax; 03-08-2005 at 11:09 AM.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  15. #15
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    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.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 01-10-2008, 11:38 PM
  2. another sort useless program
    By mrsirpoopsalot in forum C Programming
    Replies: 21
    Last Post: 09-18-2006, 03:35 AM
  3. useless post just saying thanks
    By Chaplin27 in forum C++ Programming
    Replies: 3
    Last Post: 02-08-2005, 10:27 PM
  4. Corollary to Feb. 8th useless fact Corollary:
    By Drewpee in forum A Brief History of Cprogramming.com
    Replies: 14
    Last Post: 02-13-2002, 03:44 AM
  5. Useless fact of the day
    By CoderBob in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 02-07-2002, 08:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21