Scene graph confusion

I'll try to give the simplest answer possible, you'd insert an "object" into a group/transform (child container) that "logically" makes sense, say for instance you have a scene graph representing a house with 4 rooms each already with some random objects in them:

Key: [o] := any old object ------------------------------------|                 |                  ||  [o]        [o] |                  ||                 |   [o]    [o]     | House|       [o] Room1 |                  ||                 |  Room2           | ----------------- ------------------|                 |       [o]        ||  [o]     Room3  |           Room4  ||                 |    [o]           ||            [o]  |                  ||                 |           [o]    | ----------------- ------------------Your graph/tree would look like so:Key: *    := Plain Group [|]  := Transform Group [0]  := Some Visual Object (leaf Node)                             House (*)                                |                                |         [|]------------[|]-------------[|]-------------[|]          |              |               |               |        Room1          Room2           Room3           Room 4          |              |               |               |    [|]--[|]--[|]    [|]---[|]       [|]---[|]     [|]--[|]--[|]     |    |    |      |     |         |     |       |    |    |    [o]  [o]  [o]    [o]   [o]       [o]   [o]     [o]  [o]  [o]

Okay lets say we want to add new a object into "room1" at some arbitrary position relative to "room1"'s local coordinate system (Parent-Child).

So first you'll need to instantiate a new transform group with the right coordinates in "name1"'s space and add the new object to it as child, then you need to traverse the tree from root in a recursive fashion until you find the group (transform group) Room1 and then just add the new group as a child of Room1 you'll end up with:

                             House (*)                               |                               |         [|]------------[|]-----------[|]-------------[|]          |              |             |               |        Room1          Room2         Room3           Room 4          |              |             |               | [|]--[|]--[|]--[|]  [|]---[|]     [|]---[|]     [|]--[|]--[|]  |    |    |    |    |     |       |     |       |    |    | [o]  [o]  [o]  [o]  [o]   [o]     [o]   [o]     [o]  [o]  [o]                 ^                 |              New object

How you do the "checking" doesn't really matter, you could give all nodes a string name and do your check with "Room1" say.

If your wondering how nested bounding volumes come into play with this then i'd suggest (re)computing bounds in lazy manner (lazy evalution) i.e. on an as and needed basis not as soon as you make an insertion/modification/update/etc of an object only when you the time comes where you actually need the bounds of an object/group/etc. You can do this by maintaining an "isDirtyBounds" flag in all node types in the base SG node that gets set to true when a modification/update is made to the SG that "could" effect BVs.

When the time comes to "get bounds" of a node you check if the bound's "isDirtyBounds" and if it's set to true, if it's a leaf node type that represents say geometry then it'll just recompute it's bounds in model coordinate space if it's a group node type then it needs to (re)compute the bounds of the entire group this will be a recursive method as you would expect.

[Edited by - snk_kid on December 15, 2005 8:25:54 AM]

Thx for your answer!
But one question still remains:
How do I know I should add that new object to Room1´s "group"?
Assuming I have that first scenegraph of yours, and the scene graph is told to add that new object, how would it know which room that object belongs to or which room it fits in best?
Let´s say the map designer had designed this house with 4 rooms and some objects in it, it would be quite tedious for him to assign these objects to the rooms manually, so there should be a way of calculating which room would be best to add an object too.
Thx for the explanation of the nesting bounding volumes, I think I should have a quite good understanding of that now.

Hi,

lets assume you have a bounding box or shere for each node. Than you could just see in which it fits best (beacuse you might get overlaps).

Get the lowest Node this is fit in. If you have more then one on the same level, see to which center it is closest.

hmm... thx for the suggestion, sounds like a neat idea. Wonder why I didn´t get that idea myself to put the new object into a node where it would change bounding volumes the least, i.e. finding the best fitting volume for it.
Will ponder that again tomorrow, when I´m less tired and had less wine ;)
Thx again!

Actually, you probably want to implement the scene graph such that it uses something like a loose octree within its internals, and puts the parents/children within the appropriate nodes of that tree -- not just in a flat splay tree, like the API might lead you to believe. I e, you can make the octree there in the implementation, but invisible in the API.

Then, when time comes to render, you visit the octree using a frustum intersection visitor, and consider (only) the nodes that come out of that visiting pass. The "visit scene graph with {intersection volume}" functionality of your graph uses the octree in the implementation, but still don't need to expose that to the rest of the world.

The nice thing about this is that you can start out without using the octree, and only add the tree (with its complexity) when what you have doesn't perform well enough.

Hi matches81!

Eberly is no joke. My 3D engine is basically an implementation of his book, and it's quite fantastic, if I do say so myself (although I have an OctreeNode class that pretty much just rules). :D He also supplies his own implemenation which you can find on his website link. Grab this and that will give you some serious detail on how the scene graph he describes works. I've even toyed with the thought of dumping my own engine and using his and optimizing the parts that need work.

I've also seen a couple of commercial games that implement his design (can't name em cause of NDA). The commercial Gamebryo engine is also based on this design, which I've had the pleasure of using as well.

- John

thx for the suggestion to have a look at the source of WildMagic. I´ve looked at some application samples coming with the source and it seems the scene graph is in fact build "manually", which means I´d have either have the map designer build some sort of hierarchy and save that or use something else than the scene graph to calculate a spatial hierarchy amongst dynamic objects, then either save that to a file from the map editor or build that hierarchy when loading the map.

So my next questions are coming along:
I´m most likely to have something below 1500 dynamic objects in my map, most of them being smaller than the smallest node in the octree for the static part of the map. They will also mostly be seperate from another, so logical parent-child relationships will be an exception, I guess (except for some lifts or moving platforms and stuff like that). So I´ll end up with a bunch of small dynamic objects being more or less randomly spread around my map.

1. Is a scene graph even something I would like to have in such a situation?

2. Should I simply put those dynamic objects into the octree for the static map?

2.a) If you think I should, how would I handle dynamic objects crossing leaf nodes of the octree and therefore belonging to more than one leaf node?
2.b) If you think I should not add them to the octree, any suggestions what kind of hierarchy I could use to manage those dynamic objects?

If you´ve read this and thought about an answer, thx.
If you´ve posted an answer, thx again ;)

[edit]
@hplus0603:
sry, overlooked your post first. So what you are suggesting is using another spatial hierarchy, a loose oc-tree (have to read up on that one, only know quadtree and octree with the regular division thing), and somehow use that to build my scene graph internally? Could you explain a bit more, since I didn´t get how I would go about establishing the link between the loose oc-tree and the scene graph? Or would they be the same?
[/edit]

Hi,

About the dynamic entities : For each entity, I would store 8 pointers to the nodes they belong to. 8 pointers because an entity can cross up to 8 octree node (in the case the dynamic entities are smaller than the smallest octree node)

Each frame you move your dynamic entities. As you know their directions, you can predict in which node they will enter. So this pass is quite fast.

Then, when rendering, you navigate through the octree, update the visibility of each node, then render them. After that, you loop through your entities, and before rendering it, you check if at least one of the nodes it belongs to is visible.

In fact I wouldn't implement a scenegraph for a simple project. I don't know how big your project is, but sometimes, a simple dynamic array of entities (use a virutal interface to store different kind of graphic entities) is easier / faster.

thx for your answer, Paic!

The project won´t be _that_ complex I hope, at least on the graphical side of things:

There will be a static map consisting of a regular grid, each grid containing one background mesh (brick wall, stone, vent in a wall, such things and everything you can put into a mesh and make it fit in the grid and look good), one mesh for the floor (so you can model anything you want as floor), one ceiling mesh and one mesh for the foreground wall (will be culled away most of the time, but is there to allow some camera-paths through the level for cutscenes and so on). This grid will only contain a classic 2-dimensional map at first, but corridors along the z-axis are planned as well, which is why I chose an octree to cull that.
So after all I´ll end up with a 3D-grid (or array if you choose) filled with the stuff I explained above.

The "dynamic" part of the map will contain everything that can move or is just a small decorational asset (like a trashcan standing in a hallway for example, that wasn´t included in the static background mesh, so the map designer can place these assets more freely). So these objects will most likely be completely seperate and fairly even spread around the map. In fact the only example of two dynamic objects having a direct relation to each other, would be a dynamic object placed on a lift that moves.
I guesstimate that in complete I might end up with 1 to 1500 dynamic graphical objects per map.

Sry about the rant, but perhaps this helps clear the problem up a bit.
I think, a dynamic array of entities could suffice, I guess I´ll just implement it that way and see how it goes. Perhaps it´s fast enough and I struggled with that scene graph thing all for nothing (well, except for the nice feeling of my mind swirling around the problem ;) ). If it isn´t fast enough, adding a scene graph later on shouldn´t be that much of a problem (except for the one discussed here and I hope some suggestions made here might help solving it).

Thx for the help @all

Quote:

Original post by matches81 thx for the suggestion to have a look at the source of WildMagic. I´ve looked at some application samples coming with the source and it seems the scene graph is in fact build "manually", which means I´d have either have the map designer build some sort of hierarchy

Exactly! And that's what's so great about it. For example with my 3DSMax exporter, I simply build a scene graph from the geometry data that I'm trying to export, and then run the serialization on it. Opening it up and loading it from the game engine then takes two or three lines of code because I just have to open the archive, clone the node, and place the clone into the root node of the scene (or the containing cell).

For building the game scene, I would either

1) create a new node type that referenced exported objects, or

2) use my own data file for the scene that referenced exported objects.

Since probably you're going to want to create instances (using the clone() method) of many objects, instead of loading copies of them, the latter approach would be more straight forward.

However, wild magic supports shared data in its scene graph (this does take a little getting used to because it's not as straight forward as Plain Ol' Serialization due to a re-linking pass). So, if you were to create your world editor in such a way that it properly used object instances, then you could export the entire scene, but you wouldn't be able to progressively load the scene using that techinque. Depending on how "progressive" you wanted to be, you could create a new node type that loaded the objects (probaby asycronously) when they came into or near the range of the observer.

If you wanted full progressive loading like what is used in a lot of MMOs you would need to come up with something a little more complicated because you would probably want to split the scene in such a way that it would be easily randomly accessible (regular grid chunking or even B+-trees come to mind).

Thats a lot, I hope it makes sense!

Quote:

Original post by krum Quote: Original post by matches81 thx for the suggestion to have a look at the source of WildMagic. I´ve looked at some application samples coming with the source and it seems the scene graph is in fact build "manually", which means I´d have either have the map designer build some sort of hierarchy Exactly! And that's what's so great about it. For example with my 3DSMax exporter, I simply build a scene graph from the geometry data that I'm trying to export, and then run the serialization on it.

I can see how having a sane (well, more or less) person build the scene graph manually could be an advantage, since he knows some things about the scene a program wouldn´t, but:

I can´t imagine a map designer (using my imaginary map editor, which is yet to be done) adding every NPC, lift, door, trashcan and so on that he places in the map to a scene graph. In fact I wouldn´t like that too much either, since I wouldn´t want a map designer to hassle with something so vital to my engine. So there should be a way of building a scene graph for all the props and stuff placed in a map procedurally, without having a map designer interfere with that.


---------------------------------------------------

I also thought about joining static and dynamic part of the map. If you read my posts above I stated that I wanted to use a quad-tree / oc-tree for the static part of the map, due to its uniform layout, and a seperate scene graph (or anything) for the dynamic objects.

Now I thought about Paic´s original suggestion of using 8 pointers to the nodes for every entity and have come to a problem:
In the last quadtree I implemented, which was only used for culling, when a node I visited was fully visible (being completely inside the frustum) or fully invisible (completely outside the frustum) I stopped culling its children. Furthermore I didn´t notify its children about their visibility status nor did I set it, which saved the time of having to visit every node of the tree. But if I would use these node-pointers I would have to notify every node about its new visibility status and set it accordingly, otherwise I might end up with an entity having a pointer to a node which visibility status is not up to date.
So I don´t know for sure, but this method seems to have the advantage of using the already existant quad-tree / oc-tree, but also seems to include the drawback of slowing it down a bit, because I would have to update every node´s visibility status every frame.
Any thoughts?

Furthermore I think one pointer to one node should suffice. If an entity is too large to fit into a (leaf) node of my quad tree, I could point to its parent. This would simplify checking whether an entity is visible or not, and I don´t see a drawback. Perhaps I´ve not thought it through thoroughly enough.
Could someone approve / disapprove this thought?

Quote:

Original post by matches81 Furthermore I think one pointer to one node should suffice. If an entity is too large to fit into a (leaf) node of my quad tree, I could point to its parent. This would simplify checking whether an entity is visible or not, and I don´t see a drawback. Perhaps I´ve not thought it through thoroughly enough. Could someone approve / disapprove this thought?

I'm pretty sure that's how its usually done; at least that's how its been done on every commercial engine that I've seen. Bounding volumes don't go into nodes unless they're fully contained. The only drawback is that objects that reside on the edges of larger nodes or at the origin will probably be tested a lot.