Jump to content

  • Log In with Google      Sign In   
  • Create Account


Octree traversal/Ray-AABB intersection/Octree neighbors


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
26 replies to this topic

#21 Max_Payne   Banned   -  Reputation: 757

Like
0Likes
Like

Posted 01 December 2004 - 07:50 AM

You're not trying to help me. If you were, you would be kind enough as to give me a reason why I should look into other possibilities. I also have "something called real life". I don't want to look into all possibilities, especially when I don't see a single reason to do so.

I created this thread to discuss octrees, and I'm looking for help with octrees. If you want to help, why don't you look at my pseudocode and suggest improvements, that would be helpful. I'm open to suggestions.




Looking for a serious game project?
www.xgameproject.com

Sponsor:

#22 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 01 December 2004 - 09:12 AM

Quote:
Original post by Max_Payne
You're not trying to help me. If you were, you would be kind enough as to give me a reason why I should look into other possibilities. I also have "something called real life". I don't want to look into all possibilities, especially when I don't see a single reason to do so.

maybe im not trying hard enough to help you in your opinion, but i can assure you it isnt going to get any better from me. maybe other people can help you better, but ive given all im going to. im sorry if i failed to convey my reasons why i think recursion isnt so bad, but i dont feel like trying a sixth time. either i just suck too much at explaining or youre just not even reading what i post. either way, i dont see the point in continueing trying to convince you.

Quote:

I created this thread to discuss octrees, and I'm looking for help with octrees. If you want to help, why don't you look at my pseudocode and suggest improvements, that would be helpful. I'm open to suggestions.

i dont really feel like doing so. i hate reading other peoples code. try someone else.

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.

but im not going to prove it for you so you wont believe me, and since youre not going to try and find out for yourself, i dont even know why i posted that.

good luck.

#23 grhodes_at_work   Moderators   -  Reputation: 1361

Like
0Likes
Like

Posted 01 December 2004 - 09:31 AM

Eelco, Max_Payne,

Please try to keep this discussion civil. I realize you have a difference of opinion, but this is not the place for a fight.
Graham Rhodes Moderator, Math & Physics forum @ gamedev.net

#24 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 01 December 2004 - 10:12 AM

Quote:
Original post by grhodes_at_work
Eelco, Max_Payne,

Please try to keep this discussion civil. I realize you have a difference of opinion, but this is not the place for a fight.

yeah i suppose i could cut back on the sarcasm.

#25 Max_Payne   Banned   -  Reputation: 757

Like
0Likes
Like

Posted 01 December 2004 - 10:53 AM

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?


Looking for a serious game project?
www.xgameproject.com

#26 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 01 December 2004 - 08:51 PM

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.

#27 GildeD   Members   -  Reputation: 122

Like
0Likes
Like

Posted 01 December 2004 - 10:08 PM

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=-




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS