Jump to content
  • Advertisement
Sign in to follow this  
eGamer

OCTree Traversal

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
Share on other sites
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

Share this post


Link to post
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 recursion
queue.push( topnode );
while( queue.size() > 0 ) {
node = queue.pop();
foreach( subnode in node.children ) {
if( want_traverse( subnode ) ) {
queue.push( subnode );
}
}
}

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 recursion
queue.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 this post


Link to post
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 ?...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!