Archived

This topic is now archived and is closed to further replies.

LinaInverse2010

KD-Tree Traversal

Recommended Posts

Does anyone know how to traverse a node in a KDTree along a ray using only floating point adds and multiplies? I know it can be done using one subtract and a divide, but I read in a published paper that it can be done with three floating point additions and one multiplication, but I can''t seem to figure out how they did that. Is there anyway to not use the divide? The way I know solves this (Where s is the splitting plane location and aX+b is the 1-D line that goes through it) So I need to solve aX+b=s for X which is (s-b) / a LinaInverse

Share this post


Link to post
Share on other sites
Assuming your splitting planes are vertical and parallel to your axis (is that defined by the fact it''s a KD-tree?), which is what I assume you''re saying from you description, store the horizontal positions of the last plane intersected in both directions (and vertical too if you need to), then when you want to calculate an intersection point, find the distance between the two planes using a subtraction, multiply that by the direction vector of the ray, then add that to the last intersection position.

tj963

Share this post


Link to post
Share on other sites
KDTrees are BSP''s with axis aligned splits only.

If I understand what you are getting at, I don''t think that will work:

If the previous split was at 5 at time = 0 and the new one is at 9 and it''s direction value in that coordinate is .5:

Distance = 9 - 5 = 4
Distance * Direction = 4 * .5
Then your answer would be 2 + 0 = 2

That is wrong because: .5 * 2 = 1, and obviosly the intersection at 5 isn''t one unit away from 9. The step where you multiply by the direction would have to be a division.

LinaInverse

Share this post


Link to post
Share on other sites
Ok, I think I figured it out:

The ray I am using is not actually a true ray, it has a start and end time. So all we need to do is save the start and end values for each coordinate, then we know which side it start and ends on just by using a comparison.

LinaInverse

Share this post


Link to post
Share on other sites