# newbie question about kd-tree and k-dop tree

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

## Recommended Posts

Hello: I'm new to kd-tree.Are k-d tree and k-dop tree the same things? I've read that k-dop tree is k/2 pairs of parallel planes and k-d tree is axis aligned bsp. But the axis aligned bsp is a special version of k/2 pairs of parallel planes, isnt it? I thought they are the same things before I got to learn each of them. So I need your help to clarify. Are they the same thing or not? ps: I'm planning to use k-dop tree to accelerate ray tracing.

##### Share on other sites
IIRC, a kd-tree is a special case of a kdop-tree, where the splitting planes are parallel to the worldspace coordinate axes. You will probably find a kd-tree much more convenient to work with in ray tracing than a general-case kdop-tree system, as the axis-aligned nature makes things like tree traversal, heuristic cost evaluation, etc. very simple to implement (vs. an arbitrary-alignment kdop).

##### Share on other sites
Quote:
 Original post by lythmI'm new to kd-tree.Are k-d tree and k-dop tree the same things?

Except that they are both spatial data structures, i wouldn't say the they are same because:

kd-tree is a spatial partitioning structure, it is a form of axis-aligned BSP tree, a binary tree.

k-DOP tree is a model partitioning structure, a bounding volume hierarchy (BVH) where the bounding volume type is a k-DOP (discrete oriented polytopes) in some sense you can think of them as a generalization of AABBs where a 6-DOP would be an AABB. BVHs can be binary or n-ary trees it depends on the context.

Quote:
 Original post by lythmSo I need your help to clarify. Are they the same thing or not?

I'd say no they are not.

##### Share on other sites
Thank you for your clarifying.

Another question: which is better to accelerate ray-tracing, kd-tree or k-dop tree? I found many ray-tracing article on the web use kd-tree, while article in computer graphics book use k-DOP tree.Which one will you guys pick to accelerate ray-tracing?

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

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633300
• Total Posts
3011266
• ### Who's Online (See full list)

There are no registered users currently online

×