Original Post
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 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? :)
