Packing rectangles into a rectangle

This is known as the "2D bin packing problem". It is NP-complete, meaning that there is no known algorithm to do it efficiently. It's a very important problem because of its applications to microchip layout. Depending on your exact needs (correctness, statistics of rectangle sizes, overlap tolerance) there are a few inexact ways to get pretty good guesses. What are you trying to accomplish?

It's quite simple really there are a tonne of uses for this type of function in 3d graphics. I need a way to pack images into textures. For simplicity sake let's talk about a bitmap font generator. I measure all the characters in a font and need to draw them in the smallest power-of-two sized texture ie. 128x128, 256x256, 512x512 and so on.

Currently I just measure all characters and get the largest character and use the following algorithm to get the texture size that will fit.



It obviously does not optimize the space available in the texture by using the largest sized glyph. It does not have to be the best possible packing system but something that just packs them based on size rather than largest size and in the end get better usage of the texture space.

Another consideration is say I have a bunch of images to pack into a texture, if they exceed the maximum texture size of the video card I will need to pack the rest into the next smallest texture size.

Quote:

It's quite simple really there are a tonne of uses for this type of function in 3d graphics.

I'm not quite sure how the above relates to Sneftel's post, but anyway, just in case it wasn't clear, Sneftel gave you a term that will help you find information on this subject: 'bin packing'. It's a well-documented topic, and there are plenty of resources of various types geared towards generating bitmap fonts, building lightmap textures, etc.

Depending on whether you need to do this in real time or if it can be done as a pre-processing step, you might be able to use an existing solution, such as the AngelCode bitmap font generator. Otherwise, you may need to write your own code, or find some existing C code (I have some bin-packing code lying around, but it's in C++).

I did this a few months ago when making my texture atlas maker. The best performance seemed to come from:

1. Take a guess on the initial size. You know the final width must be >= the width of the largest item width, height >= largest item height, and area >= sum of the areas of all items. You can add extra if you want to be sure it will work on the first try.

2. Sort all rectangles by their area so the largest rectangles get packed first.

3. Use a binary tree to pack all the rectangles. Every time you need to add, just crawl the tree until you find a place it can fit.

4. If you had any items that did not fit, you can repeat with a largest base rectangle size.

When testing it, it was packing something like 10,000 textures into a 4096x4096 atlas in around ~200ms. So the binary tree approach was definitely efficient from a performance standpoint. As for efficiency... it was quite good. Definitely good enough for a texture atlas.

As for how to use the binary tree to do the inserts, I recommend this link:

http://www.blackpawn.com/texts/lightmaps/default.html

you should research on what sneftel said..."2d bin packing" even try "1d binpacking","np complete"...btw i think "container loading" is closer to what you want,you should try researching on that too...and just a piece of advice dont go straight ahead to "3D bin packing" without learning the 2d one or else you will get VERY VERY LOST!!! good luck on your research!

jyk: When I say C code, I'm actually coding in C# but C or C++ is fine I can read them all. So if you have that example code lying around that would be great to have a look at. I find it alot easier to get the concept by looking at code rather than the mathematical equations and explainations you usually find when researching algorithms.

Speaking on AngelCode, I contacted him a while back asking about the same thing. This is what he had to say:

Quote:

The algorithm is rather simple. First you order all the glyphs by their height, then you simply start from the left to right and place the glyphs in the texture as far up as possible. When you reach the right edge, try to find a glyph that fits in the remaining few pixels, and then start over from the left edge.

I wanted a more generic solution that will work with any graphics so I can apply it to different areas of my engine. The reason why I can't use AngelCode's bitmap font generator is because I need to be able to use any font installed on the system so pre-rendering it is not an option. I already have the code in place for generating a bitmap font it just uses the maximum glyph size at the moment.

I appreciate all the feedback.

You can find my code here. I'm sure you can find better code elsewhere, but at least this gives you another option to choose from. (I do know that the code in the linked thread has been used successfully by people other than myself, so I'm fairly confident that it works as advertised.)

Thanks alot jyk that link is very helpful. There is also a link to a tutorial there that the OP used to success. So I have some great places to start now *rubs hands together*