2D (Texture) Allocator

Sorry, no ready-to-use algorithm at hands (bin-packing isn't easy), but atleast an idea with some assumptions (pseudo-code).

Assumption: all sub-textures are of the size 2^y x 2^y, the maximum and minimum size is know as MAX and MIN

//create a list for each texture size (buckets) to hold texture sections of size MIN to MAX
texture_buckets = ...

//subdivide the texture in equal areas of the largest size and assign all sections to the according highest-index bucket
...



// request method>>

// requested a new section (parameter)
const int requested_bucket_index = X ; // 2^X = size of texture side

// check buckets
int bucket_index = requested_bucket_index;
while(bucket_index<=MAX_INDEX && texture_buckets.getSubTextureList(bucket_index).isEmpty()) 
{ bucket_index++; }

// no free texture found ?
if(bucket_index>MAX_INDEX) {
   .. ERROR HANDLING..
}

// get free texture section
TextureSection* texSec = texture_buckets.getSubTextureList(bucket_index).pop();

// subdivide requested texture ?
while(bucket_index>requested_bucket_index) {
  // subdivide
  TextureSection* subdividedTexSec[4] = texSec.subdivide();
  
  // reduce bucket index
  bucket_index--;

  // keep first, reassign others
  texSec = subdividedTexSec[0];
  texture_buckets.getSubTextureList(bucket_index).push(subdividedTexSec[1]);
  texture_buckets.getSubTextureList(bucket_index).push(subdividedTexSec[2]);
  texture_buckets.getSubTextureList(bucket_index).push(subdividedTexSec[3]);
}

// done
return texSec;

I had to deal a similar problem a while ago and after a while noticed that I found a lot of people talking about it on sites like stackoverflow and there was always this link and/or this corresponding document referenced. It certainly solved my problem back then and although I don't have much experience in the area someone who had been dealing with different bin packers in the past commented the results certainly look much nicer.

I have some reading to do.

Thank you.

L. Spiro

Stupid way to go about it, but you could design a format where atlasing data is part of its linear sequencing.

Such in the way you can rapidly stream specific data when needed by an array algorithm.

Bin-packing is fun. It's also NP-hard. You are going to want to carefully restrict the problem space, in order to reach a (relatively) simple solution.

It may or may not work for your specific needs, but a great simplification is to separate the desired images into buckets of similar size/shape, and then have an atlas for each bucket. Within each bucket, you can treat all the images as the same dimensions, making packing trivial, and you can place multiple buckets in different sections of a large texture, if speed is of the essence.

You are going to want to carefully restrict the problem space, in order to reach a (relatively) simple solution.

Indeed.
Two decisions I made yesterday: The requests must be square except for special-case ones which will have a 1×6 ratio, and the 1×6-ratio ones will all be allocated first.
I’m not sure if I can also enforce that all requests be power-of-2 (except for the special-case one, which also may have a specialized allocation path) but it would help if I can.


L. Spiro

Minimizing unused space in the texture is a false objective. You need texture space for each sprite you use simultaneously, and it might as well be reserved from the start; copying the texture atlas content to a newly allocated bigger texture, like std::vector in C++ does when it outgrows its buffer, is unneeded work and it requires more memory (old and new texture, instead of only the larger one).

Technical constraints are important.

• Do you deallocate sprites after they cease to be used?
• Do you use POT texture atlas sizes or arbitrary ones? In the former case the bin packing wouldn't need to be close to optimal, just good enough to fit everything into the minimum POT texture size.
• Do you have only one big texture, or can you split the atlas into multiple textures? Can you draw from multiple textures efficiently?
• Can you dispense with the complexity of assembling a traditional texture atlas and use OpenGL array textures (GL_EXT_texture_array) or the like to keep sprites separated instead?

You probably have good information about the statistical distribution of texture sizes and the temporal patterns of allocation and deallocation of various sizes. This data should allow you to choose good heuristics. For example:

• If you know you have at most N_i sprites of each size w_i over the whole lifetime of your texture atlas, you could run your bin packing offline to reserve spaces in the texture and hand them out in constant time, with a simple free node list for each size w_i.
• If you know that after sprites of a certain size start being deallocated no new ones will be allocated, you can irreversibly recycle deallocated texture spaces of that size as multiple free spaces of any smaller size you need, without bothering with quadtree organization.