fullpacirish

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. And this was my first hit:Here's a summary: build a binary tree.

• 2d Bin Packing Software Piracy 2016

2d Bin Packing Software Piracy 2016

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.