Another project I want to start on this blog is posting solutions to various problems I’ve solved in the hopes that they might be useful to someone else. One such problem is packing a bunch of small images into a large texture. This is important for rendering speed since switching textures means a new draw call. This “image-packing” concept is often called a “texture atlas.” A lot of modern game engines handle this for you, but I think algorithms are cool and I’m sure someone else does too. Or maybe you’re making you’re own game engine! (NB: Making your own engine is probably a bad idea unless you want to learn or have a really good reason not to use something like Unity.) Anyway…

The algorithm works by conceptualizing a texture that grows from the upper-left as a space that can be partitioned off using binary tree nodes branching right and down that each are either exactly-sized to contain an image or are leaf nodes representing unallocated space. (I’ll provide links to example code at the end.)

Originally, the entire texture is the empty root node:

Whenever a new image is added, there are 3 possibilities:

In this case, the image is just inserted into that node and nothing else happens.

Here the node is resized to match the image and then a single new node is created for the unused space in either the “right” direction (matching height) or the “down” direction (matching width).
Or

Here the node is resized to match the image and then 2 new nodes are created for the unused space. The new nodes are “sliced” in 2 possible ways depending on which one will leave a larger empty node behind.
Or

As the tree expands, this process is repeated, packing in more images with the leaf nodes representing unallocated space:

An important optimization happens before any actual packing is done- all images are sorted so larger ones are packed first. Just like in a moving van, it’s much easier to find a spot for the little stuff last!

The insertion node for an image is chosen by traversing the tree looking for the closest empty node to the upper-left that is also big enough. Since the largest images were sorted to be first, this means we are packing the biggest things “in the back.” Again, just like a moving van!

If no empty node is big enough for the image, the texture is alternately expanded horizontally / vertically to the next power-of-2 size. (See the BONUS at the end for something super-cool!)

*This class was extracted from a large project with some external dependencies, but it’s minimal and the core algorithm should be portable. The most interesting functions are GetEmptyNodeOfSize and RecursivelyFindClosestFittingNode.

*BONUS:
Learn this one weird trick from a local man for testing if an integer is a power-of-2!

n > 0 && (n & (n – 1)) == 0

Save billions of divides every month from your home! CPU manufacturers hate him!
How it works:

1) If n is positive and a power-of-2 (say 8 for example), then:
2) Only 1 of its bit will be on. (1000, if n = 8)
3) n – 1 will have that 1 bit off but every lower bit on. (0111, if n = 8)
4) Therefor bitwise AND of n and (n – 1) will be 0. (1000 & 0111 = 0, if n = 8)