Sign in to follow this  

newbie question about kd-tree and k-dop tree

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

If you intended to correct an error in the post then please contact us.

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


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by lythm
I'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 lythm
So I need your help to clarify. Are they the same thing or not?


I'd say no they are not.

Share this post


Link to post
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?

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this