The Plasma Engine

Rectangle packing, or 2D box packing (or bin packing), is a pretty common problem in computer graphics. Plasma needs a good rectangle packer because most GL ES hardware only supports textures with sides that are powers of 2, and this isn’t an acceptable limitation. Our current solution is to pack all bitmaps into one big texture which meets any hardware requirements. Then we can just draw the parts of the texture that the frame requires.

So, how can we efficiently pack a bunch of bitmaps into one big image? I think the ideal solution would be to do this at compile time, similar to what GWT does. However, what if a game uses different textures for different levels? Loading up all the textures all the time isn’t a good solution. Having different huge bitmaps for different levels also fails, as it would make the application size explode.

The method Plasma uses is to generate the large bitmap at run-time. Our rectangle packer is fairly efficient and pretty fast, so the one-time cost at startup is hardly noticeable. But getting to this point hasn’t been easy!

When I started researching the ideal rectangle packer, I quickly found a simple recursive implementation at black pawn. There were a couple minor things in his pseudo-code which had to be fixed, but we quickly had a rectangle packer up and running.

As I used this recursive splitting packer more, I discovered that it wasn’t very efficient in several cases. The problem is that the algorithm takes a box and splits it in half recursively, and no other texture can ever cross one of the lines.  For example, in the image at left, if we had a texture which was a little taller than texture 2, the algorithm would fail because it can’t cross line A, even though the texture could fit to the right of texture 1.

One of the difficulties in writing a recursive packing algorithm is that it is difficult to know which way to split the box. Should line A go all the way across the box, or should line B? The same question applies to lines C and D. Some more advanced recursive packers test both options, judge which one results in a more dense packing, and continue with that solution.

As I started working up the background test for Plasma, I quickly found that the recursive packing algorithm was completely failing for the set of textures I needed. Although the box was more than big enough, the algorithm wasted huge amounts of space and couldn’t get all the textures to fit. The cloud texture should easily fit below the sun and cactus, but the algorithm just can’t figure that out.

Eventually, I started over from scratch and wrote a much better rectangle packer which easily fits all the textures into the same box. But you’ll have to wait and see how this is done in Part 2! In the mean time, if you think rectangle packing is easy, try to come up with an algorithm to fit these 5 60×60 squares into the 170×170 box provided. My current algorithm doesn’t handle rotation, so it couldn’t solve this either, but it does demonstrate just how difficult the problem can be!

Leave a response Trackback