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: 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:) )

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.

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();

gNode1.AddChild(tNode1);
gNode1.AddChild(gNode2);


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

GeometryNode::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
}



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?

Quote:Original post by FxMazter
GeometryNode::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]

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!

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

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.

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();