SceneGraph & Composite pattern?

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.

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:



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?

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 typesclass 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.

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.

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

i posted an answer on the cross-post just before your replied here, it should clear things up abit.