ABTSceneManager
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
ABTSceneManager
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?
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?
-
- Gremlin
- Posts: 185
- Joined: Sat May 07, 2005 3:27 pm
Re: ABTSceneManager
Would you by chance have a link to the papers you're talking about ?
I don't find them ...
I don't find them ...
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
Re: ABTSceneManager
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򤻢
[Lombard03] http://www.gamedev.net/community/forums ... =1󪯔
[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.
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򤻢
[Lombard03] http://www.gamedev.net/community/forums ... =1󪯔
[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.
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
Re: ABTSceneManager
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.
Let's start with this! ... we'll see results soon.
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.
Let's start with this! ... we'll see results soon.
-
- Gremlin
- Posts: 185
- Joined: Sat May 07, 2005 3:27 pm
Re: ABTSceneManager
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.
(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.
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
Re: ABTSceneManager
Thanks for the links, we can find huge informations and papers there! Amazing
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.
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.
- jacmoe
- OGRE Retired Moderator
- Posts: 20570
- Joined: Thu Jan 22, 2004 10:13 am
- Location: Denmark
- x 179
- Contact:
Re: ABTSceneManager
Is this outdoor or indoor scenes?
It it's indoor, I predict a big userbase..
If you are willing to share it, that is..
It it's indoor, I predict a big userbase..
If you are willing to share it, that is..
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
Re: ABTSceneManager
It's better suited for outdoor scenes.
Of course, I'll share it with the community.
Of course, I'll share it with the community.
-
- Gremlin
- Posts: 185
- Joined: Sat May 07, 2005 3:27 pm
Re: ABTSceneManager
I didn't perceive the difference between the ABT and a BVH... Since you have found one, can you please explain ?
Thank you.
Thank you.
- Rasengan
- Halfling
- Posts: 46
- Joined: Sun Jul 13, 2008 12:21 pm
- Location: Brussels
Re: ABTSceneManager
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
"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
-
- Halfling
- Posts: 94
- Joined: Fri Apr 20, 2007 5:50 pm
Re: ABTSceneManager
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.
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.
- xadhoom
- Minaton
- Posts: 973
- Joined: Fri Dec 28, 2007 4:35 pm
- Location: Germany
- x 1
Re: ABTSceneManager
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...
I´m also curious if this approach would be a (plug-in) candidate for Ogres paging functionality...
-
- Halfling
- Posts: 94
- Joined: Fri Apr 20, 2007 5:50 pm
Re: ABTSceneManager
Yeah. Noting special needed, uses Ogre plugin system.
-
- Gremlin
- Posts: 185
- Joined: Sat May 07, 2005 3:27 pm
Re: ABTSceneManager
<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).
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).
- _tommo_
- Gnoll
- Posts: 677
- Joined: Tue Sep 19, 2006 6:09 pm
- x 5
- Contact:
Re: ABTSceneManager
[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]
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]
-
- Halfling
- Posts: 94
- Joined: Fri Apr 20, 2007 5:50 pm
Re: ABTSceneManager
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.