Something for example Starling framework is still missing is a rectangle packing utility with which you could generate a texture atlas on the run-time. After some Googling I didn’t come across with too good examples so I spent couple of hours to write one of my own. Since this is a freetime project of mine I am this time also releasing the source code.
Rectangle packing
The idea in rectangle packing is to place smaller rectangles inside a bigger container rectangle as tightly as possible. This is especially useful when generating big textures containing many sub textures. My implementation uses the concept of “free rectangles” within the main rectangle. The packed rectangles are always placed in the top left corner of some free rectangle that they completely fit into. To get very close to optimal packing the top most of the left most free rectangles the packed rectangle fits into is selected for placing.
The algorithm
Initially there is naturally only one “free rectangle” that is the main rectangle itself. After packing the first rectangle in the original free rectangle is removed and there are from zero to two new free rectangles – if the packed rectangle is as big as the container there are no more free rectangles, if the packed rectangle is as wide or as tall as the container there is one free rectangle either below or on the right side of it and if the packed rectangle is smaller there is one free rectangle below it and one on it’s right side. Packing next rectangle happens the same way – also any other free rectangle the packed rectangle intersects is cut into new smaller free rectangles around the packed rectangle. During the process all the free rectangles that are fully contained by another free rectangle are removed.
The image below shows how the free rectangles are combined. The image on the left side shows that there are two free rectangles after placing the first rectangle. Placing the second rectangle would divide the free rectangle “2” into two new free rectangles (on the right side and below) and also the free rectangle “1” into three new free rectangles (above, on the right side and below) but here two of these new free rectangles are completely contained in the bigger free rectangles so the total amount of free rectangles after packing the second rectangle is three.
To see this rectangle packing in action click the image below. Drag the orange circle at the bottom right corner of the container rectangle with your mouse (keeping the left mouse button down) to see how packed rectangles move around the area. With a decent computer the packing of 500 rectangles takes about 1 millisecond.
You can download the full source code for the demo GitHub.
Like the copyright notice in the source files says you may use and/or modify the source code freely but do not remove the copyright notice or move the files into other packages. If you find the utility especially useful you can mention me in credits too.
Update: The version available since 22nd of August 2012 almost 10 times the speed of the original one.
villekoskela 
Comments
I managed to almost double the packing speed with 500 rectangles so I will update the source code soon (I’m also starting to use GitHub for that) so come back in couple of days to get the updated version.
Great, these days I was thinking to start with work on something similar. You saved my time. Thanks.
That’s nice to hear.
The latest version of the source code is now available in GitHub. Updated also the demo to use the optimized version.
It’ll can be even better if you will rotate rectangles
Yes, rotating would help how tight the rectangles are packed and it might also still improve the speed if the short side is always the horizontal side but then the classes using this utility would also need to support the rotating.
Great! I’m making a game where we need to load separate images from server and pack all of them for performance. I’ll give it a try 🙂
Will there ever be an option to NOT specify the width and height? I want to use as small a rectangle as possible so I’d prefer if the class automatically chose the smallest size rectangle once all the rectangles were sorted.
Something like:
packer.packRectangles();
trace(packer.newWidth);
trace(packer.newHeight);
The algorithm works so that it needs the initial limits for the area.
Found a little bug.
I was trying to automatically determine the minimum size container for a certain collection of rectangles. by trying different sizes, to see when all rectangles fit. however, i saw a little bug, on a reset(width,height) you’re not changing the mOutsideRectangle x and y. I added these lines at the beginning of the reset function, and all is working fine again:
mOutsideRectangle.x = width + 1;
mOutsideRectangle.y = height + 1;
Good catch. Fixed that now also to the current version in GitHub.
Trackbacks
[…] RectanglePacking is a utility class to pack smaller rectangles within larger container rectangle efficiently. Built is efficiency in mind, the algorithm can pack 500 rectangles in 1-2ms on a decent computer. The implementation uses the concept of “free rectangles” within the main rectangle. The packed rectangles are always placed in the top left corner of some free rectangle that they completely fit into. […]
[…] thing to do was a packing algorithm. Fortunately we remembered the one made and open-sourced by Ville Koskela in AS3, so we started with a Unity C# port. Click here to view the Unity rectangle packing example […]