What is the kd tree intersection logic?
- by bobobobo
I'm trying to figure out how to implement a KD tree.
On page 322 of "Real time collision detection" by Ericson
The text section is included below in case Google book preview doesn't let you see it the time you click the link
text section
Relevant section:
The basic idea behind intersecting a ray or directed line segment with a k-d tree is straightforward. The line is intersected against the node's splitting plane, and the t value of intersection is computed. If t is within the interval of the line, 0 <= t <= tmax, the line straddles the plane and both children of the tree are recursively descended. If not, only the side containing the segment origin is recursively visited.
So here's what I have: (open image in new tab if you can't see the lettering)
The logical tree
Here the orange ray is going thru the 3d scene. The x's represent intersection with a plane. From the LEFT, the ray hits:
The front face of the scene's enclosing cube,
The (1) splitting plane
The (2.2) splitting plane
The right side of the scene's enclosing cube
But here's what would happen, naively following Ericson's basic description above:
Test against splitting plane (1). Ray hits splitting plane (1), so left and right children of splitting plane (1) are included in next test.
Test against splitting plane (2.1). Ray actually hits that plane, (way off to the right) so both children are included in next level of tests. (This is counter-intuitive - shouldn't only the bottom node be included in subsequent tests)
Can some one describe what happens when the orange ray goes through the scene correctly?
