algorithm - 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.

question from:https://stackoverflow.com/questions/8762569/how-is-2d-bin-packing-achieved-programmatically

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.