# Obtaining specializations from a scene graph

## Recommended Posts

How does or could one obtain specializations from a scene graph?

I currently use a TransformNode that looks something like this:

 __declspec(align(16)) struct TransformNode final
: public AlignedData< TransformNode > {

private:

friend class Node;

SharedPtr< Transform > m_transform;
Node *m_parent;
vector< SharedPtr< Node > > m_childs;

mutable XMMATRIX m_object_to_world;
mutable XMMATRIX m_world_to_object;
mutable bool m_dirty_object_to_world;
mutable bool m_dirty_world_to_object;
};

The TransformNode encapsulates a local Transform (parent <> object) as well as its positioning in a scene graph (parent and child Nodes). A Node itself is some proxy on top of a TransformNode, allowing to do node->getTransform()->SetTranslation() via an indirection instead of directly calling and polluting the node itself (e.g. node->SetTranslation()). The Node class forms the root of a hierarchy containing abstract models, lights, sprites, cameras which all have their own specializations.

Given some Node, how does one normally convert it to its specialization?

• Each node has a name, so I can search for a specific node and perform a dynamic_cast based on a template type provided by the user. Though this requires names to be globally unique or at least unique in every subtree of the scene graph.
• If all the specializations are known in advance, then a static_cast can be used instead of a dynamic_cast if some enum member specifies the specialized type.
• If all the specializations are known in advance, I can use specialized collections instead of one general collection in TransformNode.
• The scene graph can support general visitors, but this requires an expensive double dispatch as well as lots of boilerplate code for a single implementation of the visitor.

For rendering purposes, I also have some flattened collections of the scene graph: models, specialized lights, cameras and sprites. But I do not have the need to have a collection for each specialization. For the lights, I explicitly want to know the most specialized types, but for cameras I do not really care for rendering and can just work with the abstract camera interface.

##### Share on other sites

If you're considering dynamic_casts or need to convert from base to specialization, then you most likely have a fundamental design problem on your hands and are trying to do something you shouldn't be.

Do you even need to build a linked hierarchy this way, or can you give it to a higher-level construct (scene graph itself)? What is the purpose of these specializations? Do they have anything in common, can they share an interface? Is this transform node actually necessary, or are you putting in extra effort for a non-existent problem?

If the goal is to keep transform separate from the node, then just use composition and have each node contain a transform that it can then plug into the scene graph. There's no reason to use inheritance here, IMO.

Edited by Styves

##### Share on other sites

The hierarchy looks like this:

1 hour ago, Styves said:

If the goal is to keep transform separate from the node, then just use composition and have each node contain a transform that it can then plug into the scene graph. There's no reason to use inheritance here, IMO.

But what if you have child nodes? Lets say you have a perspective camera node and add an omni light node as child (or alternatively one can specify this for a transform as well), how do you obtain the omni light node given that perspective camera node?

##### Share on other sites

You don't, because that's horrid design and asking for a spaghetti mess at the end.

Tell your nodes to process themselves, and they can handle any components/children as appropriate. Your main processing can be one line of code: tell the root node to process.

This "process" might be Tick(), or NetworkSync(), or Render(), or any number of other operations.

##### Share on other sites
8 minutes ago, ApochPiQ said:

tell the root node to process

But then I have a giant number of virtual method calls. Now I have 0 virtual method calls.

Furthermore, the issue remains for scripting. You cannot retrieve any specializations if you do not have a pointer or reference directly to those specializations.

Edited by matt77hias

##### Share on other sites
31 minutes ago, ApochPiQ said:

This "process" might be Tick(), or NetworkSync(), or Render()

My Update()/FixedUpdate() is down in some script instance which needs to store all the needed nodes.

The Render() is down outside the node itself. The node only provides an interface to access the data needed for rendering.

##### Share on other sites

Sounds like you are way over complicating things.

Really opened my eyes to what it was I was wanting to do.

##### Share on other sites
37 minutes ago, Mike2343 said:

I read the article, but it still puzzles me.

My scene graphs (multiple roots are possible) are not the primary scene data structure, neither do I operate on the scene graph for rendering or frustum culling. I have flattened collections (this works for now but has a linear complexity) of nodes in my scene itself which I iterate for these purposes.

The scene graph is only used for propagation and has some general methods for doing this as well as some specialized transform related methods with dirty flags. This is similar to Unity3D's hierarchies which always contain a transform and thus transform relationships at the very least. My scene graph doesn't do any processing.

So this looks not like violations against the design of a scene graph.

This however still does not specify how that you get some component of some child. The very least a scene graph does is specify the relationships between parents and childs.

Edited by matt77hias

##### Share on other sites

I hope L.Spiro reads this one.

Why do you need to get "some component of some child" if no processing is occurring?

What exactly is your goal? What problem are you trying to solve? It's really difficult to give you a straight answer without knowing what the problem domain is.

Also, if you want to avoid virtual calls but still process the hierarchy the way ApochPiQ mentioned then just break things up into lists of specialized components (light, camera, etc) and iterate over each list separately, keeping a simple link to the node/transform if necessry. Don't over-complicate it with OOP.

For example you can sort the nodes in order of the hierarchy with parents coming first and then process them in linear order, without even leaving the current function and without the need for any virtual inheritance. Any special behavior can just be linked to the nodes in some way.

Edited by Styves

##### Share on other sites
14 minutes ago, Styves said:

Also, if you want to avoid virtual calls but still process the hierarchy the way ApochPiQ mentioned then just break things up into lists of specialized components (light, camera, etc) and iterate over each list separately, keeping a simple link to the node/transform if necessry. Don't over-complicate it with OOP.

I have similar collections in my Scene. Furthermore, I still have composition for my scene graph (difference between Node and TransformNode). I know this seems way too complex, but so far it accomplishes the things I wanted it to support.

14 minutes ago, Styves said:

What exactly is your goal? What problem are you trying to solve? It's really difficult to give you a straight answer without knowing what the problem domain is.

If I load hierarchical models with submodels, I cannot use non-root nodes to their full potential, because I cannot access them (unless I use my previous proposals). If a plane has some propeller attached to some other part, I cannot get the propellor.

For the submodel<>model specifically, I don't want to have another hierarchy. The only thing that such submodels share is just a mesh, so special treatment is overkill.

16 minutes ago, Styves said:

Why do you need to get "some component of some child" if no processing is occurring?

Scripting.

Edited by matt77hias

##### Share on other sites
14 minutes ago, matt77hias said:

If I load hierarchical models with sub models, I cannot use non-root nodes, because I cannot access them (unless I use my previous proposals). If a plane has some propeller attached to some other part, I cannot get the propellor.

I still don't understand, can you tell us what the purpose of all of this is? Why do you need to "use non-root nodes" or "get the propeller"? What is it you want to do with the nodes?

I just don't understand what it is you're trying to do with all of this. I don't have enough context to wrap my head around the problem.

Maybe I'm just missing something or misunderstanding what was written prior. In any case more information will really help.

Edited by Styves

##### Share on other sites

I'm going to try and limit the snark a bit here, but believe me, it's hard.

Matthias, what you're doing is basically reading us one page at a time of a mystery novel, and then asking us who the killer is. Except it isn't even consecutive pages, or even chronological pages. Just rip a sheet of paper out of the book at total random, read it aloud, and then see who gets the correct killer.

And you've read us only two pages so far.

We don't even know the title of the book or who the characters are. We can't help you find the killer.

##### Share on other sites

Ok. I will try to elaborate, though it is not that easy and clear for me as well. Stated differently, if the problem was 100% clear, I just solved it.

The most basic problem, I wanted to solve first is the ability to specify relative/local transformations between a parent and a child object. So I created a Transform class which only encapsulates such a single relative transformation. Next, I wanted to relate these local transformations to world space and I wanted the ability to hierarchically structure local transformations in such a way that changing a local transformation affects the world transformation of all direct and indirect children as well. So this is my scene graph. This is not some general graph describing some arbitrary node connections, but a specialized graph in the sense that a connection between two nodes is always associated with a (direct) relative transformation between those two nodes. The idea is based on the way Unity3D's editor organizes a scene: a scene can have multiple root nodes each having their own hierarchy and each node has at least a local transformation. This conceptually works for lights, cameras and models, but is less suitable for screen-space sprites since 3D transformations are not used for the latter. One still needs them, however, to be able to add child nodes to such sprites which unlike the sprites require the chain of transformation to and from world space. So I created a TransformNode class. Instances of this class constitute the scene graph. A TransformNode has a pointer to its parent node (which does not exist for root nodes) and its child nodes. Furthermore, the TransformNode contains a Transform specifying the local transformation (connection with its parent node or the world itself in case this is a root node). Since, I want to cache the transformation matrices and update them if they are dirty, child TransformNodes must be notified of changes to a Transform of one of their ancestor TransformNodes (to invalidate their matrices). Some callback mechanism can be added to the Transform class for this purpose, but this is not clean: the Transform class is finished and must be a general class that can be used as some utility in other projects as well. Furthermore, adding some listener for example results in less controllable traversals of the hierarchy. So I wrapped the Transform inside the TransformNode. This is also more convenient for the user: instead of dealing with Transforms and TransformNodes, it suffices to use the TransformNode, furthermore it is not even possible anymore to work with a Transform since this is completely hidden by the TransformNode. By wrapping the Transform, cached matrices of the descendants of a TransformNode can be invalidated in a straight forward breadth-first or depth-first traversal. Alternatively one can flush transformation matrices down the graph once per frame. The disadvantage of flushing is the inability to use the transformation matrices for scripting. My approach, however, always results in the correct and up-to-date transformations. For example: if you translate some parent model first, and then retrieve the world-to-object or object-to-world matrix of some child light, camera or model, you will get a matrix taking the re-positioning of the parent into account.

The first problem that arises, however, is what is a parent and child node for a TransformNode. It could be a TransformNode, but like I said the TransformNode (just as for a Transform) merely deals with a hierarchy of transformations. I do not want to add extra data for activating/deactivating nodes, for giving a name to a node. So instead of storing pointer to TransformNodes inside the TransformNode for constituting the hierarchy, I use some other class Node which owns a TransformNode. So implicitly, a hierarchy of TransformNodes exists though indirectly due to the Node. This has two advantages. First, I can access the TransformNode of a Node by just calling a method Node::GetTransform(),  which is cleaner and clearer than directly invoking transformation related functionality on Node itself. Second, I can use Nodes instead of TransformNodes for the propagation of data in my graph. For example: transformation matrices can be invalidated by notifying the TransformNode of each child Node, subtrees can be activated/deactivated by notifying each child Node.

The only tricky part in my Node<->TransformNode implementation is managing the hierarchy. Adding to, removing from and re-adding to a Node is supported. If Nodes are terminated (marked for deletion), the whole subtree will be terminated. If a copy constructor is invoked, a deep-copy of the whole subtree is performed and results in a new subtree (which has no connections with the previous subtree). So far we have some abstract Node class which is finished and is a general enough to be of use as some utility in other projects as well.

The Node class is derived by the SceneNode class which basically adds a name at the moment. I do not consider a human readable name some universal property of a Node, so this is not added to the Node. The SceneNode has ModelNode, CameraNode and LightNode subclass which provide functionality to add a Model, Camera and Light, respectively, which can all have their own hierarchies. For example a Camera is not the same as CameraNode. The Camera deals with the view-to-projection matrix and the camera lens. The CameraNode obviously deals with the Camera and its Transform as well as with additional fluff such as some view settings and a viewport transformation.

For the purposes of rendering, I do not work with the root Nodes or root SceneNodes but I need to distinguish Nodes till some certain specialization level and I want a fast way of iterating these. Therefore, my Scene class contains separate collections for all CameraNodes, all ModelNodes and all specializations of the LightNodes. The disadvantage of working with specialized lights, is the user's inability to define its own lights. On the other hand it is difficult to probably impossible to handle all lights in a similar fashion for a rasterizer compared to a ray tracer. Cameras on the other hand can be specialized by the user, since the Camera interface suffices to work with for rendering. So for example: I never need to distinguish between orthographic and perspective cameras and the user can define a fish eye camera himself that will be used appropriately while rendering.

For rendering purposes, I collect all active CameraNodes, ModelNodes and specialized LightNodes in some buffer which will be passed around for the different render passes. Note that I do not directly use the implicit hierarchies underneath them. There is in fact only one indirectional usage: getting the object-to-world and world-to-object transformation matrix. If one of these matrices is dirty, some child-to-ancestor propagation is possible.

But there is even another very similar problem. Lets assume we have some OBJ mesh of some windmill consisting of a base building and the blades. The mesh specifies that the blades are a child of the base building. When I perform a Scene::CreateModel(name, args), I create a ModelNode for the base building and the blades and I add the latter to the former. Both ModelNodes are added to the collections of the Scene and the root ModelNode is returned to the caller. The caller obtains a pointer to a ModelNode which has one ModelNode as a child (i.e. the blades), but how do you use the latter one? If the name is unique, I can query the ModelNode of the building and obtain a Node of the blades (this also requires the name to be present in the Node and not in the SceneNode). Since, I have a Node, I can obtain the TransformationNode and use it in some script for rotating the blades. But I do not have the ModelNode, I have a Node, so if I want to do something fancy such as changing the material, I cannot do that without casting or double dispatching (i.e. visitor).

So I hope this somehow makes a bit sense?

Edited by matt77hias

##### Share on other sites

You are massively over-complicating and over-engineering this to the point that even a huge set of paragraphs detailing it is still confusing.

3 hours ago, matt77hias said:

Stated differently, it the problem was 100% clear, I just solved it.

Now see, there's your real problem. You haven't figured out what the problem you're trying to solve is yet but you're already trying to solve it. This is a big red flag telling you to step back and break down what it is you're really trying to do.

Hint: you mentioned what you want to do in your first line of your first paragraph:

3 hours ago, matt77hias said:

The most basic problem, I wanted to solve first is the ability to specify relative/local transformations between a parent and a child object.

3 hours ago, matt77hias said:

For the purposes of rendering, I do not work with the root Nodes or root SceneNodes but I need to distinguish Nodes till some certain specialization level and I want a fast way of iterating these.

Basically what you seem to want to do want is store transformations separately from the objects in your scene so that you can propagate transformations from parents to children without having to structure the main objects in a matching hierarchy since they currently exist in flat lists for iteration purposes. As a result you need to link the transformations to their parent/children so that changes will be propagated to the child transforms and your objects need access to their corresponding transforms so they can manipulate or use them for rendering.

Hopefully I understood that correctly.

3 hours ago, matt77hias said:

The mesh specifies that the blades are a child of the base building. When I perform a Scene::CreateModel(name, args), I create a ModelNode for the base building and the blades and I add the latter to the former. Both ModelNodes are added to the collections of the Scene and the root ModelNode is returned to the caller. The caller obtains a pointer to a ModelNode which has one ModelNode as a child (i.e. the blades), but how do you use the latter one?

My first word of advice is to stop trying to literally represent your hierarchy through class/struct objects in code because it's one of the core causes of your current dilemma. Your nodes should not own their children independently. This is a violation of the single responsibility principle: your making your nodes responsible not only for their own logic but for managing their children as well.

All of your nodes should exist in the Scene Graph which has the responsibility of managing those nodes.

3 hours ago, matt77hias said:

If you want to add this Node to the scene, you probably succeed for that specific Node but what about its descendants? They need to be added to the Scene as well and they need to be added to the appropriate collection. The only way this could be achieved is by using a visitor pattern?

Stop right now if you're thinking about "visitor patterns" or other even more complicated OOP patterns as a potential solution for this problem, which itself is the result of bad design decision motivated by complicated OOP code. Moving forward with any of these patterns will only add more complexity and will cause you even more trouble in the long run. They aren't the solution to your problem.

Objects should be added to the scene at creation time when their type is known. Anything that needs the type should be done at time where the type is known.

Don't try to move from an abstract object to it's concrete form, this is usually a sign you're doing something wrong. About the only time I've ever seen this be ok is in UI code (working with Qt's qobject_cast) but even then it's rarely necessary.

3 hours ago, matt77hias said:

But I do not have the ModelNode, I have a Node, so if I want to do something fancy such as changing the material, I cannot do that without casting or double dispatching (i.e. visitor).

Why do you only have the abstract node in this case? If you need the concrete object, then get it directly in your script via something like GetModelNode(name) or something. I don't understand why you need to go through the abstract node to access it.

PS: I think you need to revise your naming scheme: what exactly is a node? You have "TransformNode" and "Node"/"ModelNode"/etc, but only one of them seems to be in this "scene graph" (TransformNode). As far as I understood your "TransformNode" is the object that is part of the hierarchy, so this owning "Node" object isn't really a node, it's just an object containing a TransformNode, right? Having two separate concepts of "Node" in the same paragraph is really adding to the confusion.

Edited by Styves

##### Share on other sites
1 hour ago, Styves said:

Basically what you seem to want to do want is store transformations separately from the objects in your scene so that you can propagate transformations from parents to children without having to structure the main objects in a matching hierarchy since they currently exist in flat lists for iteration purposes. As a result you need to link the transformations to their parent/children so that changes will be propagated to the child transforms and your objects need access to their corresponding transforms so they can manipulate or use them for rendering.

I use transforms in the following way

Here, node_ptr is of type (const) Node* and node_ptr->GetTransform() is of type (const) TransformNode*. But that is conceptually pretty much the same: it has the same expressive power. The only reason for doing this is not polluting the Node interface with all these transformation related methods. But Nodes, SceneNodes (derives Node), CameraNodes (derives SceneNode), etc. all have access to their TransformNode. So the transformation is not separate from these objects, the functionality is just moved to a member variable.

So for example: Assume we have a car having four wheels each having one neon light attached. The car ModelNode has four wheel child ModelNodes and these have one neon child OmniLightNode. The Scene has a ModelNode collection containing the car ModelNode and the four wheel ModelNodes, and an OmniLightNode collection containing the four neon OmniLightNodes.

1 hour ago, Styves said:

Objects should be added to the scene at creation time when their type is known. Anything that needs the type should be done at time where the type is known.

But what should loading a model from file do? Return a vector containing all the generated ModelNodes instead of only returning a pointer to the root ModelNode?

Edited by matt77hias

##### Share on other sites
On 11/12/2017 at 5:29 AM, matt77hias said:

SharedPtr< Transform > m_transform;
vector< SharedPtr< Node > > m_childs;

Didn't notice this on my first pass, but this smells like you're not really sure who owns the m_transform and m_childs (children?) data.  Why are these not unique_ptrs?  If anyone needs access you have the .get() accessor you can use but ownership is now explicit.

2 hours ago, matt77hias said:

But what should loading a model from file do? Return a vector containing all the generated ModelNodes instead of only returning a pointer to the root ModelNode?

A bit off subject but it will help you in the long run... To answer your question, loading a model from a file should hand you back a block of memory you specified with the data held in it for a factory or function to process, see Hodgman's May 18th post here:

I would then say, that factory/function should return a vector containing all the generated ModelNodes, yes.

##### Share on other sites
25 minutes ago, Mike2343 said:

Didn't notice this on my first pass, but this smells like you're not really sure who owns the m_transform and m_childs (children?) data.  Why are these not unique_ptrs?  If anyone needs access you have the .get() accessor you can use but ownership is now explicit.

You are right, I should rethink the Transform member of TransformNode. I remember originally doing this, since I expose my TransformNode's internals to Node (which is a friend of TransformNode), but accessing a std::unique_ptr member is fine.

The childs are shared since these Nodes could be owned by at most one TransformNode, by a Scene and by some scripts as well. The scripts could work with a raw or weak pointer as well, but my factories inside Scene return a std::shared_ptr. I do this to allow adding this std::shared_ptr to the scene graph as well. But I could make the scene the only owner. The reason I did this was to make TransformNode some general class which makes sense on its own independent of the Scene.

Edited by matt77hias

##### Share on other sites
2 hours ago, matt77hias said:

Here, node_ptr is of type (const) Node* and node_ptr->GetTransform() is of type (const) TransformNode*. But that is conceptually pretty much the same: it has the same expressive power. The only reason for doing this is not polluting the Node interface with all these transformation related methods. But Nodes, SceneNodes (derives Node), CameraNodes (derives SceneNode), etc. all have access to their TransformNode. So the transformation is not separate from these objects, the functionality is just moved to a member variable.

Your "TransformNode" is not a node then, it's an element or component of a node. Just call it a Transform.

Also I imagine each of these derived nodes live inside your Scene Graph directly as part of some abstract list, and the parent/child relationship is part of each Node. Do I have that right?

2 hours ago, matt77hias said:

But what should loading a model from file do? Return a vector containing all the generated ModelNodes instead of only returning a pointer to the root ModelNode?

What does a call to load a model look like?

##### Share on other sites
15 minutes ago, Styves said:

Your "TransformNode" is not a node then, it's an element or component of a node. Just call it a Transform.

I had already a Transform structure. So I was running out of names.

15 minutes ago, Styves said:

Also I imagine each of these derived nodes live inside your Scene Graph directly as part of some abstract list

Yes.

15 minutes ago, Styves said:

and the parent/child relationship is part of each Node.

Yes (indirectly though via the TransformNode member variable).

15 minutes ago, Styves said:

What does a call to load a model look like?

template<typename SceneNodeT , typename... ConstructorArgsT>
SharedPtr< SceneNodeT >  Create (const string &name, ConstructorArgsT &&... args)

SharedPtr< ModelNode >  CreateModel (const ModelDescriptor &desc) //returns the root

The reason I have two methods, is that the "args" are passed to the Camera/Model/Light constructor as part of the creation of a single CameraNode/ModelNode/LightNode. The ModelDescriptor, however, contains the specification for creating a complete hierarchy of ModelNodes (each having a Model).

Edited by matt77hias

## Create an account

Register a new account