• Advertisement
Sign in to follow this  

SceneGraph

This topic is 4794 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 ! (Sorry for posting in the Graphics forum, you may remove that thread:) )

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Why do you need to update the children translations? The whole point of a scenegraph is that transformations are cumulative. So if you translate tNode1 by 1,0,0, then each child of tNode1 automatically gets translated by that much as well.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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-instanceable
class 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-instanceable
struct 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]

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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 of
Node::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
//info
class 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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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();

Share this post


Link to post
Share on other sites
The Visitor Pattern is often described in terms of "double dispatch", this is what you appear to have used here.
I use a similar method in my scenegraph:
I have my node-operations containing a dynamic array of functors (or function pointers) to functions that would perform the actual operation on a particular node. Each index in the array is referenced by a particular node type (similar method to RTTI but I use an enum so I can convert it to intergers for indexing the functors in my array for each node)

Therefore performing an operations on a node simply involves asking for the node type value (which is from enum NODE_TYPE ), finding the functor from the array and executing that functor.

My actual system is a little more complex. A traversal (otherwise called an action) is comprised of 1 or more actors which perform specific operations on nodes, these actors can be freely asigned to an action which will be performed on the scenegraph, eg rendering consists of a culling actor, (other actors) and funaly an actual draw actor.

This method allows for easy extensibility of node types, action (traversal) types and also lets me change or override functors for a specific instance of a traversal for special tasks. You might consider this method once you have a working engine, I've been told there are numerous resources on the net :)

Share this post


Link to post
Share on other sites
dmatter, thx that was very intresting. I will rather continue on what you said
instead of having to remake it later on :)

Share this post


Link to post
Share on other sites
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

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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
If you want to avoid RTTI, then you have to go with the more traditional visitor pattern:

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.

Share this post


Link to post
Share on other sites
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:


#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]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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!

Share this post


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

  • Advertisement