Packing it up

I got pretty busy last week trying to implement a tutorial on 2D text.  The experience was successful and I’ll be posting some results soon.  But the more I got into it, the more I saw possibilities to expand on it and I pulled out some old code from my OpenGL 2 library and started to geek out on an actual tool to map and pack 2D font textures (or any textures actually) into larger maps.

Discussing the “best” algorithm for packing is akin to Ukrainian mothers discussing their families’ Borscht recipe: everybody think theirs is the original and the best (or so I’ve been told by Ukrainian acquaintances).

There are different ways of naming the problem (whether it’s texture packaging or The Knapsack Problem), but pretty much everyone agrees that finding some kind of optimization to it is NP-Hard, which means that finding a fast solution to pack all your textures in the most efficient way will take more time that you’re willing to spare to code, test and execute this beast.  Which is why most lazy persons like myself use one that “just works” and move on.  One day, if the solution causes any trouble, then we put time and money on finding a better solution (and a chance of having a slightly better efficiency rate, say 3% like some guy I read earlier on Stack Overflow).

Basically, I like this developer’s solution.  It’s simple to understand and code and it gives great results, as you can see in the image below.  This was done with a set of 3 tiles ordered randomly; the recursive algorithm aborts when it meets it’s first tile that cannot be placed.  And I’m sure we could squeeze a few more green ones.  This was a simple test and already, this looks fine.  But in a real-life situation, tiles are first sorted from biggest to smallest before packing.  And for those that wouldn’t fit, it would be trivial to implement some sort of overflow tile.

See you next time when we discuss 2D text and see how all this fits together.

pack

  1. No comments yet.

  1. No trackbacks yet.

return top