On Tue, Aug 11, 2009 at 8:41 PM, Brian Meidell <brian@gameequation.com> wrote:

I'm looking for an algorithm to allocate 2d rectangles of different
sizes from a larger 2d rectangle (small areas out of a large texture),
while wasting as little space as possible without being insanely slow.

Search terms that yield google results are welcome answers (I tried,
but I guess my google-fu proved too weak).

"Rectangle packing" is probably a good search phrase.

One simple, quick and reasonably good algorithm (that I can't find the paper for right now), is to first align all the rectangles so their longest axis is pointing along y, then sort them by this height. Then you simply start putting down rectangles left to right until you reach the right edge (you have to guess how wide this is - if you're trying to optimize for "squareness" a binary search can help), and then you go right-to-left underneath that until you're back at the first edge. Then move this last row of rectangles up so that it's as close to the first row as possible. Repeat until you've run out of rectangles.

Hardly optimal, but at least it's simple!

Sebastian Sylvan