Dumb question: it seems like this assumes that once you have allocated a spot within an atlas, you can't move it. But wouldn't it be a within-GPU transfer to garbage collect a fragmented atlas into a new texture?

If so, then could you do a fast but messy allocation, then clean it up when you run out of space, or are about to? Or you could pull in more traditional GC tricks: have one texture that gradually accumulates long-lived images (the tenured region), and divide up another region into two semispaces that you do fast bump-like allocations into and then compact from one to the other when it fills up. You could even incrementally repack, assume copying within and between atlases works in the first place.