Here's a standard solution to this problem. Note that rather than packing all the textures into a single large rect, it packs them into N rects of a predetermined size. This is probably better anyway, as you will want to choose the size of the aggregate textures for optimal performance.

1. Sort the textures by area, from largest to smallest.

2. Create a new 'texture rect' of dimension size * size. 'size' should be big enough to hold the largest of your textures.

3. Go through the texture list and find the first one that fits in your texture rect. If none fits (this won't happen on the first pass), go back to 2 and create a new group texture.

4. If it fits, put it in the upper left. You can now split the remaining area in two ways, either along the textures right edge or bottom edge. Choose the split that results in the largest single new rect. After the split, we'll call the larger of the resulting rects A and the smaller B.

5. Goto 3, recursing on rect A.

6. Goto 3, recursing on rect B.

Anyway, that's how I remember it (it was in one of the Watt/Policarpo books). It's probably not the only solution, but it is a solution.

Also, I think this is the general idea of oliii's solution as well.

Quote:For step 2, what if a massive texture was created that could fit any size and any amount of subtextures. Place all the subtextures on, biggest first. Then make a new texture, that fits the grouped subtextures and copy the grouped subtextures to the new texture.

I see what you're saying. Is it a good idea? I don't know :-) I haven't coded this, so I can't really say what the best approach is. I'm thinking though that there might be issues with texture size, caching, memory, API-specific things, and whatnot, so perhaps one big texture wouldn't be ideal, and a number of smaller ones would perform better.

Again though, I'm just guessing :-)