Sign in to follow this  
lythm

newbie question about kd-tree and k-dop tree

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

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