In a previous entry, I described a simple heuristic that can be used to pack rectangles into a bin. Around the time I was writing that post, I needed to write an academic study on a topic of choice, and since I already had gathered some ideas of how it is possible to pack better, choosing this topic gave an easy start. In this article I'll summarize my results and show how to indeed perform better.
This page accompanies the paper I wrote, which is available here:
A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing.Important: Even though this study is written in academic form, it has not received any kind of critical review or proof-reading and no guarantee of correctness is given. Caveat lector.
Four different data structures were tested: SHELF, GUILLOTINE, MAXRECTS and SKYLINE. I came up with the names on my own, since I could not find any existing papers with a good naming to adopt. Using these data structures involves defining certain heuristic rules, and the different ways these rules can be defined each gives a different overall algorithm. I will not explain all of the algorithm details on this page, see the paper for more explanations.
The tests in the study consisted of benchmarks of average and worst case packing performance on synthetic data sets. On this page I will perform a different kind of test. I'll take a single example input from the context of packing font glyph caches. In this kind of packing problem, we want to maximize the occupancy rate (defined as the ratio of used surface area to the total surface area of the bin) of a single bin, instead of trying to minimize the number of totally used bins. The videos on this page illustrate the behavior of the top variants using the different data structures. It should be understood that the results are only illustrative, and should not be naively used to deem one heuristic better than the other.
The SHELF data structure
This method is absolutely the simplest of all. In academia, the SHELF algorithms are usually referred to as the "level methods". It turns out that the asymptotically best known algorithms are variants of this method.
In the SHELF algorithms, we split the bin horizontally into several shelves, and put the rectangles on those shelves. When the previous shelves are full, we create a new empty one on top of the previous ones. An input rectangle might fit into multiple shelves, in which case we use a heuristic rule to decide which shelf to put it in. The following image shows how this works in practice.
I used the SHELF-BHF-BNF algorithm to fill up a glyph cache texture with random input characters. The algorithm achieved an occupancy rate of 61.72% (with a waste map, 81.21%), which is pretty horrible. Tables turn when we are doing offline bin packing. In that case, we can avoid the worst case by sorting the input rectangles by decreasing height. The clip shown below demonstrates how the SHELF-BHF-WM-BNF algorithm produces a packing. It was the best observed case for a SHELF method in this problem. (It achieved a 95.38% occupancy rate, but this figure is not comparable to the others on this page since it was effectively on a different input). To be fair though, this is not purely a level method, since an auxiliary GUILLOTINE data structure was used for the waste map.
The point of this example is to show how sensitive the SHELF methods are to the order of the input, even when the input is "easy" and consists of several rectangles of roughly the same size, which are small compared to the size of the bin. In most cases, this method is outperformed by the other algorithms.
The GUILLOTINE data structure
This is the method I presented in the previous entry. In addition to
Jim Scott's page, the same algorithm is also described in the book
3D Games, Vol. 2: Animation and Advanced Real-Time Rendering.
In the code, I declared that one could do better. The algorithm presented in the book maintains a binary tree of the nodes, and does a recursive search to find the first free node to place the new rectangle into. This is not good, since it discards the opportunity of being able to choose which free rectangle would be the best fit for placement, and also wastes time on traversing nodes that do not have any effect on the placement anymore.
My GUILLOTINE data structure simply stores a list of disjoint free rectangles that is iterated over in a linear pass to pick the best one for placement. Different heuristic rules can be applied when deciding which free rectangle to pick, as well as when deciding which axis to split on.
The above clip shows how a packing is constructed by the GUILLOTINE-BSSF-MINAS-BNF algorithm. In the example, an occupancy rate of 90.95% is achieved.
The MAXRECTS data structure
A shortcoming of the GUILLOTINE data structure is that the split planes fragment the free area of the bin into disjoint rectangles, and new placements cannot straddle these split lines. The MAXRECTS data structure removes this limitation by tracking all the maximal rectangles of the free area remaining in the bin.
The maximal rectangles will not be disjoint, so extra care is needed to maintain consistency of the data structure when placing new rectangles. In the paper, I argue that the number of maximal rectangles in a rectilinear polygon is at most 2n^2, which gives a worst case O(n^5) time complexity for the whole algorithm. This holds if the rectangles were placed arbitrarily, but since we are placing the rectangles as conservatively as possible, the number of maximal rectangles is far less. In practice, I have observed that the number of maximal rectangles is strictly sublinear, which lends to an average-case n^3 algorithm.
The image above shows the set of maximal rectangles of the bin, slightly offset for clarity.
The MAXRECTS data structure can be used to implement two interesting heuristics:
The Contact Point heuristics. In this rule, the new rectangle is placed to a position where its edge touches the edges of previously placed rectangles as much as possible.
The Bottom Left heuristics. This rule effectively implements the commonly cited Tetris method for rectangle packing: Each rectangle is placed to a position (possibly rotating it) where its top side lies as low as possible.
Both of these variants perform very well. For the example input, the MAXRECTS-BL-BNF variant achieved an occupancy rate of 90.92%, and the MAXRECTS-CP-BNF variant got an occupancy rate of 93.35%. However, the best performance was given by the MAXRECTS-BSSF-BNF algorithm, which is shown in the above clip. The occupancy rate in the example was 94.06%.
The SKYLINE data structure
Implementing the Tetris heuristic effectively was the motivation for implementing this data structure. The SKYLINE data structure stores a horizon line that subdivides the bin into used and free parts. As new rectangles are placed, the horizon is grown to envelope the rectangles, and any possible gaps are forgotten. The following image illustrates this data structure.
To recover the gaps for future use, we use a waste map just like with the SHELF data structure. The following video clip shows the algorithm SKYLINE-BL-WM-BNF in action, which is like the Tetris heuristic.
The occupancy rate achieved in this example was 91.61%.
Conclusion
The SHELF and SKYLINE algorithms should only ever be used in conjunction with a waste map improvement (-WM), since any packing algorithm that "forgets" free space of the bin is not worth using in practice.
The Rectangle Merge (-RM) heuristic should be used with the GUILLOTINE data structure if runtime performance is not a concern, but in real-time contexts, it is better be disabled, since the packing performance gains are very small. Perhaps it would be possible to implement a better method for defragmenting the free space of the bin by restructuring the set of free rectangles completely.
The numbers on this page are results of a single example input, and they should not be used as stable indicators of performance. The packing performance of these heuristics vary significantly based on the given input, and whether packing is performed online or offline (sorting or -GLOBAL -variant).
Picking out a single best algorithm is impossible. Since the time to pack a full bin is measured in milliseconds, I propose the following meta-packer algorithm for offline packing (no kidding!):
1. Pack the input multiple times using different packing heuristics.
2. Pick the best one as output.
The MAXRECTS variants seem to have the best worst case performance, but they are slightly slower in runtime than the GUILLOTINE variants, due to the extra data structure synchronization procedure. However, this is only a concern in real-time environments. The GUILLOTINE variants can exhibit some corner cases in which their packing performance is mediocre. I do not recommend the SHELF variants to be used at all, except as a part of the above meta-packer routine. The SKYLINE variants were observed to perform better than the GUILLOTINE variants most of the time, and in my current preference, MAXRECTS > SKYLINE > GUILLOTINE > SHELF.
The final algorithm that made into my text rendering library was the MAXRECTS-BSSF-BNF variant. If I catch poor runtime performance, I will probably switch to SKYLINE-BL-WM-BNF or GUILLOTINE-BSSF-MINAS-BNF.
If I ever find myself doing lightmapping or sprite packing, I will most likely use the the meta-packer described above, or if I had to choose a single algorithm, then it would probably be the MAXRECTS-BSSF-GLOBAL-BBF variant.
< Prev Next >
