Fast, stackless kd-tree traversal in raytracing, clarification needed

3
votes

I am trying to implement a real time ray tracer, and I was reading this interesting paper on a fast, stackless kd-tree traversal method, but it is unclear regarding certain concepts. At page 4, where it presents the rope construction algorithm, it doesn't explain what the 'split-plane' and 'split-axis' are exactly, and how the 'split-axis' could be parallel to the left side but not the right side.

Would anyone with more experience in writing ray tracers and/or who understood the two concepts found in the paper please explain them to me?

Thanks in advance.

Paper [PDF]: http://www.johannes-guenther.net/StacklessGPURT/StacklessGPURT.pdf

1
raytracingkdtree
In a 3 dimensional kD tree, the split-axis is X, Y, or Z. The split-plane is the actual plane used to split the children. It is always perpendicular to an axis, with some given displacement from the origin. – Tavian Barnes

1 Answers

1
votes

I don't think the authors meant to imply that the split-axis is parallel to only the right or left side. They are optimizing the ropes for each side. In order to do this, they need to know if the split plane is parallel to that side. So they test split-axis(R) || S. Here, R is the ropes of the current node. R_L and R_R are the ropes for the left and right sub-trees of that node. The test is trying to see if the current node is splitting on the side for which the ropes are being optimized.

For example: if we're trying to optimize the left and right ropes, we first check whether the current node has a split plane that splits the world into a left and right side (in other words, the split plane is parallel to the YZ plane). If it isn't, then we give up on optimizing the left and right ropes.