dmatter, thx that was very intresting. I will rather continue on what you said
instead of having to remake it later on :)
SceneGraph
Author
dmatter, I was thinking about you said your method allows for easy extensibility of node types.
But what If it is like this:
module:GameEngine.dll
then you wish to extend the node types:
module:NewModule1
and then someone else makes another module, not knowing about NewModule1:
module:NewModule2
Will there not be problems like this if using an enum for NodeType's ?
But what If it is like this:
module:GameEngine.dll
enum NodeTypes { GeometryType = 1, TranlsationType = 2}then you wish to extend the node types:
module:NewModule1
enum NodeTypes { GeometryType = 1, TranlsationType = 2, PhysicsNode = 3}and then someone else makes another module, not knowing about NewModule1:
module:NewModule2
enum NodeTypes { GeometryType = 1, TranlsationType = 2, SoundNode = 3;}Will there not be problems like this if using an enum for NodeType's ?
Yes, there are disadvantages to using an enum (like what you describe) so in general when you want to extend the list you need access to the original enum. This enum could be stored in a DLL. There are other methods, other than using enums, you could use a NODE_TYPE class that allows the user to register new node types and will automatically assign a new enique value for each node type. This class could act like an enum with an interface such as
void AddNodeType(char *name); //Will make a new node with a unqie ID
int GetNodeType(char *name); //Will retreive the unique ID for a node
The reason I use an enum is because it is a simple work-around for not using a NODE_TYPE class, although I might one day switch to one to allow easy extensibility of new node type names when access to the original enum is unavailable.
void AddNodeType(char *name); //Will make a new node with a unqie ID
int GetNodeType(char *name); //Will retreive the unique ID for a node
The reason I use an enum is because it is a simple work-around for not using a NODE_TYPE class, although I might one day switch to one to allow easy extensibility of new node type names when access to the original enum is unavailable.
If you want to avoid RTTI, then you have to go with the more traditional visitor pattern:
This might or might not work better, depending on your build dependencies. If you only have to recompile the module/assembly that contains NodeOperation every time you add a node, then it isn't a problem to reflect those changes. Otherwise dmatter's approach might would work better.
class NodeOperation{ public virtual void Execute(Group node){} public virtual void Execute(Transformation node){} public virtual void Execute(GeometryNode node){}};This might or might not work better, depending on your build dependencies. If you only have to recompile the module/assembly that contains NodeOperation every time you add a node, then it isn't a problem to reflect those changes. Otherwise dmatter's approach might would work better.
Sorry i took some time, had sort the example out and make it worthy but concise at the same time (with some help with boost library), you should use proper vistor pattern (so long as you have a stable class hierarchy), the whole point is to avoid type casting and/or type switching:
As i said before you don't have to follow this down to a T its just an example, there so many variations of the vistor pattern & different implementations in each language i'd suggest you do a little research into it for your particular language.
[Edited by - snk_kid on January 8, 2005 3:28:28 PM]
#include <boost\smart_ptr.hpp>#include <algorithm>#include <vector>#include <iostream>namespace System { template < typename Base > struct Cloneable { virtual Base* clone() const = 0; virtual ~Cloneable() = 0; }; template < typename T > inline Cloneable<T>::~Cloneable() {}};namespace SGTraversers { struct traverser;};namespace SG { using SGTraversers::traverser; class bounding_volume { /* .... */ }; class geometry { //.... geometry() {} geometry(const geometry&) {} geometry& operator=(const geometry&) { return *this; } //.... public: typedef boost::shared_ptr<geometry> geo_ptr; static geo_ptr create() { boost::shared_ptr<geometry> n(new geometry); return n; } }; //abstract class - should be non-instanceable class Node : public System::Cloneable<Node> { friend struct Group; //forward class declaration Group* parent_ptr; bounding_volume worldBV; protected: Node(Group* p = 0, const bounding_volume& bv = bounding_volume()) : parent_ptr(p), worldBV(bv) {} Node(const Node& n) : parent_ptr(n.parent_ptr), worldBV(n.worldBV) {} Node& operator=(const Node& n) { if(this != &n) { parent_ptr = n.parent_ptr; worldBV = n.worldBV; } return *this; } const Group* const parent() const { return parent_ptr; } void parent(Group* p) { parent_ptr = p; } //..... public: typedef boost::shared_ptr<Node> node_ptr; //... virtual void accept(traverser&) = 0; const bounding_volume& world_bounds() const { return worldBV; } virtual ~Node() { parent_ptr = 0; } }; //abstract class - should be non-instanceable struct Group : public Node { typedef boost::shared_ptr<Node> node_ptr; typedef std::vector<node_ptr> child_list; typedef boost::shared_ptr<Group> Group_ptr; typedef child_list::const_iterator const_child_itr; typedef child_list::iterator child_itr; typedef child_list::size_type size_type; //.... private: child_list kids; void clone_group(const Group& g) { struct cloner { node_ptr operator()(const node_ptr& n) const { node_ptr nn(n->clone()); return nn; } }; if(kids.empty()) { kids.reserve(g.kids.size()); std::transform(g.kids.begin(), g.kids.end(), std::back_inserter(kids), cloner()); } else std::transform(g.kids.begin(), g.kids.end(), kids.begin(), cloner()); } //.... protected: Group(size_type n = 0): Node(), kids() { kids.reserve(n); } Group(const Group& g): Node(g), kids() { clone_group(g); } Group& operator=(const Group& g) { if(this != &g) { Node::operator =(g); clone_group(g); } return *this; } //.... public: //... const_child_itr child_begin() const { return kids.begin(); } child_itr child_begin() { return kids.begin(); } const_child_itr child_end() const { return kids.end(); } child_itr child_end() { return kids.end(); } void addChild(const boost::shared_ptr<Node>& new_kid) { const_child_itr result = std::find(kids.begin(), kids.end(), new_kid); if(result == kids.end()) { new_kid->parent(this); kids.push_back(new_kid); } } //... }; class TransformG : public Group { TransformG(): Group() {} TransformG(const TransformG& t): Group(t) {} TransformG& operator=(const TransformG& t) { if(this != &t) { Group::operator =(t); } } public: typedef boost::shared_ptr<TransformG> trans_ptr; static trans_ptr create() { trans_ptr t(new TransformG); return t; } void accept(traverser& t); TransformG* clone() const { return new TransformG(*this); } }; class GeoNode : public Node { geometry::geo_ptr geos; GeoNode(geometry::geo_ptr g): Node(), geos(g) {} GeoNode(const GeoNode& t): Node(t) {} GeoNode& operator=(const GeoNode& t) { if(this != &t) { Node::operator =(t); geos = t.geos; } } public: typedef boost::shared_ptr<GeoNode> geo_node_ptr; static geo_node_ptr create(geometry::geo_ptr ge) { geo_node_ptr g(new GeoNode(ge)); return g; } const geometry::geo_ptr& get_geo() const { return geos; } geometry::geo_ptr get_geo() { return geos; } void accept(traverser& t); GeoNode* clone() const { return new GeoNode(*this); } //... };};namespace RenderingSystem { using namespace SG; struct RenderList { bool cull(const bounding_volume&) const { return false; } void AddGeometryChunk(boost::shared_ptr<geometry>&) {} void draw(const Node* const) const {} };};namespace SGTraversers { using namespace SG; struct traverser : public System::Cloneable<traverser> { virtual void visit(TransformG*) = 0; virtual void visit(GeoNode* g) = 0; virtual void do_visit(Group* g) { struct acceptor { traverser* owner; acceptor(traverser* t): owner(t) {} void operator()(boost::shared_ptr<Node>& n) { n->accept(*owner); } }; std::for_each(g->child_begin(), g->child_end(), acceptor(this)); } template < typename Predicate > void do_visit_if(Group* g, Predicate cmp) { Group::child_itr itr(g->child_begin()), end(g->child_end()); while(itr != end) { if(!cmp(*itr)) (*itr)->accept(*this); ++itr; } } virtual ~traverser() {} }; using RenderingSystem::RenderList; class RenderOp : public traverser { RenderList& renderer; struct culler { RenderList& r; culler(RenderList& _r): r(r) {} bool operator()(boost::shared_ptr<Node>& n) const { return r.cull(n->world_bounds()); } }; public: RenderOp(RenderList& r): renderer(r) {} RenderOp* clone() const { return new RenderOp(*this); } void visit(TransformG* t) { if(!renderer.cull(t->world_bounds())) do_visit_if(t, culler(renderer)); } void visit(GeoNode* g) { if(!renderer.cull(g->world_bounds())) { // try to cull leaf renderer.AddGeometryChunk(g->get_geo()); //... renderer.draw(g); //... } } };};namespace SG { void GeoNode::accept(traverser& t) { t.visit(this); } void TransformG::accept(traverser& t) { t.visit(this); }};int main() { using namespace SG; RenderingSystem::RenderList renderer; geometry::geo_ptr g = geometry::create(); TransformG::trans_ptr root = TransformG::create(); TransformG::trans_ptr sib_trans = TransformG::create(); GeoNode::geo_node_ptr geo = GeoNode::create(g); root->addChild(geo); geo = GeoNode::create(g); root->addChild(geo); geo = GeoNode::create(g); sib_trans->addChild(geo); root->addChild(sib_trans); SGTraversers::RenderOp r(renderer); root->accept(r);}As i said before you don't have to follow this down to a T its just an example, there so many variations of the vistor pattern & different implementations in each language i'd suggest you do a little research into it for your particular language.
[Edited by - snk_kid on January 8, 2005 3:28:28 PM]
The way i solved this problem was in my base node class have one pure virtual method "Execute" which takes an integer as an argument indicating the action to be performed (rendering, culling, physics, loading, saving, etc.).
Inside Execute, a check determines whether this node has to actually perform anything for the given action, if so it does that action, and regardless calls the Execute method of all of its children with the same action.
This removes the need for RTTI since each node only needs to know its own type.
James
Inside Execute, a check determines whether this node has to actually perform anything for the given action, if so it does that action, and regardless calls the Execute method of all of its children with the same action.
This removes the need for RTTI since each node only needs to know its own type.
James
I'm fond of my method (described above) it is similar to the visitor pattern, the action to be performed is stored in the traversal object (like the visitor pattern) and the action to be performed is decided by the node using int GetNodeType() but the advanatges over the vistor patern are that the traversal object only jeeps functors (or function pointes) to the functionality, this allows easy extensibility of new traversal types as well as node types I can also override the funcionality of an instance of a traversal for a specific node(s) by chainging the functor in the instance of the traversal object.
I have also devised a way to allow me to couple multiple traversal objects together (each object is called an actor) into one traversalthat are performed in the order they were added. I also have a separate object for iteration so I can change the iteration technique (top-down etc)
Therefore I have a very advanced and extensibly scenegraph system.
I have also devised a way to allow me to couple multiple traversal objects together (each object is called an actor) into one traversalthat are performed in the order they were added. I also have a separate object for iteration so I can change the iteration technique (top-down etc)
Therefore I have a very advanced and extensibly scenegraph system.
Author
Thx guys, and again special thanks to snk_kid :)
That example was great :) better than any book I've seen so far heh
I think I'm ready to start over on my scenegraph :) (Third time actually)
I'll post again in a couple of days or so, the final design of my scenegraph :)
Thanks!
That example was great :) better than any book I've seen so far heh
I think I'm ready to start over on my scenegraph :) (Third time actually)
I'll post again in a couple of days or so, the final design of my scenegraph :)
Thanks!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
