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

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

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