🔒 Locked

KD-Tree Traversal

Started by LinaInverse2010 May 6, 2003 at 7:03 PM 2 replies 450+ views

Original Post

LinaInverse2010

May 6, 2003 at 7:03 PM

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

tj963

May 6, 2003 at 7:13 PM

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

LinaInverse2010

May 6, 2003 at 7:34 PM

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

LinaInverse2010

May 7, 2003 at 10:53 AM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.