DarkRadiant scene graph

From Dark Wiki

The DarkRadiant scene graph is the central data structure used by DarkRadiant to store entities, brushes, patches and other information relating to a Doom 3 map. The scene graph takes the form of a multilevel n-tree consisting of node objects, each of which is castable via C++'s dynamic_cast) to a number of different Abstract Base Classes depending on what the node represents.

The scene graph interface is defined in include/iscenegraph.h. As of June 2007, the implementing module is part of the main Radiant binary and contained in radiant/scenegraph/CompiledGraph.cpp.

Scene graph structure

An instance basically represents the location of a particular node in the graph. There are no separate Instance classes in the code.

The scene graph consists of a tree with three levels.

• Root. The single toplevel node, under which all entities are added as children (implemented by the RootNode class).
• Entities. A Doom 3 map is made up of entities, such as lights, func_statics, items, AI and the more fundamental worldspawn entity which contains all of the map geometry. All entities are immediate children of the scene graph root; entities cannot be children of other entities. Entities maintain a list of text key/value pairs, controlling aspects of their behaviour; at the very least all entities should have a unique name, a valid classname and usually an origin in 3D space.
• Primitives. Brushes and patches are examples of primitives, which make up the basic geometry of the map. Every primitive must be a child of an entity, which in most cases is the worldspawn but may also be a brush-containing entity type such as func_static or various mover types.

Path

The "depth" of the scenegraph object is never larger than 3. Each scenegraph instance holds information about its location in the graph in form of its scene::Path. The path object is a stack-type data structure holding all the node references (boost::shared_ptr<INode>) of its ancestors and itself. For example, a worlspawn patch holds a path with three pointers to three nodes (path.size() == 3):

1. PatchNode => path.top()
2. Doom3GroupNode => path.parent()
3. Map RootNode

With this path, an instance can be looked up in the scenegraph by calling findInstance(scene::Path& path). The path class is defined in include/ipath.h.

Nodes and instances

As previously mentioned, the scene graph is made up of Nodes (some of them are container objects (Traversable), but not all of them), castable to a number of abstract types depending on their content. Nodes are allocated using boost::shared_ptr<>, non-referenced nodes are removed automatically from the heap.

There is also another data structure -- the Instance -- which holds a complete path from the root to a particular child node (outlined in red on the diagram) and other information about its ancestors. (It also provides a couple of callbacks, which are not very easy to overview.) Each primitive is therefore both a Node and an Instance at the same time, but while the Node containing a primitive will not change unless it is destroyed, the Instance will change if the primitive is reparented to a different entity. Like Nodes, Instance objects can be cast to a number of abstract base types depending on their contents. Note that the instantiation of nodes can be deferred; during map load, all the nodes are created and initialised, but the actual instances are only created upon insertion of the entity as child of MapRoot.

The reason for the distinction between Nodes and Instances is that theoretically a node may have more than one parent (the scene graph is a Directed Acyclic Graph, not strictly a tree), in which case referring to the Node alone would not be sufficient to determine the parent. For Doom 3 maps however, all Nodes have a single parent.

Traversing the scene graph

The scene graph can be traversed in depth-first fashion, by passing an instance of scene::graph::Walker to the global scenegraph's traverse() function. A Walker object must define two methods:

virtual bool pre(const Path& path, Instance& instance) const

Called before descending to the children of the current Instance. Since only Entities can have children, the Instance in this case will be an Entity. By returning false in this function, the descent can be interrupted and children of the instance will not be traversed.

virtual void post(const Path& path, Instance& instance) const

Called after all children of the current Instance are traversed. Typically this will be used to "pop" any internal stack objects that were "pushed" during the initial descent.