ABT vs Octrees

generally the ABT has lesser deep than octree, so the time of traversing the tree is minor.

Bye Davide

hummm .... that makes sense. Also can anyone send me some links where I can find more information on ABTs. I tried googling but in vain :(
Regards

Btw, wtf is the difference between Adaptive Binary Trees and kd-trees?

Quote:

Original post by howbizarre79 Also can anyone send me some links where I can find more information on ABTs.

Yann L's Greatest Hits. Look for AB Trees section.

Quote:

Original post by howbizarre79 Btw, wtf is the difference between Adaptive Binary Trees and kd-trees?

This thread should give some anwsers.

If you still have any specific questions feel free to ask.

Well _DarkWIng_ I have gone through that thread before but unfortunately due to lack of my knowledge with regards to Culling Related Stuff...... most of the things were far above my comprehension :( .... That is why I am looking for some paper which can give me all the details needed by a beginer to start working on ABTs. Sorry if my ignorance is annoying ....

Regards,
Hussain

As far as I know there is no paper on ABTs so far. I only know Sages is writing one now. The only "literature" about are the 4 links on the page I posted. There were some later discussions but you'll have to search for them a bit. I sugest you re-read them a few times. If they still look to heavy try implementing octree first. Once you have that build and truly understand how it works try to move to loose-octrees and then to ABTs.

As I understand it, the ABT is essentially a hybrid between a kD-tree (which is a pure spatial partitioning), and an AABB tree (which is a pure geometric partitioning). It stills retains many of the basic traits of a kD-tree but is more intelligent about the geometry it contains; at the same time, it isn't as formless as an AABB tree. It's generally a very well balanced tree that's easy to traverse and render.

I imagine Yann will jump in here sooner or later as well, hopefulyl he can clear things up.

its basicly nothing but an AABB tree with some oddities to make it better suited to frustrum culling in a rasterizer, which demands uniqueness of leafdata.

literature on kdtrees is plentyfull i believe.

*jumps in*

Well, there is no clear separation between ABTs and kd-trees, they have many similarities, but also many differences (non-median splitting, partial overlapping, uniqueness of leaf data, etc). But this has been discussed in that other thread, so let's just say that ABTs are a mutation of a kdtree.

About ABT versus octree, this is very difficult to say. Both are different structures, and both have their advantages and drawbacks, depending on how they are used. ABTs offer the advantage of being "polymorph", in the sense that are an abstraction of both geometry and space partitioning without being limited to a fixed shape. Their main use is for hardware friendly frustum and visibility culling of complex 3D environments. Octrees are notoriously inefficient for this task, because of their rigid spatial structure. This can be somewhat alleviated by using loose octrees, but they still have a lot of constraints. Especially the uniqueness of mesh data (which is extremely important on modern 3D hardware) is not given with octrees: you basically have to split everything that struggles a boundary, or you use tags - which rules out efficient hardware rendering. Also, octrees won't adapt to geometry as smoothly as ABTs. Basically, for general purpose rendering of medium or complex scenes, ABTs are much more efficient than octrees.

Things change when you do raytracing (what I think Eelco was doing in that other thread). Tracing a ray through an ABT is pretty expensive, due to the relatively large number of box-to-ray checks. Also, the overlapping that made rendering more efficient is actually counterproductive when tracing a ray through the structure. Ray tracing requires extreme space localization, with absolutely zero overlap between the cells. Uniqueness can be an adavantage, but is not required. Also, the "procedural" fixed grid structure of octrees - the one that was the big drawback for rendering - is actually a huge advantage when tracing a ray through the tree: very efficient parametric tracing algorithms exist for octrees, that are much faster than a comparable ABT tracer (for example this paper). So if you raytrace through geometry, for example when doing lighting computations or radiosity, then use octrees (but keep in mind, that a good octree can take a lot of memory).

Edit: I just realized that howbizarre79 also mentioned the evil word™ - BSP. Never use them for rendering, they are no viable option. That's pretty much all there is to say about them.

Wow ....
That was exactly the kind of description I had been looking for :D.... Thanks Yann and every one else. Guess am gonna start with implementing Octrees, then their Loose Form and afterwards will switch to ABT; as DarkWing suggested :D. Will bug u guys again if get stuck somewhere..... :D
Regards,
Hussain.

Hey Guess what !!!!! I am stuck :(
I started looking into the Octree and got it for the most part of it ( Thanks to the Article at GamaSutra). But the article says: ( as it should be)

" If a surface straddles more than one cubelet, split the surface into subsurfaces"

Actually I want to know that as to how am I suppose to go about doing that. If some one can give me a snippet of code showing how that is accomplished, it would be a great help.

Regards,
Hussain