Jump to content
The Dark Mod Forums
Sign in to follow this  
OrbWeaver

Scenegraph

Recommended Posts

Business requirements

 

Here are my initial suggestions for requirements for the scenegraph. Hopefully these should capture the required behaviour, but there may be others which need to be added.

 

The scenegraph MUST:

 

• Accept entity and primitive information from a MAP file in any order, building up the graph incrementally without excessive pre or post-processing, or memory usage.

• Support all of the parent-child relationships imposed by the Doom 3 map format, i.e. all entities are children of the root, all primitives are children of exactly one entity.

• Obey the standard concept of a scene graph, whereby a child node inherits all of the transformations (scale, rotation and translation) of its parent before applying any transformations of its own.

 

The scenegraph SHOULD:

 

• Allow full traversal of the entire tree in the fastest time possible.

• Facilitate lookups of particular names of classes of entities, as occasionally required by other Radiant code, without searching through the entire tree.

• Use spatial information to accelerate rendering, by efficiently culling entities which cannot possibly participate in the rendered scene.

 

The scenegraph MAY:

 

• Provide objects to the map export plugin in such an order that subsequent loading by DarkRadiant will be more efficient, provided that this is consistent with the requirements of Doom 3.

• Allow more complex parent-child relationships than the Doom 3 map format, provided that they can quickly be collapsed into the Doom 3 map format during export.

• Validate links between entities, by converting the text name destinations in "target", "bind" and other keyvalues into code-level references to other entities, allowing detection of broken links and quick lookup of the link destination.

 

The current GtkRadiant scenegraph implementation satisfies the MUST requirements but falls short on the SHOULD requirements. The MAY requirements should only be implemented if they provide some benefit.

Share this post


Link to post
Share on other sites

The one thing thats springs my mind is layering, which we should take into account somehow. The problem of how to save the layers has to be adressed. (Maybe by taking the entity/primitive number as reference?)

Share this post


Link to post
Share on other sites

Layering will certainly need to be taken into account when we define the interfaces, I imagine a LayeredObject interface with setLayer() and getLayer() methods ought to do the trick.

 

I propose that we use polymorphism and multiple interfaces in a similar way to the current scene graph, except simpler. For instance, everything will be a Node, and the Instance stuff will be removed (with necessary functionlity being migrated onto Node, obviously). Nodes can then be cast into more specific interfaces (LayeredObject, Entity etc) just as they are now.

Share this post


Link to post
Share on other sites

Yes, joining the Instances/Nodes is also a good idea IMO - the advantage of having a single model node (for example) with multiple instances just makes the overall design more complicated. The intention may be well, but it's not worth the effort. Just make everything a node and that's it.

 

I could imagine that in the end everything is a LayeredObject? Maybe the dynamic_cast calls could be saved if we impose the layering interface on every Node?

 

At least we need an isVisible() method on each Node, which can be used by the Scenegraph without casting anything.

Share this post


Link to post
Share on other sites
Yes, joining the Instances/Nodes is also a good idea IMO - the advantage of having a single model node (for example) with multiple instances just makes the overall design more complicated. The intention may be well, but it's not worth the effort. Just make everything a node and that's it.

 

Indeed. Note that we can still have multiple model Nodes that refer to the same model object itself, so the instantiation is still happening; the Node/Instance distinction seems to provide no value whatsoever as far as I can make out.

 

I could imagine that in the end everything is a LayeredObject? Maybe the dynamic_cast calls could be saved if we impose the layering interface on every Node?

At least we need an isVisible() method on each Node, which can be used by the Scenegraph without casting anything.

 

So we will assume that all nodes are part of a layer and all nodes can participate in filtering? I think this is probably reasonable.

 

EDIT: Perhaps we also want all nodes to return an AABB? The Wikipedia article on scenegraphs mentions Bounding Volume Hierarchies (BVH) which can work by associating a bounding volume of each node, which is defined to include the bounding volumes of all the node's children.

Share this post


Link to post
Share on other sites
• Use spatial information to accelerate rendering, by efficiently culling entities which cannot possibly participate in the rendered scene.

Speaking of spatial information. I assume the SelectionSystem might want to query the scenegraph quite often to check for selections (by point or by rectangle). How do we cover this efficiently? It's probably best to let the scenegraph handle the traversal based on arguments passed by the SelectionSystem, as the scenegraph is the only competence when it comes to traversal. À la void traverseSubgraph(const AABB& targetArea)?

 

Of course, the camera window selections can't be described with an AABB very well, so I guess we will need something better here. Maybe something along the void traverseSubgraph(SpatialTest& evaluator)? The evaluator class provides a bool testIfSuitable(const AABB& aabb) method which can be used by the SceneGraph to evaluate whether the Node comes into question.

 

edit: Just saw your edit: Yes, the Nodes will need to carry an AABB. This is currently provided by the scene::Instance, and this functionality definitely must be merged with the Nodes.

Share this post


Link to post
Share on other sites

The selection system does present some complications, it is true. We probably need to start by considering what the role of the selection system should be, since I suspect that at the moment it tries to do too much.

 

I think the selection system should:

 

1. Maintain a set of currently-selected objects (i.e. pointers to Nodes).

2. Listen to the Event Manager for selection-related events (e.g. click, click-drag, ESC, shift-click etc), and update the set of selected objects accordingly.

3. Listen to the scene graph for information about nodes which are added or removed, e.g. if a selected object is deleted this needs to be removed from the set.

4. Provide query and enumeration functionality to the rest of the application regarding which objects are currently selected.

 

Regarding the spatial information, I wonder if a suitable way to achieve this is to take advantage of the fact that our scenegraph can contain more complex hierarchies than the raw MAP format, by adding an extra layer of Nodes underneath the root which represent areas in space (remembering that as a BVH, the AABB of these special nodes will contain all of the objects underneath them). These area nodes would have to be created automatically based on the positioning of objects, and would be used during traversal to quickly skip over sections of the scene which were not in the current view.

 

Your observation that camera windows cannot use AABBs is correct, but note that they can be represented with a capped frustum instead. The maths for this would be a little more complex but not unmanageable (I hope); instead of calculating whether an area node AABB intersects the view AABB, you would calculate whether it intersects the camera frustum.

Share this post


Link to post
Share on other sites
1. Maintain a set of currently-selected objects (i.e. pointers to Nodes).

2. Listen to the Event Manager for selection-related events (e.g. click, click-drag, ESC, shift-click etc), and update the set of selected objects accordingly.

3. Listen to the scene graph for information about nodes which are added or removed, e.g. if a selected object is deleted this needs to be removed from the set.

4. Provide query and enumeration functionality to the rest of the application regarding which objects are currently selected.

I agree with all of those, that's more or less what the current SelectionSystem does - this works quite well.

 

Regarding the spatial information, I wonder if a suitable way to achieve this is to take advantage of the fact that our scenegraph can contain more complex hierarchies than the raw MAP format, by adding an extra layer of Nodes underneath the root which represent areas in space (remembering that as a BVH, the AABB of these special nodes will contain all of the objects underneath them). These area nodes would have to be created automatically based on the positioning of objects, and would be used during traversal to quickly skip over sections of the scene which were not in the current view.

I think this approach is ok for a large heap of static objects (like the compiled level in Doom3), but for the editor this can cause problems when objects are overlapping between two spatial areas or change their position/orientation during transformations. Always keeping the spatial sorting up to date will probably spoil all the advantage for us. The Nodes should just keep their AABB up to date, I'd say.

 

Or we find a fast way of resorting objects after transformations. If this is fast enough, it could work.

 

Your observation that camera windows cannot use AABBs is correct, but note that they can be represented with a capped frustum instead. The maths for this would be a little more complex but not unmanageable (I hope); instead of calculating whether an area node AABB intersects the view AABB, you would calculate whether it intersects the camera frustum.

Yes, view frustum culling should definitely be implemented. I know how to calculate the mentioned intersections, so this is no problem.

 

To keep the Scenegraph flexible, I still suggest passing some sort of SpatialTest& evaluator, which basically is what the current VolumeTest class is about. The CameraWindow and XYWindows can pass its VolumeTest classes to the SelectionSystem on incoming clicks, like it's currently done - the idea is not bad and the system is flexible, so I'd vote for keeping that idea, but of course using a better nomenclature and better code cleanliness. The Scenegraph could then easily traverse a subset of its nodes by using the passed VolumeTest evaluator to filter out the unwanted nodes.

Share this post


Link to post
Share on other sites
I think this approach is ok for a large heap of static objects (like the compiled level in Doom3), but for the editor this can cause problems when objects are overlapping between two spatial areas or change their position/orientation during transformations. Always keeping the spatial sorting up to date will probably spoil all the advantage for us. The Nodes should just keep their AABB up to date, I'd say.

 

Yes, you are probably right. For efficient processing a full-blown spatial partitioning system would probably be required (I think Namespace suggested something like this).

 

To keep the Scenegraph flexible, I still suggest passing some sort of SpatialTest& evaluator, which basically is what the current VolumeTest class is about. The CameraWindow and XYWindows can pass its VolumeTest classes to the SelectionSystem on incoming clicks, like it's currently done - the idea is not bad and the system is flexible, so I'd vote for keeping that idea, but of course using a better nomenclature and better code cleanliness. The Scenegraph could then easily traverse a subset of its nodes by using the passed VolumeTest evaluator to filter out the unwanted nodes.

 

Yes, I'm happy with the VolumeTest design as well (surprisingly for GtkRadiant). It is a good way of using double dispatch to separate interface from implementation ("You don't know anything about me, but here are some methods you can call to test parts of yourself against my volume").

Share this post


Link to post
Share on other sites

First draft of interfaces

 

Based on the above, here is my first attempt at the Node interface.

 

class Node {
public:

/**
 * Return the filtered state of this node. Returns true if the node is
 * hidden due to filtering, and false if it is visible.
 */
virtual bool isFiltered() const = 0;

/**
 * Set the layer of which this node is a member. Layers can be labelled
 * with any arbitrary string.
 */
virtual void setLayer(const std::string& layer) = 0;

/**
 * Return the layer to which this node is assigned.
 */
virtual std::string getLayer() const = 0;

/**
 * Perform depth-first traversal starting at this node. The NodeVisitor will
 * visit this node then all of its children.
 */
virtual void traverse(NodeVisitor& visitor) = 0;
};

/**
* Visitor for traversing nodes.
*/
class NodeVisitor {
public:

/**
 * Pre-descent function. Called before the children of the current node are
 * visited. Returns true if the children should be visited, false to
 * interrupt the descent and avoid visiting children.
 */
virtual bool pre(Node& node) = 0;

/**
 * Post-descent function. Called after the children of the current node are
 * visited.
 */
virtual void post(Node& node) = 0;
};

 

The differences from the current scenegraph interface (apart from the lack of a separate Instance interface) is that all Nodes can be filtered and layered, and all nodes are traversable (there is no TraversableNode interface). Nodes which do not have any children will simply visit themselves when traversed.

 

I'm not entirely sure about passing non-const references to the NodeVisitor -- is it likely that a visitor will need to update nodes during its traversal?

 

If I'm not mistaken, this is pretty much all we need for a basic scenegraph (it is just a tree after all), the question is now how best to perform the spatial partitioning for performance.

Share this post


Link to post
Share on other sites

Do we want to delegate the traverse() method to the nodes themselves? Isn't this the competence of the Scenegraph itself, à la:

void SceneGraph::traverse(const NodePtr& startingNode, Visitor& nodeVisitor) = 0;

Otherwise the Nodes would need to know how the scenegraph is built.

 

Also, is it wise to index the layers by std::string? I fear that this might decrease the performance when drawing layers, or updating the information. I'd rather have this replaced by an integer, which would also make it possible to assign a Node to multiple layers (probably managed by bitflags).

Share this post


Link to post
Share on other sites
Do we want to delegate the traverse() method to the nodes themselves? Isn't this the competence of the Scenegraph itself, à la:

void SceneGraph::traverse(const NodePtr& startingNode, Visitor& nodeVisitor) = 0;

Otherwise the Nodes would need to know how the scenegraph is built.

 

I'm not sure that's a bad thing though -- in this case the "scenegraph itself" would just be the root node plus some metadata. It it true that nodes have to manage their own children, but this makes sense IMO because some nodes might handle children differently (i.e. some won't actually have children, others might have exactly one child, others multiple children). Trying to use a separate scenegraph class to manage all of the child relationships would seem to me a recipe for complexity.

 

One other problem with SceneGraph::traverse() is that it doesn't immediately provide good performance when you have a Node and want to traverse its children: you would need to hold some kind of hashmap of Nodes as well as the tree structure in order to lookup a given Node efficiently.

 

Also, is it wise to index the layers by std::string? I fear that this might decrease the performance when drawing layers, or updating the information. I'd rather have this replaced by an integer, which would also make it possible to assign a Node to multiple layers (probably managed by bitflags).

 

I'm unsure of the best layer implementation at this point: it is possible that bitmasks would provide greater performance but they would also limit the number of layers (32 layers only, ugh!). I think the usual way to handle layers is to have a separate subgraph for each layer, which can be traversed independently, but I doubt this would work in our case (and wouldn't be very fast when we want to render by lightvolume).

Share this post


Link to post
Share on other sites
I'm not sure that's a bad thing though -- in this case the "scenegraph itself" would just be the root node plus some metadata. It it true that nodes have to manage their own children, but this makes sense IMO because some nodes might handle children differently (i.e. some won't actually have children, others might have exactly one child, others multiple children). Trying to use a separate scenegraph class to manage all of the child relationships would seem to me a recipe for complexity.

 

One other problem with SceneGraph::traverse() is that it doesn't immediately provide good performance when you have a Node and want to traverse its children: you would need to hold some kind of hashmap of Nodes as well as the tree structure in order to lookup a given Node efficiently.

I see your point. The child relationships should not be handled by the scenegraph, but still I don't think that we will do without a separate scenegraph manager standing over all the nodes. I was thinking about this:

• Facilitate lookups of particular names of classes of entities, as occasionally required by other Radiant code, without searching through the entire tree.

How are we going to tackle this if nobody but the nodes themselves knows about their nature? I assume we need some class that has the overview over all the nodes in the scene, otherwise we will end up with a lot of traversals, I guess there will be quite some lookup tables involved, ideally speeding up the process (lookup for lights, entities, brushes, etc.).

 

On a related note: Will we need scene::Paths?

 

I'm unsure of the best layer implementation at this point: it is possible that bitmasks would provide greater performance but they would also limit the number of layers (32 layers only, ugh!). I think the usual way to handle layers is to have a separate subgraph for each layer, which can be traversed independently, but I doubt this would work in our case (and wouldn't be very fast when we want to render by lightvolume).

Aren't 32 layers enough? :unsure: I'm not sure either what's the best thing here, but I'd like to keep the door open for multi-layer assignments somehow, if it's easy enough. It works quite well in Blender, so I can see some usefulness here.

Share this post


Link to post
Share on other sites
I see your point. The child relationships should not be handled by the scenegraph, but still I don't think that we will do without a separate scenegraph manager standing over all the nodes. I was thinking about this:

 

How are we going to tackle this if nobody but the nodes themselves knows about their nature? I assume we need some class that has the overview over all the nodes in the scene, otherwise we will end up with a lot of traversals, I guess there will be quite some lookup tables involved, ideally speeding up the process (lookup for lights, entities, brushes, etc.).

 

You are right on both counts, there will need to be a scenegraph manager owning the root node, and other lookup tables will be required. I would just rather not make the scenegraph owner responsible for maintaining the child relationships as well.

 

On a related note: Will we need scene::Paths?

 

I hope not; the Node should provide the information required (and possibly its parent if it is a brush node). However I can't say for sure whether a path-like data structure might be required down the line.

 

Aren't 32 layers enough? :unsure: I'm not sure either what's the best thing here, but I'd like to keep the door open for multi-layer assignments somehow, if it's easy enough. It works quite well in Blender, so I can see some usefulness here.

 

All hard limits are evil; I can well imagine mappers wanting to partition their map into a large number of layers (north hallway, master bedroom, south garden etc). Maybe these are conceptually more like the named groups that T3Ed provided than Blender's layers.

 

Multiple layers might certainly be useful, I guess in this case the methods would need to be addToLayer(), removeFromLayer() and getLayers().

Share this post


Link to post
Share on other sites

Yes, this sounds good.

 

As for the Node's properties and methods. Do we want to make it one "large" class defining all the basic methods or do we want to split it in parts, like this:

class Cullable;

class Filterable;

class Layerable;

class Whatever;

 

class Node :

public Cullable,

public Filterable,

public Layerable,

...

{};

 

I'd rather prefer splitting the Node interface into parts.

Share this post


Link to post
Share on other sites
I'd rather prefer splitting the Node interface into parts.

 

That is precisely what I was going to do, but I think you raised concerns about the performance if you had to perform a dynamic_cast in order to check filter or layer status. Thinking about it more, this should not be a problem if Node inherits all of these interfaces, because there is no need to dynamic_cast if the Node interface itself is a sub-interface of all of the others.

 

So yeah, this is a good idea.

Share this post


Link to post
Share on other sites

Should we release the 0.9.3 version before we start working on that? This might take a while.

Share this post


Link to post
Share on other sites

Ah yes, I forgot about this...I don't see a problem with a 0.9.3 release. What user-visible changes do we have since 0.9.2? All I can really remember is the modulesystem refactor which is obviously not user-visible.

Share this post


Link to post
Share on other sites

I fixed a few bugs since the modulesystem refactor (a few of them caused by the refactor itself ;)): http://bugs.angua.at/changelog_page.php

 

My second thought was that a release would make it easier to find any remaining issues caused by the modulesystem redesign. I think it's pretty stable, but at the moment it was only tested by angua, you and me.

Share this post


Link to post
Share on other sites
Ah yes, I forgot about this...I don't see a problem with a 0.9.3 release. What user-visible changes do we have since 0.9.2? All I can really remember is the modulesystem refactor which is obviously not user-visible.

 

Re-organizing entities display list in DarkRadiant. But please give me a day or two to complete it. :)

 

In similiar news, the light also need such an re-org, it is bloody impossible to find a light texture/shader in the list now since you never can guess from their name what they actually do/look like and wether they are from doom or TDM :) One more entry for my todo I guess :)


"The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man." -- George Bernard Shaw (1856 - 1950)

 

"Remember: If the game lets you do it, it's not cheating." -- Xarax

Share this post


Link to post
Share on other sites
Re-organizing entities display list in DarkRadiant. But please give me a day or two to complete it. :)

 

In similiar news, the light also need such an re-org, it is bloody impossible to find a light texture/shader in the list now since you never can guess from their name what they actually do/look like and wether they are from doom or TDM :) One more entry for my todo I guess :)

 

Aren't the display lists being reorganized in the def files of the main mod? That doesn't affect Dark Radiant.

 

Actually, I'm a bit confused Tels. :) I brought you on board to work on Dark Radiant, but you've been working on The Dark Mod instead. Not that this is a bad thing, we can use the help there too, but I just wanted to make sure you realize these are two separate projects. :) It seems to confuse a lot of people. lol

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...