To provide some context, I have a couple of lightmaps for different objects in a 3D scene that I want to pack into a single texture. The lightmaps are square and have different sizes that are not necessarily power of two (although this restriction could be included if it makes for a better solution). The size of the resulting texture is arbitrary but should be as squarish as possible. I have to stay pixel perfect and can't use rotation. Speed is not a concern, this isn't used in a time-critical application.
The basic algorithm I found over at GameDev.SE would work like this:
While this sounds reasonable and easy to implement, I wonder whether this algorithm is a good choice for my purposes or if there is an even simpler solution. Especially, I am interested in the following:
The sort by height heuristic still works. Even this slightly simpler version works: sort by height, place from left to right on the same y, every time you reach the right side you increase y by the largest texture that was on this line. That way you don't even have to find a position, you already know where you'll put it. This works great if there isn't much variation in height, but it can be terrible.
As far as I know, there is no way to calculate the size beforehand. But, trying to do that would lead to non-power-of-two sizes anyway. Guessing a size (sqrt(total area) rounded up to a power of two perhaps) and increasing it by a factor of 2 if not everything could be fitted should find the best size quickly.
If all the things you're packing are power-of-two sized, then you can do something even simpler. Put everything in a heap, and try to put groups of 4 of equal size together to a block of the next size. There won't always be 4, that means some empty space in the bigger block.
If they are not powers of two, here is an alternative that may pack a bit better than the sort-by-height trick. It's significantly slower, and not worth it for packing only lots of small items, but I've found it useful when the items have radically different sizes. It's based on area splitting and in that regard it reminds of KD-trees, but it's not really that (because here it's about the areas, there are no "points"). Anyway you use a tree where every internal node represents a split, with the odd levels splitting in one axis and the even levels splitting in the other axis. When placing an item, recursively find the first place it can fit.
That's the basic thing. I've found it useful to first attempt to fit it somewhere "nicely" (such that it would create fewer than 2 splits, so it fits some region exactly in width or height or both) and only if there is no such place, settle for the first place it does fit. Also I've found it useful to store the free area that each node "has" and its "actual rectangle" in the node. The dimensions and location can be computed during the recursion and the area isn't really necessary at all, but having the actual rectangle right there is convenient and with the free area nodes that are too full can be skipped early. Reverse-sorting by area first can help to reduce areas that are split off once and can then never be used (whereas putting small items in after big ones should be no problem), but it is still almost never optimal.