What is the kd tree intersection logic?

Posted by bobobobo on Game Development See other posts from Game Development or by bobobobo
Published on 2012-06-06T20:04:05Z Indexed on 2012/06/06 22:48 UTC
Read the original article Hit count: 391

Filed under:
|

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)

image

The logical tree

divs

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?

© Game Development or respective owner

Related posts about space-partitioning

Related posts about kd-tree