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:

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

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:

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

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

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:

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.

Last Updated (Tuesday, 20 April 2010 01:13)