Texture packing algorithm

What is a good texture packing algorithm? Technically, bin packing is NP-hard, so a heuristic is what I'm really after.

Answer

I spent a few months at one job coming up with a better texture packing algorithm.

The algorithm we started with was simple. Collect all the input items. Sort them by total pixels consumed, large-to-small. Lay them out in your texture in scanline order, just testing stuff from the topleft pixel to the topright pixel, moving down a line, and repeating, resetting to the topleft pixel after every successful placement.

You either need to hardcode a width or come up with another heuristic for this. In an attempt to preserve squareness, our algorithm would start at 128, then increase by 128s until it came up with a result that wasn't any deeper than it was wide.

So, we had that algorithm, and I decided to improve it. I tried a bunch of wacky heuristics - trying to find objects that fit together, doing some weighting over a bunch of desired space packing properties, rotating and flipping. After all my work, quite literally three months of work, I ended up saving 3% space.

Yeah. 3%.

And after we ran our compression routine over it, it actually ended up larger (which I still can't explain) so we threw the entire thing out and went back to the old algorithm.

Sort items, jam into texture in scanline order. There's your algorithm. It's easy to code, fast to run, and you won't get much better without an amazing amount of work. That work just isn't worthwhile unless your company is at least 50 people large, and probably more.

And as a side note, I just implemented this algorithm (fixed width 512 pixels) for quite literally the exact same application that you're doing (no ftgles, but opengl-rendered freetype glyphs.) Here's the result. It looks blurry because mine is using Valve's distance-field based text rendering algorithm, which also accounts for the extra space between glyphs. Obviously, there's not a lot of empty space left over, and it does a good job of cramming things into open spots.

All the code for this is BSD-licensed and available at github.