Jump to content
  • Advertisement
Sign in to follow this  
genesys

KD-Tree traversal (traytracing) am I missing a case?

This topic is 3176 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

Hi! i try to traverse a 3D KD-Tree in my raytracer. The Tree is correct, but there seems to be something wrong with my traversal algorithm since i'm getting some errors compared to using bruteforce (some small surface areas seem to get ignored). Note: non of the rays in question is parallel to one of the axes! This is my traversal algorithm: IntersectionData* intersectKDTree(const Ray &ray, KDTreeNode* node, double tMin, double tMax) const{ if (node->GetObjectCount()==0) return 0; IntersectionData* current = 0; bool intersected = false; if (node->m_isLeaf){ ...test all primitives in the leaf... } else{ int axis = node->m_splitAxis; double splitPos = node->m_splitPos; double tSplit = (node->m_splitPos-ray.point[axis])/ray.direction[axis]; KDTreeNode* nearNode = ray.point[axis]<splitPos?node->m_leftnode:node->m_rightnode; KDTreeNode* farNode = ray.point[axis]<splitPos?node->m_rightnode:node->m_leftnode; if (tSplit > tMax) return intersectKDTree(ray, nearNode , tMin, tMax);//case A else if (tSplit < tMin){ if(tSplit>0) return intersectKDTree(ray, farNode, tMin, tMax);//case B else if(tSplit<0) return intersectKDTree(ray, nearNode, tMin,tMax);//case C else{//tSplit==0 if(ray.direction[axis]<0) return intersectKDTree(ray, farNode, tMin, tMax);//case D else return intersectKDTree(ray, nearNode, tMin, tMax);//case E } } else{ if(tSplit>0){//case F current = intersectKDTree(ray, nearNode, tMin, tSplit); if (current != 0) return current; else return intersectKDTree(ray, farNode, tSplit, tMax); } else{ return intersectKDTree(ray,nearNode,tSplit, tMax);//case G } } } } And here I created a graphic visualizing all the different cases: http://neo.cycovery.com/KDTree_traversal.jpg Did I miss a case? Thank you!

Share this post


Link to post
Share on other sites
Advertisement
Are you trying to figure out how to traverse a kD-tree yourself? You may want to check out Wald's work, or Vlastimil Havran's thesis. They both provide tiny algorithms for kD-tree traversal. Yours is too complex.

On a sidenote: Implement your own stack, and store direction reciprocals with your rays. It will greatly boost the speed of your code.

Share this post


Link to post
Share on other sites
Hey and Thanks for your reply!

I already heard about using a stack in KD tree traversal instead of recursion. But why should this be any faster? since a normal KD-Tree usually has a depth of only 10-40 so the size of the callstack shouldn't be a problem..

Share this post


Link to post
Share on other sites
Hm, I'm not a C++ expert, so someone will probably correct me, but here we go:

If you have only a small recursive function, then you are doing tons of function calls compared to the actual work load. A function call is not 'free': a stack frame is produced, parameters are put on the stack and retrieved inside the function again, and of course there is the jump and return. By creating your own stack, you guarantee that the code doesn't do anything beyond what you intended: you put only the code on the stack that you need, and some variables simply change iteratively (most notably, the current node pointer, in this case).

And finally, a recursive function can't be inlined. Depends on the circumstances how bad this is, of course.

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!