Sign in to follow this  
Max_Payne

Octree traversal/Ray-AABB intersection/Octree neighbors

Recommended Posts

Eelco    301
Quote:
Original post by Max_Payne
Quote:
Original post by Eelco
one last remark: our whole debate is rather pointless considering the fact that recursion or neighbor based tree traversal makes a 20% speed difference either way at the very most, whereas you could improve your speed by a factor 5 or so by switching to kd-trees, which are maybe even simpler than octrees.


A factor of 5, but how? You have to traverse the tree either way... And the "slowdown" comes from the fact that you have to tell which node you're going in next. In a KD-tree, wouldn't you have just as many nodes, and hence, approximately as many node changes?

kd-trees are much more efficient because they can fit the data much tighter. this makes really massive differences in sparse scenes, but is always going to be a benefit.

besides, having only one split to make makes one recursion into the tree rediculously cheap, only a couple of cycles. more generally speaking, a tree is most efficient when it has as low a number of childs/node as possible, because then you tend most to the logarithmic character of trees, wheres if you increase the number of childs, you tend more to a grid.

i have to note however that cleverly constructing a kd-tree is harder than for example an octree, because with an octree you dont have to worry about where to place your splitting planes. however, even a relatively naive method will yield quite some improvement.

Share this post


Link to post
Share on other sites
GildeD    122
I'm going to have to agree with Eelco here, Max. kd-trees are faster from my personal experience. He's just trying to help you, but if you don't want to switch implementations and your oct-trees are working out for you, more power to you. Also if you want a brief explaination of kd-trees (not 200+ pages) check out flipcode (http://www.flipcode.com/articles/article_raytrace07.shtml). Their newest tutorial on ray tracing goes into them.

Hope this helps, =)

-=GildeD=-

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this