# SceneGraph

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

## Recommended Posts

Hey everyone! I have been readeing numerous topics on SceneGraphs, as well as books including Eberly's. I hink I have understood the concept of haveing an abstract SceneGraph, and implementing it with the Composite pattern. The thing I do NOT understand is how the Updating of nodes is supposed to be handled?! I'll give you an example of what I mean: ->TranslationNode ---->GeometryNode ---->TranslationNode -------->GeometryNode -------->GeometryNode Ok, so thats the hierachy. And this is how I would build that: TranslationNode tNode1 = new TranslationNode(/*some translation*/); GeometryNode gNode1 = new GeometryNode(/*some geometry*/); tNode.AddChild(gNode1); TranslationNode tNode2 = new TranslationNode(/*some translation*/); GeometryNode gNode2 = new GeometryNode(/*some geometry*/); GeometryNode gNode3 = new GeometryNode(/*some geometry*/); tNode2.AddChild(gNode2); tNode2.AddChild(gNode3); tNode.AddChild(tNode2); My problem is that now that I want to change the translation in tNode1. I need to somehow update it's children to update their translations. But ONLY TranslationNode's are to be updated! And the only way I can think of solving this is by using some RTTI, which we all know is an indication of BAD DESIGN :( this is how I could think of updating the translation:
tNode1->UpdateTranslation(/*some new translation*/);
//....
tNode1::UpdateTranslation(/*some new translation*/) {
Iterator iter = new SomeIterator(this);
while(iter.hasNext()) {
TranslationNode tNode = (iter.next() as TranslationNode);
if(tNode != null) {
tNode.UpdateTranslation(/*some new translation*/);
}
}

m_translation = /*some new translation*/
};


// A very simplified version of the Node base class :)
class Node {
protected:
Node _parent;
Node[] _children;
};


I use a Node base class that each new nodetype is derived from. So the children need to be saved as Nodes :( As you see i'm using the ugly 'as' operator, which for you who don't know is a similarity to dynamic_cast in c#. So, the graph works at the cost of having the need for RTTI. Am I missing something crucial in the design of a scenegraph? Cuz I'm sure ppl somehow manage to UPDATE a TranslationNode without the need of RTTI right? Would really appreciate someone enlightening me how the hell it is done? I forgot to mention that "Modularity" is important to me. I strive to have the SceneGraph designed so that I can add new NodeTypes without having to change old code... like adding the UpdateTranslation(...) to the Node baseclass. Thank you ! (Sorry for posting in the Graphics forum, you may remove that thread:) )

##### Share on other sites
I am not quite sure about your problem but in any case you mean that when you update the translationNode1, you wanna update its children for that translation too right?

That's actually the strength of SceneGraph. Immagine you are using OpenGL commands:

(I don't remember exactly GL commands, please forgive me, but you get the idea ;)
TranslationNode1 should store a Matrix which represents the world matrix of its own and children. In your TranslationNode1->Update(), you, for example, translate it by:

glTranslate(1.0f, 1.0f, 1.0f);

This will translate the current world matrix to (1.0f, 1.0f, 1.0f), so anything that is drawn after this world matrix will be translated automatically, in which you do not have to translate every single children under this node.

Hope this is what you want.

Cheers.

##### Share on other sites
Why do you need to update the children translations? The whole point of a scenegraph is that transformations are cumulative. So if you translate tNode1 by 1,0,0, then each child of tNode1 automatically gets translated by that much as well.

##### Share on other sites
Ok, I'm sorry about the example of TranslationNode, that was really stupid :)

But still the problem does exist. Say I want to Render the a scene:

GeometryNode gNode1 = new GeometryNode();
TranslationNode tNode1 = new TranslationNode();
GeometryNode gNode2 = new GeometryNode();

RenderList renderer = new SortByEffectRenderList();
gNode1->Render(renderer);

GeometryNode::Render(RenderList renderer) {
if(renderer.IsVisible(/*current bounding volume*/)) {
}
//Now I also want to continue rendering my children
//And I don't know if my children are GeometryNode's
}

What functions should I have to execute a Render operation on a node, and
where are the functions supposed to be situated?

Is Everyone putting "standard" functions into the base classs, like:

class Node {
virtual void Render(RenderList list);
virtual BoundingVolume GetBoundingVolume();
}

What If I in the future want to add another equally complex operation as the
Render(....);

Then I would need to change the Node base class and then recompile all the
modules that are using this base class right?

##### Share on other sites
Quote:
 Original post by FxMazterGeometryNode::Render(RenderList renderer) {if(renderer.IsVisible(/*current bounding volume*/)) { renderer.AddGeometryChunk(/*some geometry data*/);}//Now I also want to continue rendering my children//And I don't know if my children are GeometryNode's}

This is a cross-post, in the other version of this thread i explained that this isn't how the composite pattern works, GeometryNode should be leaf terminal node type it doesn't deal with children, internal nodes deal with children, here is a hypothetical very simple example of what your code should sort of look like:

#include <vector>class bounding_volume { /* .... */ };class geometry { /* .... */ };//abstract class - should be non-instanceableclass Node {    friend struct Group; //forward class declaration    Group* parent_ptr;    bounding_volume worldBV;        //.....public:    //...    const bounding_volume& world_bounds() const { return worldBV; }    virtual void Render(RenderList&) const = 0;    virtual ~Node() {}};//abstract class - should be non-instanceablestruct Group : public Node {   typedef std::vector<Node*> child_list;   typedef child_list::const_iterator const_child_itr;   typedef child_list::iterator child_itr;   //....private:   child_list kids;   //....public:   //...   virtual void Render(RenderList& renderer) const {        //....       if(!renderer.cull(this->world_bounds())) { // try to cull entire branches          //....          for(const_child_itr itr = kids.begin(), end = kids.end();              itr != end;              ++itr)             (*itr)->Render(renderer);          //...       }       //...   }   //...  };class GeoNode : Node {   geometry* geo_ptr;public:   void Render(RenderList& renderer) const {       //...       if(!renderer.cull(this->world_bounds())) { // try to cull leaf          renderer.AddGeometryChunk(geo_ptr);          //...          renderer.draw(this); //just an example, take it as a grain of salt!           //...       }       //...   }};

I've made important code bold (may not be compileable) note that if other types of groups are contained in a group, Group::Render will recurse & try to cull entire branches (sub-trees) before continuing downwards to leafs and and attempting to cull them.

This is an example so it doesn't necessarily have to be 1-to-1 mapping in your code but if your basing your design on the composite pattern it should have a simillar structure.

[Edited by - snk_kid on January 7, 2005 7:42:00 AM]

##### Share on other sites
Thank you very much snk_kid, that really helped a lot :)

I see that you put the Render(...) function in the base Node class. That's
what I was trying to avoid doing :/

What I'm concerned about is how much work it will take to add a new Operation
similar to Render(...).

That would mean I would need to recompile each module using the Node class?

thx!

##### Share on other sites
Ok, with your help - snk_kid - I have decided to go for this design:

//Instead of adding functions to the Node base class//The Node base class will execute NodeOperations//Kind of like the Visitor Pattern, except I will //use RTTI to decide the type of the node - new//Node types will be allowed...class NodeOperation{    public virtual void Execute(Node node)    {    }}/*For eg. this RenderOperation takes the place ofNode::Render(RenderList renderer);*/class RenderOperation : NodeOperation{    private RenderList m_renderer;    public RenderOperation(RenderList renderer)    {        m_renderer = renderer;    }    public override void Execute(Node node)    {        GeometryNode gNode = (node as GeometryNode);        if (gNode != null)        {                                   if(m_list.cull(gNode.GetBoundingVolume())) {                m_renderer.Draw(gNode.GetGeometry());            }                        //count++;            //System.Console.WriteLine(gNode.m_name);        }    }    private uint count = 0;}//The Node base class, Instead of adding functions Like://virtual Render(RenderList renderer);//virtual GetBoundingVolume();//... and other similar functions//I will have the ExecuteOperation(NodeOperation op) function//That dispatches the operation.abstract class Node{    public virtual void ExecuteOperation(NodeOperation op)    {        op.Execute(this);    }}//The Group node, according to the Composite pattern //just a basic version :)class Group : Node{    private LinkedList<Node> m_children = new LinkedList<Node>();    public override void ExecuteOperation(NodeOperation op)    {        LinkedListNode<Node> currentChild = m_children.Head;        for (int i = 0; i < m_children.Count; ++i)        {            currentChild.Value.ExecuteOperation(op);            currentChild = currentChild.Next;        }    }    public void AddChild(Node child)    {        m_children.AddTail(new LinkedListNode<Node>(child));    }}//Transformation group, holds transformation//infoclass Trasformation : Group{    private Matrix m_transformation;    public Trasformation(Matrix someTransform)    {        m_transformation = someTransform;    }}//The GeometryNode, leaf node according to the Composite pattern//Will hold some geometry info...class GeometryNode : Node{    private Geometry m_geometry;    public GeometryNode(Geometry geo)    {        m_geometry = geo;    }    public Geometry GetGeometry()    {        return m_geometry;    }}

Unfortunately, I can't think of any way of eliminating the need for RTTI :(
Which is used in the RenderOperation::Execute(...) to check if the node
is a Geometry.

I have actually benchmarked the use of the ExecuteOperation(NodeOperation op)
vs having multiple functions Render(...) GetBoundingVolume() etc...

And in c# it made no difference in performance, even though the use of "as operator".
Of course I'm not saying that my benchmark was precice... I just executed
the RenderOperation 10000000 times...

This will give me the flexibility of adding new Operations but also new Node types, without the need of recompiling all old modules that use the Node class.

So the RenderOperation would be executed like this:

Trasformation root = new Trasformation(new Matrix(...));root.AddChild(new GeometryNode(pSomeGeometry));            Trasformation transform = new Trasformation(new Matrix(...));transform.AddChild(new GeometryNode(pSomeGeometry2));            root.AddChild(transform);/* now I want to render the nodes starting from root */RenderList list = new RenderList();RenderOperation render = new RenderOperation(list);            root.ExecuteOperation(render);

How does that seem?

Thank you for your help snk_kid, rated you as extremely helpful :) heh

##### Share on other sites
heh, i was actually in the process of coding one solution from the second from last post, i'll post something shortly then read the last reply.

##### Share on other sites
Another example of how this would work:

Lets say I want to retrieve the world translation for a GeometryNode:
class GetWorldTranslationOperation : NodeOperation{    public Matrix worldTransform = Matrix.Identity;    public override void Execute(Node node)    {        Trasformation tNode = (node as Trasformation);        if (gNode)        {            worldTransform *= tNode.transform;        }    }}class GeometryNode : Node{    public Matrix GetWorldPosition()    {        //I create the operation to be executed:        GetWorldTranslationOperation getWorldTranslation = new GetWorldTranslationOperation();        //Now I need to iterate backwards through the tree        //And get all the transformations        Iterator backIter = new BackIter(this);        while (backIter.hasNext())        {            backIter.value.ExecuteOperation(getWorldTranslation);        }        return getWorldTranslation.worldTransform;    }    Matrix m_localTransform;}

would be run like this:

geometryNode.GetWorldPosition();

##### Share on other sites
The Visitor Pattern is often described in terms of "double dispatch", this is what you appear to have used here.
I use a similar method in my scenegraph:
I have my node-operations containing a dynamic array of functors (or function pointers) to functions that would perform the actual operation on a particular node. Each index in the array is referenced by a particular node type (similar method to RTTI but I use an enum so I can convert it to intergers for indexing the functors in my array for each node)

Therefore performing an operations on a node simply involves asking for the node type value (which is from enum NODE_TYPE ), finding the functor from the array and executing that functor.

My actual system is a little more complex. A traversal (otherwise called an action) is comprised of 1 or more actors which perform specific operations on nodes, these actors can be freely asigned to an action which will be performed on the scenegraph, eg rendering consists of a culling actor, (other actors) and funaly an actual draw actor.

This method allows for easy extensibility of node types, action (traversal) types and also lets me change or override functors for a specific instance of a traversal for special tasks. You might consider this method once you have a working engine, I've been told there are numerous resources on the net :)

• 36
• 15
• 9
• 23
• 10