#### Archived

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

# KD-Tree Traversal

This topic is 5553 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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

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 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

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002131
×