CodePlexProject Hosting for Open Source Software

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.

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.

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

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.

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

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.

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)

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 6:42 PM by Cygon, version 4

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!

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!