Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
3  
+1 nice drawing. –  Byte56 Jun 6 '12 at 21:02

1 Answer 1

up vote 10 down vote accepted

It's pretty simple really; the test against splitting plane (2.1) should fail, because of the following:

When the ray hits splitting plane (1), you "split the ray", or; you set the t-range for which it is valid, and continue down the tree with the resulting parts.

Thus, when checking against plane (2.1), you should be checking if only the part of the ray left of plane (1) intersects with plane (2.1), which it doesn't. The "far off to the right" intersection you speak of has a t > the t value where you split the ray with plane (1).

I hope that's clear enough.

Summary: Subsequent ray/plane intersections should be done only with the part of the ray remaining after splitting it with the plane in question.

share|improve this answer
1  
Grr!! (short for great answer) –  bobobobo Jun 6 '12 at 20:53
    
Nice answer Torious! Welcome to GDSE. –  Byte56 Jun 6 '12 at 21:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.