What Tree Type Is This?

Hello,

I'm looking for the word(s) to describe a particular concept of the way I want to handle a region of memory, so I can perhaps get a handle on the algorithm required to do it (I have written something, but it seems to fail after six or so relatively small regions are allocated).

Say I have a fairly large fixed-size region of memory. The size is a power of 2, allowing for the region to be visualised as a square in 2D space.

I want to allocate regions of different sizes from this. They can be rectangular in shape, but the length of any side cannot exceed that of the largest free region. The sides are also a power of 2.

The process for allocating a region involves looking at a tree of elements. Each element can be divided into two equally-sized regions if required.

The tree is searched for an element with the same width and height as the requested region.

If the current element is too large, but has children, the search continues by evaluating the child elements.

If the current element is too large, but doesn't have children, the element is split in two. The search continues by evaluating the new child elements.

Also, if two adjacent elements that are subsequently freed can form a larger element, they are merged.

I thought it was an R-tree, but the description doesn't seem to match what I was thinking. Is this more like Binary Space Partitioning (BSP)? :confused:

I also suspect that a fair amount of sorting is required for this to be particularly efficient. My current algorithm goes down the first available node chain it can find and so doesn't cluster properly. I suck. :o

Just some thoughts to clarify understanding.

> Say I have a fairly large fixed-size region of memory. The size is a power of 2, allowing for the region to be visualised as a square in 2D space.
Say 8x8

> I want to allocate regions of different sizes from this. They can be rectangular in shape, but the length of any side cannot exceed that of the largest free region. The sides are also a power of 2.
Say 4x2

> The process for allocating a region involves looking at a tree of elements. Each element can be divided into two equally-sized regions if required.
So we could have 2x2 and 2x2 or 4x1 and 4x1

> If the current element is too large, but doesn't have children, the element is split in two. The search continues by evaluating the new child elements.
Does this happen recursively, so you might end up reducing a 4x2 into 8 individual 1x1 elements?


Example, a 4x4 has been allocated.
AAAA....
AAAA....
AAAA....
AAAA....
........
........
........
........
Do you now have
- Three free regions, each 4x4
- A 4x4 in the top-right, and 8x4 in the bottom half
- A 4x4 in the bottom-left, and 4x8 in the right half

If the next request is for 2x8, which case would you end up with?

- element is not split, but the free space is now non-contiguous
AAAABB..
AAAABB..
AAAABB..
AAAABB..
....BB..
....BB..
....BB..
....BB..

- element is not split, but the free space is contiguous (if irregular)
AAAA..BB
AAAA..BB
AAAA..BB
AAAA..BB
......BB
......BB
......BB
......BB

- element is split, but the free space is uniform and contiguous
AAAA....
AAAA....
AAAA....
AAAA....
BBBB....
BBBB....
BBBB....
BBBB....

Quote:

---

Originally Posted by Salem

Do you now have
- Three free regions, each 4x4
- A 4x4 in the top-right, and 8x4 in the bottom half
- A 4x4 in the bottom-left, and 4x8 in the right half

---

Either the second or third answer is what I would expect (at the end of the insertion, adjacent regions that can be combined are combined). Which of these, is a good question, the only thing I would say is that I would favour filling from the top to the bottom.

Quote:

---

Originally Posted by Salem

If the next request is for 2x8, which case would you end up with?

---

One of the first two. It's not important that the free space remains contiguous, but the allocated region must be contiguous.

And if you want to know the application for this, it's packing subtextures into a full-size OpenGL texture. ;)

Just a small correction/note: if the memory must be able to be represented as a square and not just a rectangle, then you need an even power of two. For example, 8 is a power of 2, but you can't make a square out of it, not with integer side lengths.

Wikipedia has a list of space partitioning data structures for you to check out: List of data structures - Wikipedia, the free encyclopedia. I scanned over most of them very quickly, and while I didn't find your exact data structure, I did feel like a quad tree was perhaps most similar to what you are looking for. Note, I'm not a data structures expert, and I did not read all articles thoroughly, so I'm sure I missed plenty.

Yes, that clarifies the spec a bit. No fractional lengths. :)

Cross-referencing the Wikipedia list with "rectangles" on Google, I came across a Stack Overflow question that was dealing with a similar problem, one of the respondents identified it as a k-d tree.

Then someone else disagreed. Hnnngggh. :confused:

I think the sticking point is just how you choose to split the area of the node. The algo that I wrote yesterday just does it alternately (horz, then vert, then horz, etc.) with no logic applied, which isn't optimal. If you decide based on the shape of the first request, then the tree is biased towards similar shapes.

Quadtree is probably more sensible, as splitting squares into squares creates no bias. However, if your input is nothing but rectangles then you'll have quite a bit of empty space that can't be used. :eek:

Reread the quad tree article, the regions don't have to be squares, though they often are, for simplicity in examples or teaching. Using rectangles adds a bit of complexity, but a very small one, IMO.

K-d tree was my second choice and it may work well for what you want, but I'm less familiar with them so I think I was more hesitant to suggest them. Both offer easy ways to split regions into subspaces represented by child nodes in the tree, and easy way to "merge" neighboring small regions, by simply deleting the two subtrees representing that region.

Quote:

---

Reread the quad tree article, the regions don't have to be squares, though they often are, for simplicity in examples or teaching. Using rectangles adds a bit of complexity, but a very small one, IMO.

---

Regardless of the article....a quad tree when used in computer graphics or spatial partioniing is all about squares. A quad tree for spatial partioning will partition a region into 4 equal parts and each of those into 4 equal parts. The key is equal parts. An octree partitions a region into 8 equal parts. Quadtrees are often used in terrain based games and simulators like FSX. Octrees are often used in games for collision detection, lighting, etc. Sparse octrees can be used to represent an enormous amount of detail in voxel rendering. Quad trees are plane based and Octrees are usually volume based.

Quote:

---

Originally Posted by VirtualAce

Regardless of the article....a quad tree when used in computer graphics or spatial partioniing is all about squares. A quad tree for spatial partioning will partition a region into 4 equal parts and each of those into 4 equal parts. The key is equal parts. An octree partitions a region into 8 equal parts. Quadtrees are often used in terrain based games and simulators like FSX. Octrees are often used in games for collision detection, lighting, etc. Sparse octrees can be used to represent an enormous amount of detail in voxel rendering. Quad trees are plane based and Octrees are usually volume based.

---

A quad tree when used in computer graphics or spatial partitioning is all about...well, spatial partitioning. Quadtrees and octrees will partition a region into equal parts, except when you design them to partition a region into non-equal parts, which is perfectly valid, if atypical. Google "irregular quadtree decomposition", and you'll see plenty of applications of quadtrees that don't decompose into squares.