How is 2D bin packing achieved programmatically?

Question

There are a few similar questions on stackoverflow, but none of them seem to provide a tangible answer that someone without a solid understanding of NP-hard problems and algorithms can understand.

How does one perform 2D bin packing of rectangular objects? In my case, I'm trying to assemble several images into a single image, for use as a spritesheet, using the smallest amount of space. Each image possibly has wildly different bounds, but there is no set bounds to the container.

I was hoping someone with an understanding of bin packing algorithms could explain how this can be achieved programmatically, rather than providing a general overview of the bin packing method.

Fairfax

codeproject.com/KB/web-image/rectanglepacker.aspx – Decani

I actually read that article quite thoroughly, and while it did improve my understanding of bin packing, its example implementation relies heavily on constructs only available in C#. Even after reading through the source code provided, I have no idea how he accomplishes some of the necessary steps. – Fairfax

Answer 1

I Googled "bin packing code" and this was my first hit: http://codeincomplete.com/posts/2011/5/7/bin_packing/

Here's a summary: build a binary tree. Each branch in the tree contains a sprite. Each leaf node represents available space. Initially the tree has just the root node, which represents all available space. To add a sprite to the tree, search the tree for an unoccupied (leaf) node big enough to hold the sprite. Turn that node from a leaf into a branch by setting the sprite as the node's occupant and giving the node two children. One child represents the remaining space to the right of the sprite; the other represents the remaining space below the sprite and the first child.

The article I linked above explains this much more fully, with diagrams and JavaScript code. It also explains how to dynamically grow the sprite sheet rather than choosing a fixed size in advance.

Jujutsu

I tried it, and it doesn't work very well for the limited rectangle version when you put arbitrary rectangles: i.imgur.com/YaGlGNN.png – Beside