#### Archived

This topic is now archived and is closed to further replies.

# Totally newbish question on scenegraphs, trees, etc..

This topic is 5062 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

OK, so I''ve read every bloody topic on this forum - including the ones with Yann''s wisdom. I''m currently in the process of designing a simple engine and I''m currently thinking about scene management. This is what I have in mind so far: - Have a scenegraph for a hierarchycal representation of the scene - The scenegraph would contain indices/pointers into a global list of all dynamic objects - It would contain (at the root level) an octree for static indoor geometry and a quadtree for outdoor terrain geometry This is all very basic stuff. But I''m having problems with incorporation collision detection into all this. Collision detection would require somekind of a structure with dynamic objects grouped in relation to their position, and that would mean a dynamic tree. Yann''s ideas about using degeneration factor and stuff are very interesting. But would I have to build a second tree for collision detection? How do you manage your scene in your engines/games? Bah.. the more I read, the more lost i feel

##### Share on other sites
quote:
Original post by klajntib
Bah.. the more I read, the more lost i feel

Same here...

Anyway, don''t you think portals, bsp or abt might be better for indoor areas? (abt can also be used for outdoor).

Octtree/quadtree/abt are all dynamic. I don''t think you need another tree for collision detection. Check the collider with every collidee in the same node.

I''m very noob, and haven''t started to implement trees, but the above is what I think, based on what I''ve read (Including YannL''s excellent posts).

##### Share on other sites
i haven''t written any scenegraph implementations yet, but I usually insert dynamic objects into leaf nodes of the tree. A direct access quatree can make this very simple as the leafnode to insert in to can be determined using the players x,z locations. once all dynamic objects are in the tree you just need to test objects that exist in the same leaf nodes against each other for collision.

##### Share on other sites
quote:
Original post by frostburn

not true, necessarily. the standard implimentation of the above is dynamic at build time, but static at run-time. this is the same as with BSPs. at build time you dynamically throw your polygons into the data structure, but at run-time you statically load them from a file already in the structure. they are intended for non-moving objects. there are a few methods that i''ve seen/used for keeping dynamic objects in the correct tree node, but they''re largely inefficient. you definitely don''t want to be splitting your geometry up between tree nodes at runtime b/c it''s a really slow process. if you''re using the tree for your dynamic objects as well as the static ones, you''ll end up with multiple instances of your dynamic objects in the tree at the same time. i.e. an object can potentially occupy up to 8 leaf nodes in and oct-tree or 4 nodes in a quad treee. it can still help with collision detection, but there are better algorithms for the implementation of collision detection amongst dynamic objects.

on a first pass you check the dynamic objects each against the octtree/quadtree, then you check them amongst eachother using something like a .... searching for term... called something like a prune sweep or pruning (don''t know the algorithm i''ve just heard the term )...

-me

##### Share on other sites
Yeah, that''s the problem. Inserting object dynamically is a pain in the ass and also very slow. So, whats that pruning stuff?

http://parallel.vub.ac.be/documentation/pvm/Example/Marc_Ramaekers/node3.html

Hm... what about culling? I would use frustum culling, but that''s probably not enough. Any tips?

And also - sorting by shader and texture - how would I go about integrating that into my scenegraph? Blah.. so many problems

##### Share on other sites
You don''t exactly integrate the spatial division (i.e., octree) with your scenegraph; the two are basically independent, and just happen to hold pointers to the same objects. Your scenegraph simply helps you organize objects conceptually (and apply hierarchical transformations), while your spatial division scheme helps you decide which objects to render this frame (among other purposes, including perhaps collision detection). Sorting of the objects is accomplished by your graphics engine, so it''s not really integrated with your scenegraph / octree at all.*

* I''ve seen some people sort objects within octree nodes, but whichever way you choose really depends on your engine.

##### Share on other sites
Yeah that''s what I was thinking, but didn''t know how to put it in words

So I should use an octree or something for dynamic objects too? And rebuild it when it gets too deformed of what? How costly is ti to constantly update the tree? Yann talked about ABTrees or something - but I have no clue what that is - and how he rebuilds certain branches from time to time...

And about sorting - what I''m having problems is the fact that if I apply transformations and draw everything as I traverse the scene graph, I have no way of sorting by texture and stuff... so I should traverse the scene graph and store world transformation matrices and compute other stuff (skeletal animation matrices and soforth) and then have another class (for example the renderer) go through all objects, sort them by shader for example and then draw them using the data previously computed by the scene graph traversal?

##### Share on other sites
Octtrees/Quadtrees static at runtime? I definitely need to read more before trying to implement it
I''d rather go with ABTs anyway..

ABT: Axial Binary Tree.

Fore each branc you split either along the X, Y or Z axis.

NOTE: The location of the split can vary. the splits aren''t linearly spaced. Any split objects will be wholly contained in the "current" and the nabouring node.

Luvly ASCII art:
2D ABT:Root+-------+|       ||   a   ||       |+-------+1: split along Y axis+---+---+|   |   || b | c ||   |   |+---+---+2: split along X axis (right branch shown)+---+---+|   | d || b +---+|   | e |+---+---+(The next are enlarged to make it easier to see and "draw")3: Split along Y axis (Right top shown) - For 3D split Z instead+-------+---+---+|       |   |   ||       | f | g ||       |   |   ||   b   +---+---+|       |       ||       |   e   ||       |       |+-------+-------+4: Split along X axis (Right top left shown) - For 3D split Y instead+-------+---+---+|       | h |   ||       +---+ g ||       | i |   ||   b   +---+---+|       |       ||       |   e   ||       |       |+-------+-------+a             (root)+ b             (left)+ c             (right)| + d             (top)| | + f             (left)| | | + h             (top)| | | + i             (bottom)| | + g             (right)| + e              (bottom) (I only made one part of the tree)for a 3d tree it could be:(root)  (left)    (top)    (bottom)      (in)      (out)        (left)        (right)  (right)etc.Problem with Quadtree:    a   b   c   d  +---+---+---+---+1 |   |  ###  |   |  +---+---+---+---+2 |   |   |   |   |  +---+---+---+---+3 |   |   |   |   |  +---+---+---+---+4 |   |   |   |   |  +---+---+---+---+(### = object)The object gets split and ends up in b1 and c1. These nodes are spatially neighbors, but not hierarchially neighbors.Tree:(root)  (12ab)    (1a)    (1b)    (2a)    (2b)      ##   (1/2 object)  (12cd)    (1c)      ##   (1/2 object)    (1d)    (2e)    (2f)  (34ab)  (34cd)An ABT would AFIK avoid splitting the object by moving the split.

If someone could correct any mistakes that would be great.. The only source I have for ABTs are Yann''s and other''s posts here on GameDev.

##### Share on other sites
Oh, thank you veryveryvery much This explains a lot!
PS: You''re a talented artist

This tree is initially created on runtime, then it is constantly checked for degeneration and when it gets too degenerated, you just rebuild certain branches. Correct me if I''m wrong somewhere

This seems very cool. So basicly I should have 2 spatial partitioning trees - one for static geometry that always remains the same and one for dynamic objects, that is constantly checked for validity and "repaired" if objects move around too much. (this is how yann does it I think..)

And have a scenegraph for a purely logical representation of the scene.

The I would do this every update:
- Go throught the scenegraph and calculate all transformations etc. and store it.
- Go through the ABT for dynamic objects and check for collisions and simultaneously determine visibilty and add visible objects to a renderlist
- Go throught the tree of static geometry and find visible parts and add them to the renderlist
- Sort the render list by shader and maybe by texture so as to minimize state changes
- Draw

But this could be very ineffective for various reasons:
1. There''s tons of tree traversal going on - how slow is this?
2. Sorting could take a while, but a simple bucket sort should be fast enough
3. Doing things in this order kind of breaks CPU-GPU parallelism or at least I think so... because I first do purely CPU work and the purely GPU work...

Thoughts? Ideas? Sugggestions?

##### Share on other sites
quote:
Original post by klajntib
So I should use an octree or something for dynamic objects too? And rebuild it when it gets too deformed of what? How costly is ti to constantly update the tree? Yann talked about ABTrees or something - but I have no clue what that is - and how he rebuilds certain branches from time to time...

One possibility is a "loose octree" by Thatcher Ulrich - google will find it.

quote:

And about sorting - what I''m having problems is the fact that if I apply transformations and draw everything as I traverse the scene graph, I have no way of sorting by texture and stuff... so I should traverse the scene graph and store world transformation matrices and compute other stuff (skeletal animation matrices and soforth) and then have another class (for example the renderer) go through all objects, sort them by shader for example and then draw them using the data previously computed by the scene graph traversal?

Yes.
quote:

3. Doing things in this order kind of breaks CPU-GPU parallelism or at least I think so... because I first do purely CPU work and the purely GPU work...

It''s ok for PCs because (at least with Direct3D) the driver buffers up to 3 frames worth of render commands (even with vsync enabled). So if your CPU is running ahead of the GPU it doesn''t matter whether the CPU is traversing your scenegraph or sending the sorted renderlist to d3d/ogl because the GPU is still working on the previous frame or the frame before that even. And if the CPU spikes temporarily due to, say, a fixed 20Hz physics update then it has up to 3 frames of padding where it doesn''t have to feed anything to d3d/ogl.
If your CPU is running behind your GPU (ie no frames are buffered) then it''s probably because the CPU can''t keep up (on average) but you''re still getting CPU/GPU parallelism.

##### Share on other sites
Thanks Solied! I''m probably going to get down to designing it right now

Any more tips and thoughs are most certainly welcome

##### Share on other sites
quote:
Original post by klajntib
And have a scenegraph for a purely logical representation of the scene.

The I would do this every update:
- Go throught the scenegraph and calculate all transformations etc. and store it.
- Go through the ABT for dynamic objects and check for collisions and simultaneously determine visibilty and add visible objects to a renderlist
- Go throught the tree of static geometry and find visible parts and add them to the renderlist
- Sort the render list by shader and maybe by texture so as to minimize state changes
- Draw

But this could be very ineffective for various reasons:
1. There''s tons of tree traversal going on - how slow is this?
2. Sorting could take a while, but a simple bucket sort should be fast enough
3. Doing things in this order kind of breaks CPU-GPU parallelism or at least I think so... because I first do purely CPU work and the purely GPU work...

If you build your scene graph logically rather than spatially*, wouldn''t your renderlist should be almost completely sorted already, without needing to do any extra sorting?

*Of course some spatial ordering will be useful, but ideally within logical categories, not outside them.

##### Share on other sites
Well, it depends on how you define "logically".
As it looks now, it just might happen that I''ll have a bunch of level 1 nodes with very few children.

If for example I have a box, a car with 4 wheels and an NPC character holding a torch which has a flame emitter attached to it - they would be in the tree like this:

Root|- box|- car   |--wheel   |--wheel   |--wheel   |--wheel|-- NPC   |-- torch      |-- flame emitter

So this does provide some visibility culling possibilites, but from this tree I cannot conclude that if the torch is not visible the flame emitter is also not visible... and this is why I think I would need another purely spatial & dynamic tree.

Thoughts?

##### Share on other sites
quote:
Original post by klajntib
Well, it depends on how you define "logically".
As it looks now, it just might happen that I''ll have a bunch of level 1 nodes with very few children.

If for example I have a box, a car with 4 wheels and an NPC character holding a torch which has a flame emitter attached to it - they would be in the tree like this:

Root|- box|- car   |--wheel   |--wheel   |--wheel   |--wheel|-- NPC   |-- torch      |-- flame emitter

So this does provide some visibility culling possibilites, but from this tree I cannot conclude that if the torch is not visible the flame emitter is also not visible... and this is why I think I would need another purely spatial & dynamic tree.

Thoughts?

Well, suppose you had multiple cars, you could group them under a ''cars'' node, e.g:

Root|- box|- cars     |-car1        |--wheel        |--wheel        |--wheel        |--wheel     |-car2        |--wheel        |--wheel        |--wheel        |--wheel|-- NPC   |-- torch      |-- flame emitter

If you have a lot of cars, and they are very widely distributed, you could arrange them in some kind of loose spatial hierarchy underneath the ''cars'' category. Same goes for boxes - with the additional bonus that you can batch stationary boxes which are close together into one big lump and render them all at once, which is quicker than rendering them separately.

As for the flame emitter issue, provided you make the bounding volume for the emitter large enough to cover the area of influence of the flame''s light, and propogate that upwards to the torch, and npc bounding volumes etc... there shouldn''t be a problem.

It''s true that with a hierarchy like this your culling is going to be less efficient, but culling isn''t really that expensive an operation - and you should save a lot by being able to avoid unnecessary state changes or additional sorting later on, with the exception of alpha blended stuff.

I''m not really an expert on this though, I''m just going by what I''ve picked up from Yann''s posts and various other things I''ve read about the subject.

##### Share on other sites
From what i gather the idea with the ABT is that it is used to cull dynamic objects and is seperate from the logical scenegraph hierarchy. While this makes culling more efficient it does seem to make the transform update more expensive. I''ll try and explain.. Say you have a highly complex, dynamic and huge world, and you have both a logical hierarchy and ABT. The ABT will be used for culling this world, but before that you''ll have to traverse the scenegraph updating the transforms. Since you need the ABT for culling, and the ABT needs the transforms, won''t you have to traverse the entire hierarchy and update every transform? Or will the transform update use some kind of gross culling seperate from the ABT? In that case, why bother with the ABT at all? Or am i completely missing something here?

##### Share on other sites
Yeah, I think you missed something (or maybe I did)

All my dynamic entities would be stored in a sepparate list/array.
Both the SG and ABT would only have indices/pointers to the entities.

So I would go through the SG applying transformations to all objects and store the previous transformations for object.

Then I would process the ABT and cull + process collisions.

This seems to be somewhat optimal, but since I haven''t implemented it yet I have no idea if it would even work and more so if it would yield a significant speed increase.

So... opinions, tricks, tips.. help me people!

##### Share on other sites
quote:

So I would go through the SG applying transformations to all objects and store the previous transformations for object.

Then I would process the ABT and cull + process collisions.

That is exactly what i meant. You have to traverse the entire SG to calculate the transforms. If you''re traversing the entire tree anyway then you might as well cull as you go along, instead of using the ABT.

The method you suggest is optimal in that the culling is faster, but the extra cost is that you have to traverse the entire SG when updating transforms. For a very large world that could get obscenely expensive.

##### Share on other sites
Ooops.. I seem to have missed Sanders last reply completely.. must get more sleep.

What you are proposing is cool, but it kind of breakes the concept of a scenegraph, if my idea of it correct. Or I could be completely wrong

I always thought that a scenegraph is supposed to be parent-child organised in such a way that any transformation that is applied to a parent is also applied to it''s children.. example:

I have a carrier with 10 gun turrets on it and also 5 planes in the hangar. There''s also a smaller ship in the scene. My scene graph would be:

Root|-carrier  |- turret (10x)  |- planes (5x)     |- bombs attached to the planes|-smaller ship

So if the carrier turns by 30° every object on it turns with it.

And what you are proposing (if I understand you correctly) is something like this:

Root|-ships  |-carrier  |-smaller ship|-turrets  |-turrets (10x)|-planes.. etc

Is this how you imagined it?

##### Share on other sites
quote:
Original post by treething
quote:

So I would go through the SG applying transformations to all objects and store the previous transformations for object.

Then I would process the ABT and cull + process collisions.

That is exactly what i meant. You have to traverse the entire SG to calculate the transforms. If you''re traversing the entire tree anyway then you might as well cull as you go along, instead of using the ABT.

The method you suggest is optimal in that the culling is faster, but the extra cost is that you have to traverse the entire SG when updating transforms. For a very large world that could get obscenely expensive.

Woohoo.. replies coming faster then I can type

Yeah, I have no idea how costly tree traversal is.
But the key thing here is also collision detection which by all means has to be minimized. Culling and collision detection could as well outweigh the cost of 2 traversals.

I guess I''d just have to test it both ways with different scenes and find the way that''s optimal. Who knows - maybe it''s somewhere in between

##### Share on other sites
Hmm, I actually didnt consider collision detection. (None of my apps have ever required it).

I was really just thinking of the culling for rendering the main camera view. If you add in other things then you''ll see more benefit from the seperate ABT tree. It would still be nice to reduce those traversals in an elegant way though..

##### Share on other sites
quote:
Original post by klajntib
Ooops.. I seem to have missed Sanders last reply completely.. must get more sleep.

Yes you should, since you got my name wrong too

quote:
What you are proposing is cool, but it kind of breakes the concept of a scenegraph, if my idea of it correct. Or I could be completely wrong

Not really - I was thinking that in the absence of any other kind of ''logical'' hierarchy, grouping by ''object type'' would be a good alternative in order to avoid having a wide, flat tree. Since objects of the same type aren''t necessarily spatially coherent, you could then break them up with some kind of spatial tree in order to make culling them all easier. However, I''m not so sure that that''s the best way to go now.

quote:

Root|-ships  |-carrier  |-smaller ship|-turrets  |-turrets (10x)|-planes.. etc

Is this how you imagined it?

Not quite, as I said above I was thinking of hierarchy-by-type being useful in the absence of any other logical hierarchy, in order to avoid a scenegraph that''s stupidly wide and only a couple of levels deep.

Root|-ships  |-carrier     |-turrets (10x)     |-planes  |-smaller ship     |-turrets.. etc

While this might work pretty well for static objects, I''m not so sure about the dynamic ones now. After all, should the planes be chidren of the carrier, children of the inevitable ''planes'' node, or both, or what?

In fact, I think with a bit of thought, you can probably find logical categories for these things, or at least, logical categories should develop as the game goes on. So you might end up with something like this:

Root|-fleet   |-convoy      |-carrier        |-turrets (10x)        |-air squadron           |-planes          |-smaller ship        |-turrets      |-submarines|-air squadron   |-planesetc.

##### Share on other sites
What the ..??!? How the hell did I manage to get your name wrong... I was looking at your post while COPYING your name! Must use copy/paste next time.

Your ideas on constructing the scene graph are very helpful.. now I just have to figure out exaclty how to do collision detection and culling efficiently along with it.

Lots of hard work to come.
Any other ideas are welcome!

##### Share on other sites
quote:
Original post by klajntib
And about sorting - what I''m having problems is the fact that if I apply transformations and draw everything as I traverse the scene graph, I have no way of sorting by texture and stuff... so I should traverse the scene graph and store world transformation matrices and compute other stuff (skeletal animation matrices and soforth) and then have another class (for example the renderer) go through all objects, sort them by shader for example and then draw them using the data previously computed by the scene graph traversal?

My mesh data structure "surfaces" which are groups of polygons, dots, patches etc. all with the same material (which contains texture data, alpha values, colours, shaders and stuff). When traversing all the visible mesh structures it''s really easy to split everything up by material. Currently the only reason I''m doing it is to separate out all the alpha blended surfaces so I can sort and render them last but the process seems to be quite useful for other reasons too.