Packing rectangular image data into a square texture

Question

I have N items of 2D image data that will be rectangular and I want to pack them into a single power of 2 texture as efficiently as possible.

A simple non-efficient and naive implementation of an algorithm to pack these rects would be easy to whip up, but I'm sure people have come up with algorithms to do this as space efficiently as possible. I've found various references to lightmap packing which is similar to what I'm looking for, but the algorithms for lightmapping tend to take non-rectangular images into account which actually complicates things more than I need them to be.

Does anyone have hints? Names of algorithms or paper authors I should google?

Thanks.

Solution 1

Your problem in 1D is called Bin Packing. Perhaps that's a good start for your search.

Note that the problem you want to solve is really hard (it is NP-hard). So you should not search for the optimal solution, but some clever heuristical algorithm.

I think bottom-up dynamic programming is possible for 1D bin packing, but not for the 2D case.

You could think of simplifying your problem by only solving the 1D problem, making restrictions like cutting the textures into several (variable sized) slices in 1 dimension.

Another possiblity is running meta-heuristic optimization on it, like Evolutionary Algorithms or Particle Swarm Optimization.

Solution 2

Very good and simple packing algorithm can be found here: http://www.blackpawn.com/texts/lightmaps/

Its implementation only takes 200 of C++ lines, not more (I suppose you have the Bitmap manipulation routines already).

For the theory behind there is an introduction by Jukka Jylänki (look for the "A Thousand Ways to Pack the Bin").

The author of the paper provides the C++ library which is really bloated from my point of view, but on the other hand it has a lot of options and is very well documented.

Solution 3

I had a similar problem but I was packing squares. Try this: http://www.mrashid.info/blog/stacking-squares-problem.php

The C++ code is not very elegant but at least you get the basic idea on how to approach this problem.