I have a mesh consisting of about 100'000 - 200'000 quads. Each quad has a rectangular texture.

I'm packing these rectangular textures into a power-of-two atlas. My packing algorithm currently works like this:

  1. Calculate total area of all textures
  2. Set atlas width to sqrt(total_area), rounded up to next power-of-two.
  3. Sort all textures by height (tallest first).
  4. Start in bottom left corner of texture atlas and fill the atlas in rows left to right.
  5. The height of first texture in a row defines row_height.
  6. Place texture into atlas and advance by width of texture to the right.
  7. If the height of a placed texture is less than row_height, try to fill that 'gap' at the top with smaller textures and remove these filler textures from the sorted list.
  8. If there's no space to the right for the next texture, try to fill the gap to the right with smaller textures and remove these filler textures from the sorted list, then move the cursor back to the very left of the atlas and up by current row_height, go to step 5 and continue until all textures have been placed.
  9. crop atlas height to smallest possible power-of-two.

Now, this works very well and if the total texture area is close to a power of four, I get almost optimal atlas usage.

However, now I would like to optimize the atlas for cache coherence by trying to place textures of quads that are likely to be rendered together close-by each other.

Each quad is assigned a 2-D point in the [0,1)x[0,1) square. If the points of two quads in this parametrization are close by each other, the quads are likely being rendered together, so I would like to pack the corresponding textures close by each other in the atlas for better texture cache utilization (I'm aware textures are kept in morton order or similar in texture memory on graphics hardware - this can be ignored here).

I'm not looking for the optimal solution, just for a somewhat improved layout according to this metric.

My current attempt at this optimization for the algorithm described above works like this:

  1. When a row has been completed, sort all entries of that row according to the x coordinate in the 2D parameter-space of the corresponding quads.
  2. After all textures have been placed, compute for each row the median of the parameter-space y coordinate of that row, then sort all rows according to those y medians.

It's apparent that especially the second step doesn't do much, since the entries in each row have been selected by similar height but texture size and parameter-space location are uncorrelated.

So I wonder whether someone can suggest a better algorithm that helps placing the textures in the atlas while trying to minimize parameter-space distance, without sacrificing much texture area in the atlas.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.