Quickly allocating sub-textures out of a main texture

[Burton Radons]

Hey all, what I need to do is allocate sub-textures from a main texture and discard them as needed. What I currently use is a quadtree with leaf nodes being coloured with a pointer to which subtexture that leaf is used by; I search for any region containing only null pointers to add a new subtexture. Quick and easy.

The problems are that this creates a LOT of nodes that are hard to optimise and that searching for new subtextures can require visiting every node multiple times. About the only benefit is that it's easy to remove nodes, but everything else gets exponentially more expensive as more subtextures are created from the texture.

So does anyone have or can think of a good design for this? The requirements are:

- Needs to be able to add new subtextures of any size to the texture, meaning both quick insertion and searching for unoccupied areas.
- Needs to be able to remove subtextures and then reuse that space if possible.
- Needs to do this in realtime.
- Does not need to be pixel-perfect.

I've encountered these packing problems before (such as in generating a graph for texturing a model) but they haven't been realtime.

[Burton Radons]

Here's an approach I just hammered out. I separate an image into a list of regions. Each region is a 1.5-dimensional array of tops, bottoms, and lengths, like this:


struct Strip
{
Strip *next, prev;
int length; // The horizontal length of this strip.
int top, bottom; // The vertical top and bottom of this strip.
}

struct Region
{
int start; // First X coordinate.
Strip *first, last;
}

struct Image
{
Region [] regions;
}The image initially contains a single region with a single strip encapsulating the entire texture. To allocate an area, I search through each region, then through each strip, trying to find an area from the start of the strip which fits into it and those next to it. When I do, I merge strips and adjust their tops to cover the area that's been allocated, then I (if necessary) create any number of new regions for the areas which are above the newly allocated rectangle and are therefore orphaned.

For freeing an area, I search for regions which are adjacent to that area and push down their bottoms as needed. I should then merge regions as possible but I haven't done that yet. That will be an expensive operation, but that's alright.

This works a lot faster than the quadtree and is better because there's no waste in the structure, and it's simpler besides. I could also maintain the area that a region contains and the maximum vertical gap so that I don't bother searching all the tiny slivers produced.

[V-man]

What is this about? You are putting lots of small textures in a large 4096x4096 texture or what. You don't provide any kind of technical details. Not even if you are using shaders or doing this on the CPU.
Why use a quad tree instead of something very simple? You are changing subtextures every frame?

[Mikkel Gjoel]

Burton - I'm currently looking at the same problem (and yes, I need to change subtexture-sizes each frame). I find your description a bit hard to follow though - could I get you to explain a bit further, maybe create an illustration? :)
<edit>
something like this?

http://www.userwebs.dk/gjoel/regioner.jpg
</edit>