Sometimes, you're faced with the problem to cramp as many smaller textures as possible onto a larger texture. Typical cases are lightmaps, which are very small textures with dimensions that usually are not powers of two, or bitmap fonts where you want to try and fit the entire ascii character set onto a texture without wasting much space.
What you need then, is a rectangle packer, an algorithm that arranges as many smaller rectangles on a larger rectangle as can possibly fit.
The Nuclex.Support assembly contains several rectangle packing
algorithms in the Nuclex.Support.Packing namespace offering
various levels of compromises between space efficiency and runtime
performance. All of these algorithms have been implemented as classes with
a common interface, so, once implemented, you can easily switch forth and
back between different algorithms to find the one best suites for
your purpose.
Currently, there are three different packing algorithms for you to choose:
| Packer | Average Result | Time Taken | Example |
|---|---|---|---|
The Simple PackerThis packer is optimized for runtime performance. It does sacrifice a bit of space, but the time needed to find a position for a new rectangle is O(1). In english, that means it doesn't take longer to search for a suitable position, no matter how many rectangles have been added to the packing area. |
406.995 rectangles |
0.016 seconds |
|
The Cygon PackerNamed after your humble webmaster, this algorithm is highly efficient in its space usage and offers reasonable performance. It will never exceed O(n) time but generally achieves almost O(1) on average. English translation: Search time is usually constant and guaranteed to never exceed a linear increase (so when you've got 99 rectangles already packed and add the 100th one, it guarantees that search time will at most be 1% longer than the time taken for the previous rectangle). |
582.820 rectangles |
0.422 seconds |
|
The Arevalo PackerNamed after Javier Arevalo, who posted his implementation of this packer on flipcode back in the golden times. This algorithm offers very good space efficiency and runs in slightly less then O(n) time. Just to be consistent, in english, that means, the time needed to find a suitable place for a new rectangle will only increase linearly. |
569.845 rectangles |
108.983 seconds |
|
Sources
The source code to this is part of my "Nuclex Framework" project. I haven't had the time to set up a nice project page with downloads and illustrations yet, so if you're interested in the sources, just view them here: https://devel.nuclex.org/framework/browser/game/Nuclex.Game/trunk/Source/Packing ;-)