Best-Fit Atlas Packing and the Cost of the Free List

A texture atlas exists because changing textures between draws is expensive. Put many images in one texture, and everything using that texture can be drawn together. The whole benefit is batching, and the atlas is the mechanism.

Which turns the interesting part into a packing problem: given a rectangle of fixed size and a stream of smaller rectangles arriving at unpredictable times, where does each one go?

This is the second post taking one system out of my custom engines. The allocator here is the one piece of code that survived a full engine rewrite nearly unchanged.

It's an Allocator, in Two Dimensions

The framing that makes the problem manageable is that this is malloc with an extra axis. The same vocabulary applies: free space, fit strategy, fragmentation, coalescing.

And the same fit strategies are available. First fit takes the first free space large enough, which is fast and wastes space. Worst fit takes the largest, which keeps big holes available and fragments quickly. Best fit takes the smallest space that still works, which packs tightest and costs a full search.

The implementation picks best fit, and tracks the smallest waste seen so far:

float over = chunk.size.x * chunk.size.y - (needed.x + border) * (needed.y + border);
if (over < smallestSize) { smallestIndex = i; smallestSize = over; }
if (over == 0) return i;

Keep the early return on an exact fit. A perfect match can't be improved on, so there's no reason to finish the search, and in practice exact matches are common because games have a lot of same-sized art. One line turns the common case from a full scan into an early exit.

Best fit suits atlases for a reason that doesn't apply to heap memory. Unlike heap memory, an atlas can't grow, and a failed allocation means a whole extra texture and a whole extra draw call. Packing density converts directly into frame time, so a search to get it pays for itself.

The Border Nobody Guesses First

Every allocation reserves one pixel more than it needs in each dimension.

int border = 1;

That's not defensive rounding. When the GPU samples a texture with bilinear filtering, it reads the four texels around the sample point and blends them. At the edge of a packed image, one or more of those texels belongs to whatever was packed next door. The result is a thin fringe of the neighboring image bleeding along the edge, and it gets worse at smaller mip levels, where the filter reaches further in texture space.

The one-pixel gap gives the filter something harmless to blend with. Nobody arrives at this from first principles. It arrives as a bug report about a strange colored line at the edge of a sprite, and once seen it's never forgotten.

The first version of my allocator had no border, and the second one did. That difference is the entire visible record of an afternoon spent working out where a magenta line was coming from.

The Free List Was a Linear Scan for Years

What I got wrong, twice, is how free space was found.

The original identified an unused chunk by testing whether its filename string was empty, then walked every chunk on every allocation. So each allocation was a linear scan doing string inspection. The rewrite dropped the string test but kept the linear walk.

For an atlas with a few dozen chunks that's genuinely fine. No performance disaster ever happened, and the problem isn't the cost. It's that the data structure encodes no knowledge the algorithm could use.

A real allocator keeps free space in a structure that answers the fit question directly: a size-bucketed free list, or a tree ordered by area, so best fit is a lookup near the right size rather than a scan of everything including allocated space. That change makes the search proportional to the number of free chunks rather than to all chunks, and it makes the common case a couple of pointer hops.

I made this mistake in several places across these engines. Choosing the right algorithm and then storing its data in whatever container was nearest is a specific and repeatable failure. Best fit expresses an intent about free space, and a flat array of everything is a structure that has no opinion about free space at all. The algorithm and the structure have to agree, or the algorithm is decorative.

Coalescing, or the Absence of It

The other thing a mature allocator does is merge adjacent free space so that two freed neighbors become one usable larger hole. Mine never did.

The consequence is predictable. Load and unload enough differently sized textures and the atlas ends up as a mosaic of small free chunks with no single space large enough for anything useful, while reporting plenty of free area in total. Classic external fragmentation, in two dimensions, where it's harder to fix because merging rectangles only works when they share a full edge.

I avoided the problem rather than solving it. Atlases were largely populated once and used, rather than continuously churned, so fragmentation never had time to develop. That's a legitimate engineering answer as long as it's a decision. Mine was an accident that happened to hold.

If I were building this again for a workload with real churn, I'd either implement rectangle merging with the edge-matching constraint spelled out, or sidestep it by making chunks uniform, giving up density in exchange for never fragmenting. Which one is right depends entirely on whether the content has a natural size distribution or not, and that's knowable in advance.

The commit history makes that accident concrete. Atlasing landed on 2011-07-28. The same day, the background eviction path picked up an unconditional return at the top of its body, and the general texture eviction policy had already been switched off seven weeks before that. So from the day the atlas existed, nothing in the shipped build ever took a texture back out of it.

The allocator was safe because of a property of the system around it, and nothing in the allocator recorded that it depended on that property. Turn eviction back on two years later and the fragmentation shows up with no note attached explaining where it came from. A design that survives because of an assumption should say so somewhere the next person will read.

What Transfers

None of it is about textures.

Treat a bounded resource as an allocator and the whole existing vocabulary becomes available. Fit strategy, fragmentation, and coalescing are the questions to ask about any fixed pool, and knowing they're the questions is most of the work.

Add an early exit for the case that can't be improved. It's usually one line and it usually covers the common path.

And make the structure hold the knowledge the algorithm needs. If the search is scanning things it will always reject, the container is the thing to change, not the search.