Rectangle packing


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.

Post a comment or leave a trackback: Trackback URL.

Comments

  • villekoskela  On August 13, 2012 at 6:45 am

    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.

  • gonzo  On August 13, 2012 at 4:19 pm

    Great, these days I was thinking to start with work on something similar. You saved my time. Thanks.

  • villekoskela  On August 14, 2012 at 6:50 am

    The latest version of the source code is now available in GitHub. Updated also the demo to use the optimized version.

  • cromantin  On September 4, 2012 at 6:09 pm

    It’ll can be even better if you will rotate rectangles

    • villekoskela  On September 6, 2012 at 6:59 am

      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.

  • Pham Tien  On January 17, 2013 at 11:34 am

    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 :)

  • xLite  On January 24, 2013 at 8:49 pm

    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);

    • villekoskela  On February 22, 2013 at 11:17 am

      The algorithm works so that it needs the initial limits for the area.

  • Martijn Croezen  On February 2, 2013 at 1:28 am

    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;

    • villekoskela  On February 3, 2013 at 11:02 am

      Good catch. Fixed that now also to the current version in GitHub.

Trackbacks

  • By RectanglePacking | AS3 Game Gears on June 2, 2014 at 3:50 pm

    […] 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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 231 other followers

%d bloggers like this: