Jump to content
  • Advertisement
Sign in to follow this  
FxMazter

SceneGraph & Composite pattern?

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

If you intended to correct an error in the post then please contact us.

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 !

Share this post


Link to post
Share on other sites
Advertisement
Hello,

you should take a look at the Visitor pattern. It is often used together with
Composite. The overall idea is that you traverse the scene graph with the visitor
object and each node calls a member function of the visitor, which implements the
operation to be performed. Every node derived from the base class must override
the traverse function and must call the visitor method for its particular type.
This prevents the use of dynamic_cast or RTTI.

Ciao, Thorris.

Share this post


Link to post
Share on other sites
Hum, I actually have checked out the Visitor pattern :)
But I don't see how that would help me out?

Lets say I have a design like this:


class Operation
{
virtual void RunOperation(TranslationNode node)
{
//Here goes the update for translationNodes
}

virtual void RunOperation(Node node)
{
//A catch for node types that are not supported
}
}

class UpdateTranslationNodeOp : Operation
{
virtual void RunOperation(TranslationNode node)
{
//Update the translation of the children
}

virtual void RunOperation(Node node)
{
//whatever...
}
}

class Node
{
virtual void ExecuteOperation(Operation op);
}

class TranslationNode : Node
{
virtual void ExecuteOperation(Operation op)
{
op.RunOperation(this);
}
}



Now that solves the problem of RTTI, but instead I will have a hard time
adding new Node types later on. For each NodeType I want to add I now
need to add a corresponding RunOperation(NewNodeType node) function
in every of my operations :(

So is there any other way to do this?

Share this post


Link to post
Share on other sites
This doesn't look like a typical instance of a composite pattern and nor does Wild Magic library seem to structure it's SG this way, although Eberly's book/s is/are decent & insightful i'm not very fond of the SG design.

Need to lay down some termnology, in the composite pattern the relation to have SG that implements it is:


Composite Pattern | Scene Graph structure
---------------------------------------------
Component | abstract Node
Composites | Grouping Nodes
Leafs | Leaf Nodes


in the composite patttern the component does not maintin a container of children there-for the base scene graph node shouldn't either (there is valid reason & very useful property to this i'll describe later on).

The sole purpose of the component is to define the interface for objects in the composition & implements default behavior for the interface common to all classes, as appropriate. For example the base node could (and usually does) contain a bounding volume this will automatically be distributed to all type nodes this will result in the ability to perform efficent hierarchical frustum culling of dynamic objects.

The component can optionally maintain a link to a parent (for a tree) or set of parents (for a DAG) which is distributed to all node types, in the context of the base SG node you will most definitely want to maintain a link to a parent because you will want to quickly propagate root in certain situations for instance in the example of the bounding volume you will need to update invalid bounds, this must happen from leaf to root!.

I suggest you don't maintain a set of parent links this make the structure a full-blown DAG (reasons for DAGs over trees are to permit sharing of nodes AKA instancing) it will make you cry, even a restricted form of DAG where you only permit the sharing of leaf nodes (the structure of the composite pattern makes this easy to convert because you've sperated concerns) can be complicated. Besides you can still have a tree structure and provide sharing instead of sharing nodes you can externalize state and share that, share node attributes for instance say you have a geo Node (a leaf node) that has reference to geometry you can share that with any number of geo nodes.

Another minuet detail is the type of the parent link member it should actually be of type reference/pointer to Composite/Group and not Componet/Base node because you want to enforce that only instances of Composites/Groups can be parents, instances of Leafs are terminal nodes they shouldn't be parents, in C++ you can do this you using a forward class declaration:


class Group; //group is an abstract class of all grouping node types

class abstract_node {
//...
Group* parent_ptr; //weak reference to parent node
//...
public:
//....
virtual ~abstract_node() { /* ... */ }
};


I don't know C# much but i'm pretty sure there isn't any need for forward class declarations you can just declare parent variable of type reference to Group.

Composites are the ones that maintain a collection of children, instances of composites represent internal nodes (non-terminal nodes), while instances of leaf types are just that leafs, terminal nodes, its not much sense for leaf types to inherit container of children from the base node when you've got composites. As i was saying before there is a nice property of speration of concerns, leafs are generally the renderable (or contain them) and have other things, internals nodes have things like transforms.

You should have look at this the example is in C# and this is gives more detailed description on composite pattern, basing a sg on a composite it should have something like this class hierarchy:


SG node (abstract class)
^
|
+ - - Group node (abstract class)
| ^
| |
| + - - Transform Group (concreate class)
| |
| + - - Any other Group types
|
+ - - - Any concreate Leaf thats appropriate i.e. Geo Node


You might want to check a thew SGs, you will find that openscenegraph, xith3d, nvidia recently released SG SDK follow this structure.

Your problem with type checking & casting you can't completely solve once you assign a derived instance to a base pointer/reference you've lost type information. There are (but very rarely) times you need to know the exact type a base pointer/reference refers to. To limit this to these very rare times your base node type should provide an appriopriate uniform interface (but not monolithic) this prevents you from caring what the actual type is.

Share this post


Link to post
Share on other sites
If you really just want to simplify things, you could just have a variable depicting the Node Type.

EX:

const int NodeType_Translation = 1;
const int NodeType_Geometry = 2;
//etc....

class Node
{
.....

int m_NodeType;
};

class TranslationNode: public Node
{
TranslationNode()
: m_NodeType(NodeType_Translation)
{
....
}

.......

};


Then just do a simple check. Although, that's kind of a cheating way.

Share this post


Link to post
Share on other sites
Thx for your replies!

And special thx to snk_kid!
The example I showed, was just to show my problem with the base class pointers.

I'm having problems figuring out how everyone supports operations on Nodes?

snk_kid, I would really appreciate if you could show me an example of how
you would for render a Node (a scene). No need to show the specific implementations.

I'm intrested in how you start the "Render operation" and how you would do to Render all the children of a Node?

I would think it should go something like this:

GeometryNode gNode = /*a "Renderable" node with children of unknown types*/
RenderList list = new SortByEffectRenderList();

gNode->Render(list);

GeometryNode::Render(RenderList list)
{
list.AddGeometryChunk(/*some geometry data*/);

for(each child) {
GeometryNode gNode = (child as GeometryNode);
if(gNode != null) {
gNode->Render(list);
}

}
}

Now this is not entirely valid, since I still need to continue Rendering the
child nodes of the child, even though they are not of GeometryNode type...

Alternatively I could put a Render function in the CompositeElement base class,
but then again - later on I might want to add equally complex operations, and
changing the CompositeElement base class is no good, since I will have to
recompile each module that uses the old CompositeElement base class :(

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!