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

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

## 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 on other sites
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 on other sites

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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 10
• 9
• 35
• 16
• ### Forum Statistics

• Total Topics
634125
• Total Posts
3015674
×