# OCTree Traversal

This topic is 5182 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i want to aviod the recursive traversal in my octree,does anyone know a link of an article explaining another way of traversal but not recursive or do you have any tips or ideas to follow. thanks a lot.

##### Share on other sites
This depends on what you are trying to accomplish by a traversal. I am not sure of myself but as far as I know , there is no way to render the octree's geometry without recursive traversal. However, you could use neighbour-matrices for ray-tracing and collision detection.

##### Share on other sites
Quote:
 Original post by AghisHowever, you could use neighbour-matrices for ray-tracing and collision detection.

Can you explain that a little more?? I'm interrested to know what is neighbour-matrices??? Thanks
Thanks

##### Share on other sites
You can traverse with a priority queue instead of a recursive call. For breadth-first, pop nodes from the front and push on the back; for depth-first, both push and pop from the back.

// traverse an octree using no recursionqueue.push( topnode );while( queue.size() > 0 ) {  node = queue.pop();  foreach( subnode in node.children ) {    if( want_traverse( subnode ) ) {      queue.push( subnode );    }  }}

##### Share on other sites
A long time ago i was working on something i called a flat octree, you could easily call up any branch of the tree without traversing through it. It was only good for small depth levels, but was a neat idea at the time.

##### Share on other sites
Quote:
 Original post by AghisThis depends on what you are trying to accomplish by a traversal. I am not sure of myself but as far as I know , there is no way to render the octree's geometry without recursive traversal. However, you could use neighbour-matrices for ray-tracing and collision detection.

There is always a way to avoid recursion, although in some cases recursion can make the code easier to read.

##### Share on other sites
Quote:
 Original post by DaivukCan you explain that a little more?? I'm interrested to know what is neighbour-matrices??? ThanksThanks

Neighbour-matrices are used to store references to neighbouring nodes. Each node has one and is through it enabled to access all of the nodes that it is "in contact" (i.e. shares borders) with.

This proves useful in ray tracing functions where one tests whether a ray from point A to point B intersects any polygons. A quicker way than using recursion is finding the node in which one of the points (say A) lies and "following" the ray as it moves from node to node which is possible because of the neighbour matrix.

I hope I was clear enough.

##### Share on other sites
Quote:
 Original post by hplus0603You can traverse with a priority queue instead of a recursive call. For breadth-first, pop nodes from the front and push on the back; for depth-first, both push and pop from the back.// traverse an octree using no recursionqueue.push( topnode );while( queue.size() > 0 ) { node = queue.pop(); foreach( subnode in node.children ) { if( want_traverse( subnode ) ) { queue.push( subnode ); } }}

This is very interesting but -when traversing to render- wouldn't it invalidate culling branches of the tree which lie outside the frustum?

##### Share on other sites
Quote:
 Original post by head_hunterI hope I was clear enough.

yes thanks :)

##### Share on other sites
well i want to avoid the push and pop that the stack of compiler does,when most of the tree is visible rendering the scene using the octree is slower than rendering
it normally,do you think that array-like implementaion is faster that others
so if we do the following:
- use a priority queue to breadth traversal
- use an array-like implemetation of the tree

do you add any tips ?...

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 9
• 24
• 52