Rectangle Packing

A rectangle packer tries to place as many rectangles of different size onto a larger area as possible while minimizing the space wasted. It's similar to when you want to load boxes into the back of your car: with a clever arrangement, more boxes will fit into the car.

Rectangle packing is a complex topic that often occurs in game development when programmers try to reduce the number of texture switches by placing multiple smaller textures in a larger one. The XNA sprite font rendering system, for example, has to place the pictures for its letters onto a texture that is as small a possible.

A naive approach might just put these letters in a regular grid, but by intelligently arranging the letters to minimize the wasted space, more letters can fit onto a single texture, saving video memory and allowing for larger font sizes.

Nuclex.Game provides 3 rectangle packing algorithms you can use without researching the topic. You just specify the size of your packing area in the constructor and ask them for a good place for a rectangle - which they provide, until the packing area is full.

SimpleRectanglePacker

SimplePacker.png

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

Benchmarks
Rectangles from 20x20 to 32x32 in a 512x256 packing area: ~340 rectangles in ~0 ms
Rectangles from 8x8 to 16x16 in a 512x512 packing area: ~1500 rectangles in ~0 ms

CygonRectanglePacker

CygonPacker.png

Named after its humble creator, this algorithm is quite efficient in its space usage and offers good 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).

This is a very good compromise between space-efficiency and time-efficiency. It's actually almost as good as the most space-efficient algorithm, but runs nearly as fast as the !SimpleRectanglePacker.

Benchmarks
Rectangles from 20x20 to 32x32 in a 512x256 packing area: ~410 rectangles in ~1 ms
Rectangles from 8x8 to 16x16 in a 512x512 packing area: ~1740 rectangles in ~13 ms

ArevaloRectanglePacker

ArevaloPacker.png

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

This algorithm is useful if you want the best possible result for offline packing, since performance degrades rapidly when the number of rectangles increases.

Benchmarks
Rectangles from 20x20 to 32x32 in a 512x256 packing area: ~420 rectangles in ~190 ms
Rectangles from 8x8 to 16x16 in a 512x512 packing area: ~1800 rectangles in ~12,500 ms (12 seconds, no typo)

Usage

This is pretty straightforward, so a simple code example should suffice:
CygonRectanglePacker packer = new CygonRectanglePacker(1024, 1024);

// Find a place for a rectangle of size 30x20 in the packing area
Point placement;
if(packer.TryPack(30, 20, out placement)) {
  // Successfully packed, placement contains position of upper left corner
} else {
  // Packer ran out of space
}

Last edited Sep 12, 2009 at 7:42 PM by Cygon, version 4

Comments

kosta_kosta Mar 31, 2010 at 8:37 PM 
Great work!!!

I have one question...I have 10 rectangles, and these engines only sort them in landscape order, they do not try to rotate some of them for the best fit (this would provide minimum the space waste ) !!!
I read some articles and this algorithm name is Guilottine Cut!
Is there any chanse , to modify these algorithms for the best fit, or could you provide Guillotine Cut solution?

Again, great work, and thanks anyway!