An Abstract Algorithm To Augment Alpha'd Atlases

Texture atlases are routinely used to improve rendering performance (fewer texture swaps) and reduce memory footprint (especially on power-of-two-texture hardware).

In the specific case where textures are irregular sprites with an alpha channel (for 2D games and UI elements), there is an opportunity to save additional memory by eliminating most of the redundant blank space around the edges of the images.

Normally this is done by hand, if it is done at all: manually placing images within a larger texture and then defining irregular polygonal areas for each sprite. This can become burdensome if the number of images is very large or images change frequently.

The algorithm described here achieves significant savings (around 25% of total texture space on a sample commercial mobile app) without any user input and without excessive processing.

Outline

• For each image you want to add to the atlas:
• Find the initial bounding rectangle within the original image. This is how much room the image would take up if committed to the atlas unchanged.
• Find the left and right extents of every horizontal line of the image.
• For every possible horizontal slice you could take out of the image (ie, every possible y_top and y_bottom that you could cut across in order to extract a slice)
• Estimate the savings that would result if that slice were extracted and the empty space at either end cropped.
• Because atlasing images requires that a pixel gap be left to prevent bleeding, reduce each estimate by the number of duplicate pixels needed.
• Then, while savings remain to be made:
• Find the best remaining slice (the one that saves the most memory if extracted on its own)
• Examine every combination of two contiguous slices (ie, <y_top to y_middle> and <y_middle to y_bottom>) that would together cover that 'best slice', and find the most memory-saving combination (if there is one).
• Take whichever is the most memory-saving individual slice of that 'best pair'
• Mark that vertical span of the image as 'done'.
• Repeat until no further savings can be made.

Once you have your slices, add them to a master list and feed them (rather than the original images) into a standard texture-atlasing algorithm. It's then straightforward to auto-generate geometry that stitches the image back together from its parts. The example below uses wireframe to illustrate how a rectangular image (of a shopping basket) is automatically broken up into smaller, individually atlased sections and then reassembled at render-time. The yellow area is background and not part of the atlased image.

In practice, the overhead of transforming the extra geometry is (especially on hi-res mobile platforms) more than compensated for by fill-rate savings.

Other Considerations

• Slices of an image should ideally all be kept together on the same atlas, which does require extra computation (since atlasing algorithms usually sort input images by height, which tends to mix all your image slices up together and then spread them across however many atlases you end up using)
• As well as the 'duplicate pixel' cost of splitting an image, you must also factor in the memory consumed by the extra geometry (which will depend on your implementation).
• If you wish, you can further decrease estimated savings by a 'transformation tax', to represent the performance penalty of transforming additional vertices versus savings in fill rate.