Hello,

the topic of bin packing comes up quite often at GameDev that we have a thread roughly every month or two about it. Rectangular bin packing comes up in contexts of light mapping, texture atlasing, font glyph caching, sprite packing and RPG-like tetris inventory organization. Most of the veterans here are surely familiar with this topic.

Last August I was in turn to approach this problem, and around the same time, I had to write a smallish academic study about a topic of my choice. Now that the stuff is finally done, I thought I'd share the results here, as so many people work on these things. Hopefully someone can find this material useful.

The results of my study are available here: A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing (pdf).

Along the way, I've written three blog posts to accompany the paper:
Rectangle Bin Packing:The recursive GUILLOTINE algorithm, a sample video.
More Rectangle Bin Packing:Videos and explanatory pictures about the SHELF, (iterative) GUILLOTINE, MAXRECTS and SKYLINE variants.
Even More Rectangle Bin Packing:Downloadable source code, links to resources.

Any feedback on the contents is greatly appreciated.

Here's a short catalog of some of the more informative threads that have come up here at GameDev:
6/15/2003, Algorithm to pack items into container: Algorithm discussion, Shelf method.
5/11/2006, Rectangle packing: jyk shares his code that implements the Guillotine method.
4/28/2007, Fitting small rectangles into a large rectangle: utilae shares his implementation of a bin packer. Some discussion about optimally solving bin packing.
11/2/2007, Need AI to fit rectangles in a larger square: Algorithm discussion.
2/5/2008, Automatic Texture Atlas Generation: Discussion on rectangle packing atlases.
11/22/2008, Packing rectangles into a rectangle: Q&A on rectangle packing and jyk's code.
12/23/2008, How to merge multi small pngs into a single one with smallest size?: Performance considerations.
5/24/2009, Allocating a texture large enough to hold all font glyphs: Font glyph caching.
8/17/2009, Lightmap generation with Radiosity: Bin packing in the context of lightmapping.
8/23/2009, Freetype: Font glyph caching. My initial results on bin packing.

The motivation of this post is not only to sum up a list of links from my behalf, but to ask all you guys, how do you do it?

Now, there's quite a lot of links in this post. No need to bother going through all of them before replying, as that could take quite a lot of time! Just if you have your material on bin packing, please share it here! Code, knowledge, or pretty pictures at least? :)

The paper looks good, and quite comprehensive. Nice job! :)

Thanks! Assembling the stuff together did take some time. Unfortunately I had to draw the line somewhere, and didn't include some of the more interesting ones of recently published methods (least wasted fit, caving degree, corner-occupying action). If someone's got extra free time on their hands, there's a good topic to go for. :P

Sorry to bring up an old thread, but since my website went down, the links referred to above no longer work. Someone was looking for the code and PDF files, so I'm attaching them here instead:

[attachment=5209:RectangleBinPack_backup.zip]

The algorithm you describe sounds like the SkyLine algorithm I studied for the review. (though, I did not maintain a sorted order if I remember correctly)