Sign in to follow this  
ph33r

Adaptive Binary Trees(ABT)

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by dmatter
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


Yep, those links should give you enough info on ABTs, also, checking on amazon/google these books came out with ABT articles:

Game Programming Gems 5
(1.14 An Effective Cache-Oblivious Implementation of the ABT Tree)
Game Programming Gems 6
(5.5 Spatial Partitioning using an Adaptive Binary Tree)

Anybody got any of them that can tell us how good they are?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I hope that appears an article in gamedev.net. Until then, the following could help you:

The book "More OpenGL Game Programming" (http://glbook.gamedev.net/moglgp/) has an article on chapter 12: "Chapter 12 - Scene Management" wich includes information about the ABT.

I know that, because in the author's website (http://www.3dgloom.net/) says that. And, the best thing is: you can download the source code!




Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by Anonymous Poster
I hope that appears an article in gamedev.net. Until then, the following could help you:

The book "More OpenGL Game Programming" (http://glbook.gamedev.net/moglgp/) has an article on chapter 12: "Chapter 12 - Scene Management" wich includes information about the ABT.

I know that, because in the author's website (http://www.3dgloom.net/) says that. And, the best thing is: you can download the source code!


CO-AUTHOR's website... lol

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Err yes. But it's impossible to edit as "Anonymous Poster".
So thanks for nothing... lol

Share this post


Link to post
Share on other sites
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.

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