I have a feeling that I haven’t done a good job of describing the topic which I really wished to discuss. In a moderately complex game there needs to be a mechanism to perform geometric queries. This database needs to be able perform the following operations at least reasonably well: add, delete, move and intersection. Where “intersection” tests the contents against some geometric object(s). Some examples include (but are far from limited to):
-
Frustums: potential visible set (hopefully near minimal) for rendering, visually perceived events, etc.
- Spheres: point lights, broadband collision/nearest neighbors
- Boxes: broadband collision/nearest neighbors
- Capsule: broadband collision
- Lines: cheap line-of-sight and some instantaneous events.
For games that have simple “environments” and few entities, the method of storage is of little importance. As the complexity grows, being able to perform of above and similar operations quickly becomes critical.
To be very repetitive: spatial partitioning techniques are not scenegraphs.
A Scenegraph is a hierarchically data-structure, where states that are applied to a given node propagate to all children. Ignoring all kinds of states other than geometric, this means all nodes are within a local (scaled) coordinate frame of its parent. Now let’s assume that the only geometric operations allowed are linear transforms, which is a reasonable limitation. This means that it is effectively is a direct representation of a ridged body system. This is the “strength” of scenegraphs. The ability to simply manipulate a node and all of the modifications are auto-magically applied to the children. It’s is also what makes it nearly worthless as a “world” representation of any complexity. Some issues:
Since state information is all local, when you need global states either the tree must be traversed, concatenation states, for each query (very bad) or they must be cached. This means when a node is updated that the cached values of all children of the node need to be updated as well. The performance of the update can be reduced with a lot of duct tape and glue to avoid computation until needed.
Likewise the data structure presents no spatial coherence. Specifically there is no way to perform the kind of queries that I listed at the start of this post, other than visiting every entry in the structure. Again concatenating states or yanking cached values as one performs the walk. Wait! Hold the phone! Early on people working on scenegraphs noticed this glaring problem and it can made slightly less bad by maintaining a bounding volume hierarchy (BVH) for each node. This volume (typically bounding box, axis aligned bounding box or sphere) covers the entire “extent” of the node and its children. The implication of this is when a node is modified it updates its BVH, then recursively updates the BVHs of all its parents up to the root. Like the previous issue, with some duct tape and glue this can be deferred until needed. The disadvantage of BVHs vs. spatial partitioning is that in spatial partitioning a point query will only ever need to visit one child of a given node, since no spatial overlap is possible between children. Conversely it is very likely that the BVHs of children in a scenegraph will overlap requiring the query to visit multiple children at a given level.
Taking these last two issues together notice that when a node is modified that all of it children’s information is now dirty and well as all of its parents.
These are only a couple of examples of glaring faults of scenegraphs as a world database. The duct tape and glue to lower the cost of those problems above significantly complicate an already complicated codebase as well as increase the required memory footprint. And one goes to all of this hassle to have a world database that’s good at representing a ridged body system. What’s the last 3D game you played that looked like a rigid body system? In practice it seems that a lot of systems that use scenegraphs end up with most nodes directly off the root. This means that you’re really using a very complicated implemenation of a linked list.
A common complaint made against scenegraphs is rendering related (changing textures, states, shaders, etc). Here I have no problem. I advice using spatial partitioning techniques for world databases which suffer from the exact same problem. Besides if one is performing any “modern” rendering methods, a rendering queue is pretty much required.
However, there is a common thing in games that “do” have something in common with ridged bodies: articulated models and character animation. Scenegraph like systems are work well at the model level since the above issues are moot and the data structure actually matches what is being modeled.
But, WRT the original post - there’s nothing inherently wrong or daft about using scenegraphs for games at all I don’t think: using the