A hard problem
Finding the smallest rectangle that holds a given set of rectangles without overlap is NP-hard. Deciding whether a set fits a given box at all is NP-complete. Huang and Korf set this out in their 2012 paper, which traces both results to bin packing. In practice, no known method finds the best answer quickly once the set grows large.
Their benchmark makes the point. Pack squares of size 1×1, 2×2, up to N×N into the smallest box. For N = 32, the best box is 85 × 135. Their packer extended the known answers from 27 squares to 32.
Where the idea came from
Chip designers meet the same puzzle. Floorplanning places functional blocks on a silicon die, and in its classic form the goal is the smallest area. The first ZeroSprites, a command-line script and a website that ran until 30 October 2020, borrowed two tools from that field:
- rectpack, Huang and Korf's optimal packer. It finds the true smallest box, but only for small sets, so the script gave it a 20-second limit.
- btree, from Chen and Chang's floorplanner. It finds good, not perfect, answers for large sets.
ImageMagick then drew the sheet from the coordinates.
The B*-tree, briefly
A B*-tree stores a packed layout as a binary tree. Each node is a block. A left child sits directly to the right of its parent, touching it. A right child sits above its parent, at the same x position. Read the tree in order and every block slides down and left into place, so any tree gives a tight, legal layout.
Chen and Chang's floorplanner improves the layout by simulated annealing. It makes small random changes to the tree, keeps the ones that help, and sometimes keeps a worse one early on to escape a dead end.
What this version does
This ZeroSprites runs entirely in your browser, so it uses a packer fast enough for JavaScript:
- Pad. Your padding is added to each image's width and height, then trimmed off the outer edge of the finished sheet, as the original script did.
- Pick widths. It starts from the square root of the total sprite area, the width of a perfect square sheet, and fans out to hundreds of nearby widths.
- Place. For each width it places the sprites with the MaxRects method. It keeps a list of every free rectangle and drops each sprite into the free space that keeps the sheet lowest and fits tightest.
- Vary. It repeats with five sort orders (tallest, widest, largest area, longest side, longest perimeter) and three placement rules.
- Keep the best. The smallest sheet wins. A long thin strip pays a penalty of up to 5%, so a near-square sheet of almost the same area beats it: square sheets are easier to check and fit texture size limits. A sheet with zero empty pixels ends the search early, because nothing beats it.
The search stops after about a second, or two and a half for very large sets. The studio shows how many layouts it tried and how full the winning sheet is.
Rules it follows
| Rule | Why |
|---|---|
| No rotation | CSS backgrounds cannot rotate a slice of an image, so every sprite stays upright. |
| Whole pixels | Every sprite starts on a whole pixel, so nothing blurs. |
| Input order kept | The CSS and JSON list sprites in the order you added them, wherever they land on the sheet. |
| Power of two, square | Optional shapes round the sheet up after packing. |
References
- Huang, E. and Korf, R. E. (2012). Optimal rectangle packing: an absolute placement approach. Journal of Artificial Intelligence Research, 46, 47–87. doi:10.1613/jair.3735
- Chen, T.-C. and Chang, Y.-W. (2006). Modern floorplanning based on B*-tree and fast simulated annealing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(4), 637–650. doi:10.1109/TCAD.2006.870076