Sign in to follow this  
canuckle

ABTs... really AABB tress or k-d trees? again

Recommended Posts

Although this topic has been beaten to death, it is still not clear to me whether Adaptive Binary Trees (ABTs) are k-d trees or AABB tress. From my (limited) knowledge attained from these forums, I'd say ABTs are really AABB trees constructed with an algorithm similar to k-d construction algorithms. However, some people (including Yann) seem to disagree, which makes me wonder if I'm misunderstanding the original idea. I would like a clarification purely for better understanding this structure (and not to prove anyone wrong). As I understand (and as it was previously mentioned on another post): - each k-d tree node stores a dividing plane - each AABB tree node stores an AABB box - each ABT tree node stores an AABB box With this in mind, with dynamic elements the ABT tree is ALWAYS an AABB tree even if it majorly diverges from the (k-d tree-like) way it was initially constructed. To illustrate what I mean, here is an example construction of an ABT tree. Here are the original objects: During the first step, construct tree in a k-d like way by recursively finding splitting planes (for the sake of simplicity, I am not allowing for overlaps): During the second step, create AABB's for each node: At this point, the ABT definitely looks like an AABB tree. Now consider the case where the green object moves (with simple adjustments between the leaf and root without rebuilding the tree): As is shown, the tree remains AABB but does not retain much of its original k-d tree properties. Please let me know if I am misunderstanding something or if my reasoning makes sense. PS: Please keep this thread free of condescending, pretentious, or flaming comments.

Share this post


Link to post
Share on other sites
Quote:
Original post by canuckle
Although this topic has been beaten to death, it is still not clear to me whether Adaptive Binary Trees (ABTs) are k-d trees or AABB tress.
A tree that predominantly stores AABBs in the nodes (and leaves) is an AABB tree. Such a tree can be created top-down, bottom-up, or in any number of other ways. Regardless of how it's constructed, it remains an AABB tree.


Quote:
From my (limited) knowledge attained from these forums, I'd say ABTs are really AABB trees constructed with an algorithm similar to k-d construction algorithms.
Yes. (IMO, they are AABB trees plain and simple and should be referred to as such.)

Note also that a k-d tree has the distinction that it is a spatial partitioning method. That is, the volumes of space carved out by the k-d tree do not overlap. In stark contrast is a bounding volume hierarchy such as an AABB tree, where the volumes of the tree is allowed to overlap. That's because a bounding volume hierarchy is not a spatial partitioning but an object partitioning method.

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