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 