ABTSceneManager

What it says on the tin: a place to discuss proposed new features.
Post Reply
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

ABTSceneManager

Post by Rasengan »

Hey,

I would like to implement the ABT partitioning system within Ogre (from Campbell03 or Lombard02-03, Teran-Ravniker04 papers).
Do you think it would be a usefull SceneManager for Ogre or it's useless at all?
I mean, do you think that it give us a real performance benefit compared to the actual OctreeSceneManager?
Shadow007
Gremlin
Posts: 185
Joined: Sat May 07, 2005 3:27 pm

Re: ABTSceneManager

Post by Shadow007 »

Would you by chance have a link to the papers you're talking about ?
I don't find them ...
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

Re: ABTSceneManager

Post by Rasengan »

well, I'm reading the section 5 from GameProgramming Gems 6, ABT.
There are 4 links at the end, they point to some forums at gamedev.net.

[Campbell03] http://www.gamedev.net/community/forums ... _id=163240
[Lombard02] http://www.gamedev.net/community/forums ... =1&#675554
[Lombard03] http://www.gamedev.net/community/forums ... =1&#961492

[Teran-Ravniker04] "Tranquility Demo" http://fly.to/teran ->seems to be dead, but we can found this little demo here: http://nehe.gamedev.net/data/contests/c ... contest=08
You can change the resolution for the demo, in Config/Settings.txt, the default res is too low ;)

So, not really papers at all.
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

Re: ABTSceneManager

Post by Rasengan »

No advice?

Well, I'll implement a "first" ABT scene manager, wich "take care" of static geometry.
If I get good results, I'll try to implement one wich "take care" of dynamics objects. :twisted:

Let's start with this! ... we'll see results soon. :)
Shadow007
Gremlin
Posts: 185
Joined: Sat May 07, 2005 3:27 pm

Re: ABTSceneManager

Post by Shadow007 »

Well I had a look yesterday, and It seems awfuly close to what in Ray Tracing they call a "Bounding Volume Hierarchy" (but for precision should be named "Axis Aligned Bounding Box Hierarchy").

(cf http://www.sci.utah.edu/~wald/Publicati ... togbvh.pdf)

They work quite well for ray-tracing (with beeing much more lenient than Kd-trees regarding "approximate" construction) but it has some problems with scenes with big oblique primitives.

You may want to have a look at the Bounding Interval Hierarchy too (which is an hybrid between a kd-tree and a BVH).

Since last year, a variant of the BVH seems promising (for incoherent rays mostly though) : the "QBVH" where each node has up to 4 leaves instead of 2)

All in all these are structures that work well fo ray-tracing, but I don't know how adapted it is for Rasterization. It may pose problems regarding batching for example). You may also want to check if some variation of the SAH is not better than the ones suggested in your references.

Anyway, a great ressource (although completely Ray-Tracing focused) is the ompf.org/ forum, where these structures were discussed quite a lot.

You may also want to check Kesen-Huangs papers indexes @http://kesen.huang.googlepages.com/
for the "IEEE/EG Symposium on Interactive Ray Tracing" indexes, as well as this year's "High Performance Graphics"... some of the papers are closely related to BVHs.
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

Re: ABTSceneManager

Post by Rasengan »

Thanks for the links, we can find huge informations and papers there! Amazing :wink:

After investigating a little bit the BVHs, it seems that the structure is, as you says, more adapted for "fast" ray tracing rendering.
I've started to implement an ABT manager into Ogre, I think that this manager can be used by more users than the BVH one...
Depending on the scene, we can expect good results.
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Re: ABTSceneManager

Post by jacmoe »

Is this outdoor or indoor scenes?
It it's indoor, I predict a big userbase.. :)

If you are willing to share it, that is.. :wink:
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

Re: ABTSceneManager

Post by Rasengan »

It's better suited for outdoor scenes. :)
Of course, I'll share it with the community.
Shadow007
Gremlin
Posts: 185
Joined: Sat May 07, 2005 3:27 pm

Re: ABTSceneManager

Post by Shadow007 »

I didn't perceive the difference between the ABT and a BVH... Since you have found one, can you please explain ?

Thank you.
User avatar
Rasengan
Halfling
Posts: 46
Joined: Sun Jul 13, 2008 12:21 pm
Location: Brussels

Re: ABTSceneManager

Post by Rasengan »

Well, you're right, both are very similars. I want just "quote" a note about that, written in the book More OpenGL Game Programming, edited by Dave Astle.

"Aren't ABTs Just AABB Trees?

... Both ABTs and AABBs are 3-dimensional data structures, but AABBs are object-centric data structures (or BVHs), and they do not contain information on how to partition space. ABTs are spatial data structures, and they do partition space since that is their purpose.
..."


I agree with that, but I want to say that I did'nt know the term "BVH" before you spoke to me.. :) and the current BVHs implementations seems to do the same purposes than ABTs, though. I want just test this scene manager in the hope that it's going to speed up the rendering of my scene, and theoretically, I would say "yes"!
Also, I want to contribute to the Ogre community, making some usefull work for all of us, I'm not a 3D guru nor a very good mathematician, but I start with this...I don't know if this will be usefull for people, but I hope :wink:
Sairon
Halfling
Posts: 94
Joined: Fri Apr 20, 2007 5:50 pm

Re: ABTSceneManager

Post by Sairon »

I use a solution which lies fairly close to the described technique, I call it dynamic icoseptree manager ( roughly based on http://www.cs.nmsu.edu/CSWS/techRpt/2003-006.pdf ). It probably doesn't play nice with all parts of Ogre ( in some regards, to benefit I'd say ), but works really great for us atm. It still has a few bugs which I haven't spent time ironing out yet, but it performs really really well under most conditions and handles arbitrarily large scenes terrific as long as memory permits.

EDIT: Will release it once I can dedicate some time to document it, profile, and implement a few more features, one thing which I think will be fairly easily added, which is one of the largest benefits of this manager, is spreading tree balancing over several frames.
User avatar
xadhoom
Minaton
Posts: 973
Joined: Fri Dec 28, 2007 4:35 pm
Location: Germany
x 1

Re: ABTSceneManager

Post by xadhoom »

Interesting approach! I´m glad you are going to release the code. Did you create a custom scene manager to implement the icoseptree?
I´m also curious if this approach would be a (plug-in) candidate for Ogres paging functionality...
Sairon
Halfling
Posts: 94
Joined: Fri Apr 20, 2007 5:50 pm

Re: ABTSceneManager

Post by Sairon »

Yeah. Noting special needed, uses Ogre plugin system.
Shadow007
Gremlin
Posts: 185
Joined: Sat May 07, 2005 3:27 pm

Re: ABTSceneManager

Post by Shadow007 »

<Pedantic>
In fact, both the approaches here are not "Spatial Partitionning Structures" (as are the Kd-Tree, Octree, QuadTree), but "Objects Partitionning Structures"...
If I understand correctly the distinct references in this thread, when splitting a node, no primitives are "shared" (ie duplicated into) the children, the children may overlap in space and in some case don't cover the upper level volume in it's entirety... So the Objects are what count, and not the volume.
Wether the splitting was computed based on spatial criteria or not is of no import ...
</Pedantic>
With that said, I again don't see a difference between ABT and what the Ray-Tracing (RT) crowd call a "BVH"...

I'll talk about what I know about them regarding Ray-Tracing, and will try and find out how it relates to Rasterization.
Pros :
"Not as sensible" to an approximate splitting heuristic as Kd-Tree
"memory friendly : no duplicated primitives
"Quick to build"
"Adaptable" to small changes

Cons :
Problems with long primitives/ Diagonal are the least friendly .. problems with architectural scenes (this may be bettered with the
No strict front to back order--> no early out.


With regard to Rasterization, only the first "cons" seems relevant...
I see two other problems :
it does not manage big occluders, and I think it may not work well for an interior scene manager, however, by choosing the order of traversal well ie closest children first, you may get easy Z-culling.
May not be optimal regarding batches( however, reordering by batch may be possible).
User avatar
_tommo_
Gnoll
Posts: 677
Joined: Tue Sep 19, 2006 6:09 pm
x 5
Contact:

Re: ABTSceneManager

Post by _tommo_ »

[OT]
It's a while that i'm wondering... do spatial structure have any advantage at all?

I mean, traversing a really complex structure like this ABT requires a lot of memory reads, recursion, complex bounding computations etc...
And all of this to skip some polygons that would anyway be mostly killed by frustum culling.
After all modern cards can render tons of polygons, and techniques like deferred shading + postfilter remove most of the off-screen-drawing overhead... so the additional cost of unculled polygons could be lower than expected.

Given the near-insignificant effect of spatial culling, i think it would be easier and faster to bin all the geometry into one big single-level 3D array, so that you can access a cell using just three integer divisions.
This would cut off enough polygons, then a more fine-grained frustum culling could do the rest.

Of course Portal Scene Managers aren't included in this.
[/OT]
OverMindGames Blog
IndieVault.it: Il nuovo portale italiano su Game Dev & Indie Games
Sairon
Halfling
Posts: 94
Joined: Fri Apr 20, 2007 5:50 pm

Re: ABTSceneManager

Post by Sairon »

The problem that my icoseptree manager aims at isn't optimal rendering of geometry, that is highly specialized and there already exists decent solutions for that in Ogre. What's good with the icoseptree manager is that it handles moving and animated objects, while n-trees and the structures which are discussed seems to target static and preferably pre processed static geometry.
Post Reply