.NET Tips & Tricks

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:

	The Simple Packer 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.
	The Cygon Packer Named 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).
	The Arevalo Packer 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.

You can download the C# version of the algorithms from here.

The usage is very simple :

	Point PP;
	var ARP = new ArevaloRectanglePacker(200, 200);

	if(!ARP.TryPack(Width, Height, out PP)) {
		// Do something
	}
	else {
		// Do something else
	}

A few posts you might find interesting:

1. C# Image Processing with AForge.NET Framework
2. SpeedTrace – .NET Profiler and Tracer
3. Image Resizing in C#
4. C# The “double” trouble
5. C# string.Empty vs “”