Sign in to follow this  
FxMazter

Scene Graph & visitor pattern?

Recommended Posts

FxMazter    164
Hey guys! I have been reading on different implementations of Scene Graphs. And I'm wondering if anyone have implemented it using the visitor pattern? The simple standard visitorpattern could be applied like this:
//The default node type in the scenegraph
class ISceneNode;

//A node that has information to test collision
class ICollideable;

//A node that has enough information to be rendered
class IRenderable;

//This is the class that every node will visit
//You can derive different kinds of operations...
//Rendering or Collision testing
class ISceneGraphOperation {
public:
	virtual void Visit(ICollideable* pNode) = 0;
	virtual void Visit(IRenderable* pNode) = 0;
	virtual void Visit(ISceneNode* pNode) = 0;
};


//This would make a SceneGraph where you could add new operations
//along the way
class ISceneGraph {
public:
	virtual void AddSceneGraphOperation(ISceneGraphOperation* pOperation) = 0;
	
	virtual void RunOperations() {
		for(each ISceneNode) {
			for(each ISceneGraphOperation) {
				pSceneNode->AcceptVisitor(pSceneGraphOperation);
			}
		}
	}
};

//Example of a Collision testing operation
class CheckCollisionsOperation : public ISceneGraphOperation {
public:
	//...
	virtual void Visit(ICollideable* pNode) {
		//whatever...
	}
	//...
};

//Example of a rendering operation
class RenderNodeOperation : public ISceneGraphOperation {
public:
		//...
	virtual void Visit(IRenderable* pNode) {
		//push the data to a VertexCache or whatever...
	}
	//...
};

After I have read some about Scene Graphs I get the feeling that not so many BaseClasses on nodes are added after the standard ones -> like Collision, Rendering, Physics ... classes. Then only Derived ones from those base classes are created. So as long as the ISceneGraphOperations would support the standard baseclasses, then everything would be fine right? How would an acyclic visitor pattern with a dynamic_cast work with performance in mind? Looking forward for any thoughts about this kind of design.

Share this post


Link to post
Share on other sites
Nypyren    12063
I implemented a Scenegraph in C# using Visitors. It works well - I haven't progressed to a point where I can test for performance or anything.

What I have so far -

EffectVisitor - responsible for setting DirectX "Effect" objects up.
FrustumCullVisitor - disables the GraphicsVisitor when a BoundingNode is outside of the view frustum.
GraphicsVisitor - when enabled, renders ShapeNodes.
LightVisitor - adjusts lighting when a LightNode is traversed.
SoundVisitor - plays or updates sound effects when SoundNodes are traversed.
TransformVisitor - maintains a tramsform stack to be used by SoundVisitor and GraphicsVisitor.
UIMouseVisitor - does hittesting on UIGeometryNodes to update 3d user interface.

The traverser maintains a list of Visitors, and some visitors reference others.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Nypyren
I implemented a Scenegraph in C# using Visitors.


Are you sure you understand what a scene graph is and what visitor pattern is and what it's applied for?

basing the main structure of a scene graph soley on the visitor pattern is a little mad.

a visitor:

Quote:

Represent an operation to be performed on the elements of an object structure. Visitor lets you define new operations without changing the classes of the elements on which it operates


Remember visitor is a behavioural pattern and not a structural pattern and behavioural patterns can be used inconjunction with structural patterns, a scene graph implies a data structure normally a kind of tree data structure.

Scene graph usually are mean't to represent whole-part hierarchies (not to be confused with class hierarchies which represent static relationships this implies dynamic relationships or object hierarchies).

so there is a structural pattern that fits this bill of typical scene graph:

Composite pattern:

Quote:

Compose objects into tree structures to represent whole-part hierarchies. Composite lets clients treat indiviual objects & compositions of objects uniformly.


visitor certainly goes well with composites as they represent operations/behaviours that you don't wont to distribute across a type hierarchy and you isolate it in one place.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
or http://www.opensg.org/
(speciel support for rendering on cluster with multiple display surfaces)

Share this post


Link to post
Share on other sites
FxMazter    164
snk_kid, hey I was hoping for your reply on the Scene graph thread in the Game Programming forums :)

I checked out that thread where you spoke of implementing a SceneGraph using the composite pattern. That sounds very nice and clean to me.
I read the example you had there with the transorm3d stuff, and
it seemed to work very well.

I was hoping you could post another example in that thread:

The other thread

The thing I'm a little unclear about is that of how you would actually
update the nodes. For eg. if I got it right you mentioned using
a Controller node for updating nodes in the structure? Did you
mean removing the "standard" Update() function in the Nodes?
For what I know the composite pattern needs a common Operation
that all nodes have like Traverse(), Update(), Process() which
is called for all the children in the structure.

Maybe if you posted another example explaining it I would
understand it better.

Lets say you have a scene like this:
Root
.|->TransformGroup01 (the relative position to the root for all children)
.......|->GeometryGroup
...........|
...........|->PlayerMesh
................|->TransformGroup02
......................|->GeometryGroup
..........................|->GunMesh

Now lets say you change the position on the TransformGroup01

transform_group01->transform(matrix);

Now from an abstract view, which is how you work with the
scenegraph I guess, would you update it like this:

Composite* pCompositeGroup = transform_group01;
pCompositeGroup->Update();

Which would in turn do something like this:

Composite::Update(){
for(each child) {
child->Update();
}
}

Or would you somehow do this "Update()" with some design pattern?

This is where I thought about visitor patterns...

Anyway, as I mentioned, another example would be great!
Thank you!

Share this post


Link to post
Share on other sites
FxMazter    164
And I was also thinking about having another SceneGraph which
would keep Spatial information.

which would prolly work something like this:

SceneGraph->ColloctRenderables(pVisitor);

where pVisitor is a RenderableVisitor:

class RenderList : public RenderableVisitor {
public:
....SetFrusturm(...);
....Visit(IRenderable*);
....Visit(ISceneNode*);
};

Now only the IRenderable within the Frusturm would be collected...


Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by FxMazter
snk_kid, hey I was hoping for your reply on the Scene graph thread in the Game Programming forums :)


Sorry i never saw it, i'll reply to that one soon.

Quote:
Original post by FxMazter
The thing I'm a little unclear about is that of how you would actually
update the nodes. For eg. if I got it right you mentioned using
a Controller node for updating nodes in the structure? Did you
mean removing the "standard" Update() function in the Nodes?
For what I know the composite pattern needs a common Operation
that all nodes have like Traverse(), Update(), Process() which
is called for all the children in the structure.


It depends on exactly what you mean by update, the scene graph could be updated in different ways which could even be implicit (meaning no explicit "update" method) via external forces.

Really i think i do know what your referring to when you say "standard" update method, it depends on how or going to implement it, in that thread the guy said he was having problems because for him it didn't make sense to have an "update" method for certain types of nodes so i suggested to take it out of the main structure because these time-varying quantities that apply mostly to particular kinds of groups that implicitly effect it's children it contains.

In 3ds max sdk they have something called controller types so thats where that idea came from but when you think about it controller is really a specialization of a behaviour (not in the OO sense) this creates a so called "behavioural graph", i've seen "behavioural graph" merged into the scene graph (that was implemenated with a composite pattern) by using a kind of Decorator pattern on a Composite pattern (notice in the definition of decorator pattern the component from composite pattern is mentioned).

At the time in the other thread i didn't relize it but i think i was applying the kind of decorator pattern for "RigidBodyInterloper" type.

Quote:
Original post by FxMazter
Lets say you have a scene like this:
Root
.|->TransformGroup01 (the relative position to the root for all children)
.......|->GeometryGroup
...........|
...........|->PlayerMesh
................|->TransformGroup02
......................|->GeometryGroup
..........................|->GunMesh


You don't need a GeometryGroup type, geometry is either a leaf or is referenced by leaf and implicitly contained in a particular type of Group.

Quote:
Original post by FxMazter
Now lets say you change the position on the TransformGroup01

transform_group01->transform(matrix);

Now from an abstract view, which is how you work with the
scenegraph I guess, would you update it like this:

Composite* pCompositeGroup = transform_group01;
pCompositeGroup->Update();

Which would in turn do something like this:

Composite::Update(){
for(each child) {
child->Update();
}
}


if transform_group is a sub-type of Composite then you can call "update" directly from transform_group01.

Quote:
Original post by FxMazter
And I was also thinking about having another SceneGraph which
would keep Spatial information.


the transform groups is the main spatial information, granted its minimal but it does represent location & orientation.

Share this post


Link to post
Share on other sites
CoffeeMug    852
Visitor simply changes the trade offs. Adding new classes becomes complicated while adding new operations becomes simple. What is the purpose of using the visitor pattern with a scene graph? It seems like you're a lot more likely to add new types of objects than to add new operations. Visitor pattern is more appropriate for the opposite case: when your hierarchy is very stable (highly unlikely you'll be adding more object types) but you often add new operations.

Share this post


Link to post
Share on other sites
FxMazter    164
snk_kid, thx I think I understand it more or less now :)

CoffeeMug, yeh I know that but after checking out some implementations of scenegraphs I noticed that in fact there
are not so many baseclasses - mostly derived classes from
a couple crucial baseclasses.

So making a visitor for those baseclasses would suffice.


[Edited by - FxMazter on October 5, 2004 2:04:20 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this