# non-rendered nodes in scene-graph

This topic is 5466 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

In my scene-graph I use a base class called SceneNode, with two virtual functions Update() and Render(). All nodes are derived from this and just fill in functionality. A MeshObject node updates the mesh resource and animation step in Update() and then issues the buffer to the rendering queue using Render(). My question is what do I do in Render() for nodes that don't render anything, like a switch node, a bounding volume node or an action/event handling node? I could just have it empty but then what would these nodes do at rendertime? Alternatively I could re-arrange my class hierarchy structure. How does anyone else get around this? Does my scene-graph structure need a re-think now that I have got more complex structures being implemented - or is this a common problem and there is a pretty decent solution? Thanx

##### Share on other sites
I'd say this depends alot on how complex your scenes are. Are you planning on using any sort of hierarchical culling system?

Anyway, this is the way they do it in the OpenGL Game Programming book, by Hawkins, Astle and LaMothe... But the game they end up with is very simple, and might not be what you want.

It's perfectly okay to leave the render function emtpy. If it doesn't need to do anything at render time, then it won't. But your bounding node, for example, would be the parent of your mesh. Then, when traversing the tree at render-time, you would perform culling on the bounding volume nodes, and if the node is within the camera frustum, traverse further to the node containing the mesh itself.

On the other hand, the scene-graph should represent game-object relationships, and not geometry data. Therefore, I suggest you build an entirely different structure containing the data needed to render your scene. The scene-graph then has nothing to do with rendering at all. It's just a hierarchical representation of objects. Update the entities in your scenegraph every frame, and perform physics/collision detection, then traverse the second tree/structure and render your scene.

##### Share on other sites
I would say do a little re-thinking on it, scene graphs are typically manifestations of the composite design pattern, the main elements of the composite pattern and there relation to scene graphs are:
 Composite Pattern  |  scene graph ---------------------------------     component      |    node           Leaf         |    Leaf     Composite      |    Group

Composite composes leafs & other composites there for Groups contain nodes which are either Leafs or Groups. This creates a tree structure. If you permit nodes to have more than one parent so you can share nodes then this becomes a directed acyclic graph (DAG) this can be unmanageable so usually if you wont share nodes its generally prefered to restrict sharing of leaf nodes only.

Node, leaf, and group are abstract types tradionally things like geometry, textures, materials would derive from leaf and switching nodes, transform nodes etc would be sub-types of group because you wont it to effect the children it contains.

I think now modern scene graphs tend to take out things like geometry, textures, & materials from the main structure of the scene graph so instead of these being leafs, leafs reference these instead so you can share them among leafs, this is like applying the flyweight pattern these are extrinsic state of the scene graph (i think thats correct!?! someone please correct me).

So modern scene graph structures are mainly to implement a kind of bounding volume hierarchy (BVH) (and yes you can have a bounding leaf aswell as) & a transformation tree nicely under one uniform interface, the abstract type node will contain a bounds type that gets inherited by leafs & groups thus instantly setting up the structure for BVH, transformation tree happens by deriving from Group thus you have a transform group.

Now getting to your problem things like render and update shouldn't really be part of the interface of the scene graph in my opinion i believe you'll wont a Renderer type that iterates/visits the scene graph in an in-depth traversal of the tree. It will typically begin at the root as it travels down first it does a trivial rejection with view frustum, if the bounding volume of the node is contained in the view frustum it continues downwards concatenating any transformations it incounters, as it approaches leafs it asks for any gemeorty & any appearance attributes it may reference, accumlates render state into a renderer queue for sorting then/later. When it reaches the most bottom child it will begin to traverse upwards this time re-computing bounds that have become invalidated.

The renderer could iterate the scene graph more than once per frame doing other things you wont. Also you can have more than one scene graph aswell.

Now with update methods, perhaps something like a Contoller type that maintains an alpha value & can be attached to nodes to update.

You can also implement behvaiours, sounds & aural attributes to be part of/referenced by scene graph for a spatial sound system, regions of influence, LOD nodes list is endless.

If i have anything wrong or missing something here please correct me, people tend to implement scene graphs in all kinds of ways.

[Edited by - snk_kid on September 29, 2004 4:29:01 AM]

##### Share on other sites
wow, snk_kid, that was really detailed :)

I still have some questions and thoughts:

1)
Quote:
 Now with update methods, perhaps something like a Contoller type that maintains an alpha value & can be attached to nodes to update.

Are you refering to some method to attach some kind of affector class instance that will update the nodes? Or the Controller type will maintain pointers to the nodes that need to be updated. Either method would remove the problem of attempting to update nodes that dont need to be.

2) When the renderer traverses the tree and..
Quote:
 asks for any gemeorty & any appearance attributes it may reference
isnt this similar to what I said? In more detail: When my current Render() function is called in the traversal it returns a RenderOperation which contains a vertex buffer, index buffer and required render states - All the render operations are sorted in the render queue instantly (as they are added) and then each render operation is passed onto the API interface class.

At the moment I'm happy with geometry being part of the scene-graph, geometry is derived from SmartObject that allows it to be referenced by SmartPtr, a pointer class that is responsible for releasing memory automatically. A MeshObject node actually maintains a SmartPtr to both the mesh resource and appearance attributes, this allowing the mesh and the appearances to be shared between different MeshObjects (the flyweight pattern?)

##### Share on other sites
Quote:
Original post by dmatter
wow, snk_kid, that was really detailed :)

I still have some questions and thoughts:

1)
Quote:
 Now with update methods, perhaps something like a Contoller type that maintains an alpha value & can be attached to nodes to update.

Are you refering to some method to attach some kind of affector class instance that will update the nodes? Or the Controller type will maintain pointers to the nodes that need to be updated. Either method would remove the problem of attempting to update nodes that dont need to be.

Yeah something like, heh thats another name "affector", lets take an example you have a type called transform group which is a sub-type of Group and maintains a transformation/4-by-4 matrix type to apply to children, you wont to be able to effect transformations over time so lets say you have "RigidBodyInterloper" this can be a sub-type of leaf and maintains a reference to transform group, one of its constructors has an arguement to pass a pointer/smart pointer to a transform group, this will effect the transformation matrix of the transform group over-time.

Quote:
Original post by dmatter
2) When the renderer traverses the tree and..
Quote:
 asks for any gemeorty & any appearance attributes it may reference
isnt this similar to what I said? In more detail: When my current Render() function is called in the traversal it returns a RenderOperation which contains a vertex buffer, index buffer and required render states - All the render operations are sorted in the render queue instantly (as they are added) and then each render operation is passed onto the API interface class.

The things is like you where saying your having problems of your render memeber function being distributed/endowed to all types, if wonted it to keep it this well for sub-types where it doesn't make sense for them to render you just override/implement it to do nothing.

##### Share on other sites
Quote:
 Yeah something like, heh thats another name "affector", lets take an example you have a type called transform group which is a sub-type of Group and maintains a transformation/4-by-4 matrix type to apply to children, you wont to be able to effect transformations over time so lets say you have "RigidBodyInterloper" this can be a sub-type of leaf and maintains a reference to transform group, one of its constructors has an arguement to pass a pointer/smart pointer to a transform group, this will effect the transformation matrix of the transform group over-time.

Would this involve making the RigidBodyInterpoler a friend of the transform group? (assuming the matrix is a private/protected member). I have nothing against using friends but doesnt it indicate that its not truly OOP and thus a better solution is available? I think its a cool idea though - OOP or not.

As for rendering.. first off I should probably should renaim my Render() function to something more suitable like GetRenderOp() but thats just a name.
If I implemented the Render() to nothing ( ie {} or {return;} ) then how would hte node work? For example a switch node needs to select a single branch to iterate down, it could do this in Update() but how would it direct the traversal down the selected branch and when would it do it? Its not just a switch node that I have problems with, basically any non-renderable node, leaving the Render() empty only means they dont do anything at rendertime, further more a soundFx node might want an implementation at rendertime but its render function would be returning a RenderOperation to send to the render queue, a sound needs to go to the sound manager.

I could conclude that a Render() function should not be implemented in a base class because it is too specific to renderable nodes, but Update() is non-specific and at some point most (if not all) object must be updated so it could be implemented (unless the "affector" style update method is used or the nodes are flagged as 'old' and an UpdateManager is responsible for keeping track of these old nodes and updating them).
However without a Render() function I cant think how to retrieve a RenderOperation from renderable nodes and it doesn't help me with getting non-renderable nodes to work either.

I'm at a loss with this and I could do with some help :)

##### Share on other sites
Quote:
 Original post by snk_kidI would say do a little re-thinking on it, scene graphs are typically manifestations of the composite design pattern, the main elements of the composite pattern and there relation to scene graphs are: Composite Pattern | scene graph --------------------------------- component | node Leaf | Leaf Composite | GroupComposite composes leafs & other composites there for Groups contain nodes which are either Leafs or Groups. This creates a tree structure. If you permit nodes to have more than one parent so you can share nodes then this becomes a directed acyclic graph (DAG) this can be unmanageable so usually if you wont share nodes its generally prefered to restrict sharing of leaf nodes only....

That's exactly what I use. I have scenegraph which contains nodes. Each functionality required for nodes is acquired via ScenegraphPlugins although Visitor pattern would be more suitable. Only method for my SceneNode class is Serialize.

##### Share on other sites
Quote:
 Original post by dmatterWould this involve making the RigidBodyInterpoler a friend of the transform group? (assuming the matrix is a private/protected member). I have nothing against using friends but doesnt it indicate that its not truly OOP and thus a better solution is available? I think its a cool idea though - OOP or not.

doesn't have to be and i don't think it should be a friend, RigidBodyInterloper would ask transform group for it's transform to manipulate, take this very incomplete probably non-compilable example but should give you an idea:

#include <boost\pool\pool_alloc.hpp>#include <boost\smart_ptr.hpp>#include <list>namespace scenegraph {//abstract type, we could have bounding spheres, boxes etc.template < typename T >class bounds {  /*....*/public:  /*....*/  virtual bool intersects(const bounds&) const = 0;  virtual ~bounds() {}  /*....*/};template < typename T > struct matrix4 { /* ... */ };class transform3d {   /*....*/   matrix4<float> m;   /*....*/};//abstract type non instancableclass node {  /*....*/  boost::scoped_ptr<bounds> _bounds;  /*....*/public:  static const transform3d IDENTITY;  /*....*/  // default does nothing but return the identity matrix for now  virtual const transform3d& transform() const {      return IDENTITY;  }  // default does nothing  virtual const node& transform(const transform3d& t) {      return *this;  }    /*....*/    virtual ~node() {}};//abstract type non instancableclass group : public node {public:   typedef boost::shared_ptr<node>               node_ptr;   typedef boost::pool_allocator< node_ptr >     node_ptr_alloc;   typedef std::list< node_ptr, node_ptr_alloc > node_list;   /*....*/private:   /*....*/   node_list kids;   /*....*/public:  /*....*/  virtual ~group() {}};//abstract type non instancableclass leaf : public node { /*....*/ };//concrete type, inherit's child listclass transform_group : public group {   /* ... */   transform3d _trans;   /* ... */public:  /* ... */  const transform3d& transform() const {      return _trans;  }  const node& transform(const transform3d& t) {      _trans = t;      return *this;  }  /*....*/};//concreateclass RigidBodyInterloper : public leaf {  transform_group& _transg_ref;  /* ... */  RigidBodyInterloper(transform_group& trans, float alpha)  : _transg_ref(trans) ,/*....*/ {}  RigidBodyInterloper& update(float delta) {     transform3d&  t = _transg_ref.transform();     /* ...to do... */     return *this;  }  /* ... */}; };

"begin rant..."
As far as i'm concernd the so called "pure" OOP methodology is no panacea and nor is any other, it isn't very useful in isolation & it would be to restrictive & limiting on its own besides same goes with any other methodology.

But when a programming langauges supports multiple disciplines the world becomes your oyster, and you can really have your cake & eat too...
"end rant..."

##### Share on other sites
snk_kid, I find your design with the composite pattern/scenegraph very nice :)

I'm not 100% on how it works, just more or less.

I guess that your Nodes still need an Update() method at least?

I was hoping you could make another example with the
Controller types you mentioned:

"Now with update methods, perhaps something like a Contoller type that maintains an alpha value & can be attached to nodes to update."

That would be really nice of you :)

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 22
• 17
• 46