OCTree Traversal

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.

Quote:

Original post by Aghis However, 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

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 );    }  }}

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.

Quote:

Original post by Aghis 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.

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

Quote:

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

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.

Quote:

Original post by hplus0603 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 ); } }}

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

Quote:

Original post by head_hunter I hope I was clear enough.

yes thanks :)

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 ?...