Even More Rectangle Bin Packing

This is the last post I will make about bin packing. There's two things that were missing from the previous entry, so here they are.

 

Code

The following files contain the implementations for the bin packing algorithms I used in the study.

Browse the individual source files here: http://clb.demon.fi/files/RectangleBinPack/
Or, download all the code files in one package: RectangleBinPack.zip.

I release all the code into public domain, do whatever you want with it. If you find a bug, please let me know.

Resources

I've collected here various links I found while putting the review together. The complete list of academic publications is available in the paper, but here's a more informal list of web pages that address the problem:

My two previous entries on the topic:

• Rectangle Bin Packing
• More Rectangle Bin Packing

Good starting point to 2D bin packing research using heuristics:

• Andrea Lodi, Silvano Martello, Daniele Vigo, Recent advances on two-dimensional bin packing problems.
• A. Lodi, S. Martello, and D. Vigo, Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.

Bernard Chazelle presents an excellent implementation of the bottom-left heuristics that runs in O(n^2): 
B. Chazelle, The bottom-left bin-packing heuristic: An efficient implementation.

For anyone interested in trying out other heuristic approaches than the ones described here, these might be worthwhile:

• Lijun Wei, Defu Zhang, Qingshan Chen, A least wasted first heuristic algorithm for the rectangular packing problem.
• Wenqi Huang, Duanbing Chen, Ruchu Xu, A new heuristic algorithm for rectangle packing.
• Wenqi Huang, Duanbing Chen, An efficient heuristic algorithm for rectangle-packing problem.

If you have implemented one of the above algorithms, I'd like to hear from your results. 

The ultimately most read web page on the net for practical bin packing solving for the 3D graphics people: Jim Scott, Packing Lightmaps.
The book 3D Games, Vol. 2: Animation and Advanced Real-Time Rendering also describes this same algorithm.

Rectangle packing for texture atlasing is slightly more involved due to mipmapping and filtering. See

• NVidia Texture Atlas Tools.
• GamaSutra's Practical Texture Atlases page describes how to use the NVidia's tool.
• And there is the UVAtlas (Direct3D9) tool as well.

Various people over the internet have written about bin packing in blogs and tutorials:

• John Ratcliff also describes the Guillotine method in his blog post: Texture Packing : A code snippet to compute a texture atlas.
• Hidden Games Dev Diary ponders on the effects of texture atlasing in games.
• Javier Arevalo implements what is sort of like the Bottom-Left rule: Rectangle Packing Code, by Javier Arevalo.
• Rod Stephens: Solving the 2D Packing Problem comes up with novel(?) heuristics called One/Two Columns and Fill By Stripes and also describes an exhaustive search procedure.
• DMedia has a Tutorial on Text Rendering that shows how to perform font glyph caching.
• PolliniMini.net: Rectangle Packing implements Jim Scott's algorithm in Java. It also comes with a nice web browser demo page!

And of course, our beloved GameDev.net has tons of threads from this topic. I tried to pick out some of the more informative here:

• 6/15/2003, Algorithm to pack items into container: Algorithm discussion, Shelf method.
• 5/11/2006, Rectangle packing: jyk posts 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.

There will not be a "even even more rectangle bin packing" entry, so this is it. I hope these resources provide you with a nice start to integrating bin packing into your own program, because that's all I got.

< Prev		Next >