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 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? :)
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
I have invented my own algorithm for rectangle packing (though I'm quite sure someone else came up with the idea before). I wanted for it to be fast during runtime so I could use it to cache font characters and other small bitmaps on the fly.
All it does is try to place any new rectangle as high in the bin as possible. To quickly locate the position that allows this, my algorithm tracks the silhouette of the upper end of the bin (as a sorted list of "runs" or "slices", telling where on the X axis the run begins and how high it is on the Y axis). When a rectangle is inserted, it will attempt to put the rectangle at the start of each run with its left edge and then with its right edge. The placement that allowed for the highest placement is selected and the list of runs will be updated accordingly.
The algorithm averages on O(1) because once a full row of rectangles has been built, the search time for new rectangles tends to stay constant. Worst case performance could be O(n) but is very unlikely.
Professional C++ and .NET developer trying to break into indie game development. Follow my progress: http://blog.nuclex-games.com/ or Twitter - Topics: Ogre3D, Blender, game architecture tips & code snippets.