|
Author Topic:   Implicit Binary Trees
LDA Seumas
unregistered
posted August 30, 1999 09:37 PM           
I was asked about this in e-mail, so here's some info about how implicit binary trees work. An implicit tree means that the structure of the tree is implied, and you can instantly jump to any node by using shifts and adds. An explicit tree has its structure explicitly defined through pointers, which means it's slower to use, but its structure is also dynamic at run time.

The size of a full binary tree should be ((1 << Levels) - 1) nodes, which means if you're storing an implicit tree of bytes, you need that many bytes for the array.

Each "level" of the tree is represented by a contiguous set of array elements starting at a specific index. That starting index is computed with levelindex = ((1 << level) - 1), where level is 0 for the root node. There will be (1 << level) nodes at that level, as array entries progressing from (and including) levelindex.

So to find any node given its level and its position in that level, you can use something like:

#define node(l, i) (((1 << (l)) - 1) + (i))

To go to a node's left child, increment l and double i. For the right child, add another 1 to i.

Now there's another way to access the tree, which is better if you're doing a lot of jumping around. If you index the tree from 1, rather than 0 (as arrays normally are), it's really easy to jump around the tree. Just use a global node index G as the 1-based index into the array for this node. To go to the left child, double G. For the right child, double and add 1. To go back to the parent, divide by 2 (which is right shifting by 1).

If you're using an implicit tree to store a hierarchical set of multi-resolution information, such as the variance levels of triangles in a binary triangle tree, it is very much like a a 1-dimensional mip-mapped texture, as you might use for 3D rendering.

If you draw the tree on a piece of paper, it becomes pretty clear. Draw one box, which is the root. Then to the right draw 2 more boxes, and to the right of those 4 more boxes, and then 8 more. Each set of boxes is a level in the tree.

------------------
-- Seumas McNally, Lead Programmer, Longbow Digital Arts

IP:

Vexxed
New Member
posted October 04, 1999 09:13 PM            
There are a few details that aren't plainly stated with your description but new folks might be interested in:

1. The allocation for the implicit tree is done as a single chunk of contiguous memory. The means making changes to the size of the array is extrememely costly.
2. All nodes for all branches to the complete depth of the tree must be allocated, even if there are "empty" spots in the tree. This means it is perfectly suited for a completely balanced tree like the one used for the variance tree in Tread Marks, but of limited use elsewhere.
3. The main benefits of this structure are rapid indexing and zero structure overhead. By comparison a linked binary tree has two pointers for every node. As such the variance tree in Tread Marks would have had 9 bytes per node instead of only 1 byte per node and a progression through the tree would require a pointer deference instead of a simple shift/addr. However, linked structures are still useful in situations where the tree is not balanced and/or where the size and shape of the tree changes often (like with the binary triangle tree itself).

Notes on binary trees:
Root node - The top of the tree
Branch node - A node with one or two children
Leaf Node - A node with no children. The end of the branch.
Depth - The number of nodes between the root and another node.
Balanced tree - Every branch node has two children. All leaves have the same depth.

The same information applies to other trees (quadtrees and octrees), there are just more possible children at each node.

Right after linked lists and arrays, trees are probably the most commonly used complex data structure in computer programming.

Tom Hubina

IP:

Chris C
Member
posted October 05, 1999 02:27 PM         
Hi,

I just thought I'd mention that the same data structure can be used to implement efficient priority queues. When these implicit trees have the property that each node's value is always greater than either of its children, then this structure is called a heap. The efficient priority queue implementation extends from this. I used this technique in my ROAM implementation, and it's quick and simple.

Just thought someone might be interested!

Chris

------------------
Chris Cookson
Computer Science Undergraduate, University of Warwick

IP:

Vexxed
New Member
posted October 07, 1999 10:47 PM            
Actually, that sounds rather interesting. Can you explain in more detail?

IP:

Oiler
Member
posted October 08, 1999 04:37 PM            
I too use a max heap in my implentation (templatized C++). If anyone is interested in it I could email it to them. What I want to get my hands on is a min-max heap becuase currently I have to walk the heap linearly to get the min value.

Oiler

IP:

MikeC
Member
posted October 10, 1999 04:55 PM            
The implicit Binary Tree sounds interesting, and quick. Is it as simple for a Quadtree? I have been looking at a document that someone (forgive me for not remembering) posted on using a quadtree for "Real-Time Generation of Continuous Levels of Detail for Height Fields". Whew.. what a mouth full. Anyway, in their implementation they use an indexing system into a matrix which represents the breakdown of the quadtree. Is this the same idea as implicit binary trees, only applied to a quadtree? It doesn't look the same, because in the binary tree, the levels of the tree are stored in order.

if you haven't read or seen the paper you probably have no idea what I am talking about, but I guess my main question is how would you create an implicit quadtree?

Mike

Man don't you hate when you have something in your head, and it won't come out of your mouth?

IP:

Chris C
Member
posted October 12, 1999 09:46 AM         
Hi!

Vexxed - I'll post up the details about the heap implementation soon, if you are still interested.

MikeC - I implemented the 'Real-Time Generation of Continuous Levels of Detail for Height Fields' algorithm and as far as I can recall, the matrix was simply a big array, with no clever indexing tricks. It's definitely a sort of implicit quadtree, but not really as neat as an implicit binary tree. In other words, to access the next quadtree levels you split the current quadtree level into 4 to generate the indexes, so in a way, the quadtree is kind of implicit - there's no list of quadtree levels/nodes, just one big matrix. The real bonus of implicit binary trees is the fact that with simple bit shifts/adds you can access the children/parents of a given node with ease - something that's a little harder with the quadtree matrix.

Hmm. I hope something there made sense!

Chris

IP:

Vexxed
New Member
posted October 12, 1999 04:29 PM            
Any size tree can be stored implicitly by changing the indexing and size parameters. Off the top of my head, I'd say to go from the binary tree Seumas mentioned to a quadtree you would change his shifts by 1 into shifts by 2 (mult/div by 4 instead of 2) and the child access would be index, index +1, index + 2, index +3.

Pretty straightforward actually and it should be obvious now how to turn this into an octree or any other size tree. Powers of two work best because you can use shifts instead of mult/divides, but I think it should work fine with non-power of two tree complexity as well.

Tom

IP:

MikeC
Member
posted October 13, 1999 12:01 AM            
Chris C,

Yeah, that is how I have it working now, but I thought there may be some tricky little algorithm that I was missing. Did you do the error calculation exactly like it is in the paper? I am having some issues with the D2 error... it always seems to be 0. I think I must not be doing it right.

When I first did the quadtree terrain, I started with the whole "Ok... here is my node, and here are the children.. blah blah blah", then I erad that paper and when I saw the drawing matrix I was like DUH! I totally got rid of the pointers. After I get all of the error calculations figured out, I will probably post this code as a small GLUT app if anyone is interested.


Vexxed,

Thanks for responding. I kind of figured it would be something like that for an array, but I was thinking more along the lines of a matrix. Basically, in that paper I was mentioning there is a point where you need to compare the parent of one quadrant with the child of another, and I wanted a quick way to get there. I can just do it with a few steps instead of one though.

Thanks,

Mike

IP:

Chris C
Member
posted October 14, 1999 05:56 AM         
Hmmm, I certainly agree that you could store the quadtree implicitly, but if I remember, I used extra space in the quadtree matrix to store extra information ie. if you notice, not all the entries in the quadtree matrix are actually used by the algorithm, so to be more space efficient I used these entries to store extra data - can't remember what though . Anyway, the point is, those extra spaces I used would not fit too nicely into the implicit quadtree parent-child style structure, so for me, I would still choose with the array.

I certainly know what you mean about problems with the calculations - It took me a while to work them out - the explanation in the paper isn't exactly crystal clear, I'll have to dig out my source and see what I made of them, I do have a nasty feeling there may have been some omission/error somewhere in the paper. My final program worked fine (just like the screenshots in the paper!), so I must have done something right. Didn't quite get those damn geomorphs working though, maybe some other time


IP:

bdiscoe
Member
posted November 12, 1999 07:39 AM            
I just wanted to tell everyone that i keep a page of notes on this subject (regular-grid terrain LOD algorithms)... you might like to visit:
http://vterrain.org/LOD/runtime-reg.html

-Ben

[This message has been edited by bdiscoe (edited January 02, 2000).]

IP:

Dudymas
Member
posted August 06, 2000 07:38 PM            
could i actually return this from the dead?

IP:

Random Chaos LDA
Member
posted November 28, 2000 01:47 PM            
Is it possible to make posts that are gone re-appear?

IP: