My question for this posting concerns whether I am using/understanding scene graphs appropriately in my game engine design. [BTW, thanks for the replies to my posting of last week re: BSP Trees vs. Scene Graphs. I found the replies quite helpful.] I’m handling static objects (stationary) and dynamic objects (moveable) separately in my game engine design. I’ve set up a scene graph to model a level in a virtual world as follows. The root node of the scene graph tree refers to the level itself, and has multiple internal nodes, each of which might refer to a region of the level. Of course, all nodes in the scene graph have their own bounding volumes. A region node would have multiple internal nodes referring to sub-areas, hallways or rooms within that region. A room node would have internal nodes referring to desks, chairs, lamps, etc. This decomposition continues down to some atomic level (e.g., to a drawer in a dresser). Also, I should mention that the polygons representing the floors, walls and ceilings of the level are not part of the scene graph in my design. They are modeled and rendered separately in a BSP tree. Anyhow, having the scene graph set up as above allows me to do visibility and collision culling. For example, if a region’s node does not intersect the view frustrum then I don’t have to traverse it’s internal nodes during rendering. Or, if the player doesn’t “collide” with the bounding volume of a room’s node, then I don’t have to check for collisions with nodes internal to that room. It seems like this only works if I don’t try to model dynamic objects in the scene graph. If a bot, which has the freedom to move from room to room (or region to region, for that matter) is modeled as a scene graph node, then I’d constantly have to check to see if it should be relocated within the tree. If a bot walked out of a room and into a hallway then it seems that I’d have to remove the bot’s node from the room’s node and insert it into the hallway’s node. [overhead/complexity]. Also, if a bot was in the process of leaving a room it might be considered to be “in” the room, but it’s foot might have extended into the hallway. If the hall intersected the view frustrum and the room did not, then the foot which perhaps should be rendered might not be. It seems that I could allow dynamic objects to be in the scene graph if I restricted their movements so they couldn’t leave the bounding volumes of their parent nodes. Such a bot which could patrol inside a room, but not leave the room, for example. For the above reasons I’ve model static objects as nodes in the scene graph and dynamic objects separately. I don’t feel comfortable with this, however. I feel like I’m missing the boat and not truly understanding the scene graph concept. I feel that I should be able to include dynamic objects as just another branch in my scene graph, but I can’t see how to do so without incurring a lot of complexity to handle special cases such as described above. Any insight as to handling dynamic objects in scene graphs would be greatly appreciated. Thanks.

Okay I had to read your post a number of times because something of the things you have described just sound backwards to me.

Generally dynamic objects are well suited to typical/traditional style scene graphs that what yours sounds like to be.

Where visibility determination preformed on the scene graph of dynamic objects can be done efficiently via nested bounding volumes and thus quite similar to bounding volume hierarchies (BVH), typically (not always, depends) static objects are handled separately from the scene graph or are allowed to be encoded in any spatial data structure desired not the other way round as you’ve described.

Also you’ve mentioned removing and re-inserting on every update sounds like a naïve method. Typically what is done is bounding volumes are updated from leaf to root only when bounds are invalid.

On the update pass via a depth-first traversal of the scene graph, concatenation of transformations are calculated on the downward pass and cached in leafs then on the upwards pass bounding volumes are updated from leaf straight up to root node via a merging algorithm that’s dependant on the type of bounding volume you are using, where parent’s bounds are recalculated via merging of children bounds.

Note that you can obtain temporal coherence here, when doing viability determination of dynamic objects, if you keep the set of visible objects from frame to frame and check that set is still valid the next frame (via flags or something similar) then you don’t have to keep traversing the entire scene graph every frame. The same applies for collision culling.

In order to maintain scene graph bounding volumes you should use a bounding type that is cheap, bounding spheres are generally used in scene graphs because they are very cheap, they are invariant to rotation and they are quick to test against the view frutum.

It makes the process very efficient how-ever they generally are poor fitting volumes so don’t expect to have good culling mechanism for rendering or collision detection with this setup alone.

What should be done is for large static geometry they should be encoded in some spatial data structure and culling should happen with in when that node is reached (or handled separately). For exact collision detection of dynamic objects they should also be encoded in some spatial data structure generally real bounding volume hierarchies are best for these OBB trees or AABB trees (or ABT trees?) basically model partitioning types are generally better than spacial ones in this case (well so i've read i maybe wrong).

If you want to know about how to perform maintenance of bounding volumes in a scene graph, there is a sample chapter of Dave Eberly’s recently released book 3D Game Engine Architecture here which is the chapter actually on the basics of these kind of scene graphs.

That being all said and done, traditional/typical Scene graphs have there disadvantages, it maybe better to maintain more than one scene graph, have multiple scene graphs each one used to make certain operations faster e.g. culling, picking etc. Other alternatives are merging of spatial data structure into the scene graph structure itself making hybrids. In both cases these setups are not well documented or people don't really want to give away there magic [smile] and what information there is they don't match up plus everyone has there own view about it.

[Edited by - snk_kid on March 30, 2005 3:57:58 PM]