# minimal po2 surface for sprite arrangement

I've got 64 images of 96x192 pixels. I have to arrange them on a rectangle. I need the height and width of that rectangle to be powers of two. Given the dimensions of my images, they don't perfectly 'fit' on it (I can not rotate or cut the images into smaller ones); there is always some 'wasted space'.

1. ¿What are the dimensions of the rectangle that minimizes that wasted space?
2. ¿Can this problem be generalized to n images of w x h pixels?
3. ¿Does this problem have a name?

Context: This is not a class exercise. I'm trying to arrange sprites into a image for using them on hobby videogames. The requirement of power-of-two comes from the fact that some old video-cards don't handle non-po2 images very well. I've been thinking about this for 24 hours and couldn't arrive to any satisfying solution.

You need at least $96 \times 192 \times 64 = 1179648$ pixels. This is slightly more than $2^{20} = 1048576$ but fewer than $2^{21} = 2097152$. So you just need to check that you can fit them into $2^{21}$. One of many possibilities would be a rectangle $2^{9} \times 2^{12} = 512 \times 4096$, you could have 4 images across (since $4 \times 96 = 384$ ) and 16 images down (since $16 \times 192 = 3072$ ) and so the 64 images would fit.
• @Henry: I think you need to wrap your exponents in curly braces: 2^{20} becomes $2^{20}$ but 2^20 becomes $2^20$. – user856 Mar 2 '11 at 12:21
• In this case, the minimal solution must involve $2^{21}$ pixels as $2^{20}$ is too few. So $2^{21}$ is a lower bound, and it turns out to be achievable. To generalise, do the same thing: find a lower bound of the smallest power of 2 which is at least $n \times w \times h$, see if it possible to fit your small rectangles in it, and if not try the next larger power of 2 until you do find a solution. – Henry Mar 2 '11 at 12:37