🔒 Locked

Adaptive Binary Trees(ABT)

Started by ph33r Apr 3, 2006 at 11:11 AM 11 replies 13.8k views

Original Post

Apr 3, 2006 at 11:11 AM

I read a thread by Yann L, where he discusses how he uses ABT's in his engine for frustrum culling. I did a search on google for ABT and came up with nothing. I checked the ACM and found papers but I don't think they are related to his algorithm he mentioned. From his description in this thread clicky it makes it seem that its very similiar to a KD-tree or a BVH tree using AABB. If anyone can give me further information on ABT, i.e. a reference from ACM or other white papers, I'd appreciate it. Also, going out on a limb, but is an ABT a kd-tree?

NLDEV

Apr 3, 2006 at 2:25 PM

Quote:
Original post by ph33r
I read a thread by Yann L, where he discusses how he uses ABT's in his engine for frustrum culling. I did a search on google for ABT and came up with nothing. I checked the ACM and found papers but I don't think they are related to his algorithm he mentioned.

From his description in this thread clicky it makes it seem that its very similiar to a KD-tree or a BVH tree using AABB.

If anyone can give me further information on ABT, i.e. a reference from ACM or other white papers, I'd appreciate it.

Also, going out on a limb, but is an ABT a kd-tree?

I don't have much information for you, myself, on ABTs. However, perhaps you should check out this thread where Yann discusses the construction (and implicitly, structure) of an ABT, if you haven't bumped into it already.

ph33r

Apr 4, 2006 at 2:28 AM

I actually have run into it. I can potentially implement my own system fairly well based on his posts on ABT's. Unfortunately, I'd like to do more research and comparisons on ABTs with other geometric data structures.

I was wondering if the ABT was a concept that Yann L created himself. I have pinged other engine developers and while they are familiar with its properties they have not heard of the name.

noNchaoTic

Apr 4, 2006 at 6:31 AM

Do you mean Red/Black Trees?

b2b3

Apr 4, 2006 at 6:32 AM

As far as I know Yann L created this system. I don't think there are any whitepapers about this (IIRC he started writing something but it was never finished).

ph33r

Apr 4, 2006 at 10:38 AM

Quote:
Original post by b2b3
As far as I know Yann L created this system. I don't think there are any whitepapers about this (IIRC he started writing something but it was never finished).

Ahh, that's a shame. All that knowledge is locked up in his head!

dmatter

Apr 4, 2006 at 11:28 AM

Quote:
Original post by ph33r
Quote:
Original post by b2b3
As far as I know Yann L created this system. I don't think there are any whitepapers about this (IIRC he started writing something but it was never finished).

Ahh, that's a shame. All that knowledge is locked up in his head!

Well thats not really the case, there is more than enough infos here at GameDev to implement your own ABT, check out these links (in no particular order):

Combining Octrees and BSP trees... is it possible?
ABT questions: construction and use
ABTs, relaxing them and other questions [<-- yay me [smile]]
ABT and polygon soup
ABTrees Questions
ABTs and the possibility of multiple division planes
ABT vs Octrees

Special kind of ABT called a LABT: LABT (liquid adaptive binary tree) explanation?

Hope that this list provides some help, there are other posts on these forums that mention ABTs too, all you have to do is search.

Happy Coding

Dybbuk

Apr 13, 2006 at 8:40 AM

Mirko Teran aka DarkWIng used ABT's in his demo for the NeHe create contest. In his entry he also included his source code.

So if you need an example: check out the nehe contest page, or go directly to his home page: http://fly.to/teran

Promit

Apr 28, 2006 at 4:28 PM

Quote:
Original post by ph33r
From his description in this thread clicky it makes it seem that its very similiar to a KD-tree or a BVH tree using AABB.

Fundamentally the ABT is an AABB tree. It just works with poly soup and adapts a little differently than a normal AABB tree, which usually works with objects at a time.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.