# Scene Graph container :: questions

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

## Recommended Posts

Hi there, I am developing a container for scene graphs and was wondering if you guys could comment on what I've come up with so far. The container uses two structs, BRANCH_NODE and LEAF_NODE, as given by:
	struct BRANCH_NODE
{
LEAF_NODE*	_parent;	// the parent leaf this leaf stems from
LEAF_NODE*	_leaf;		// points to a doubly-linked list containing leafs
};
	struct LEAF_NODE
{
BRANCH_NODE*	_branch;	// points to the branch this leaf belongs to
// This is very useful for when iterating (i.e. going up-level)

LEAF_NODE*	_prev;
T		_data;
LEAF_NODE*	_next;

BRANCH_NODE*	_child;		// child branch, level down
};
There doesn't seem to be any reason for BRANCH_NODE to exist at the moment, as the information it holds is totally redundant, however, I'm thinking of adding an element count and a list tail pointer. Could you please comment on this design? Is this a robust enough container or is it likely to give me headaches? Am I missing something? Anything you can think of, please post it! As I'm sure you know, it is extremely important to get the design for this important container right from the start or I risk getting complications further down the road... I would have got this information from a book on game design but unfortunately I can't really afford to buy any at the moment as I'm a student living on a very poor and limited monthly budget. Also, finding resources on the net has proved a very difficult task, which humbly lead me here. Once again, it is all on you gurus to give me some inspiration and point me in the right direction. For that, I thank you. EDIT: On a different note, can static objects (ie objects part of a scene that never change in position/direction/etc) be contained in a scene graph or should they be contained elsewhere?

##### Share on other sites
One thing that immediately springs to mind is that your leaf nodes have children. By definition, leaf nodes are terminal and cannot have children, so your use of terminology there is misleading. On the other hand, I don't think there is a point in having leaf nodes as you want to be able to say attach a ParticleSystem to a RenderableModel, or a Sound to a ParticleSystem, meaning that all nodes would need to be capable of having children.

Another thing is that you're apparently using C, not C++. It's not for me to convince you of switching, but I believe that object-oriented languages are preferable. More importantly, the linked list might not be a good idea, depending on how you are going to use the scene graph, since this pretty much locks you into going through each child node until you find the one you need. Maybe this isn't an issue though, I haven't given it too much thought (nearly 5 am here sorry ^_^).

I've only written one very basic scene graph so far, but in my case I only had a Node class which had a single parent and a list of children. It took care of its transform and of propagating the transform changes to child nodes. All other nodes derived from it.

##### Share on other sites
Im not bought with this design. Theres a few things that stand out to me.

But firstly, contrary to what lightbringer said, it appears you are in fact using C++ not C, the syntax is wrong for C but correct C++ and your placement of the asterix for pointers is common pactice for C++ programmers and not so common in C.

Scene-graphs are especially well suited to object-oriented languages like C++ and making better use of the language can make an elegant scene-graph design.
What you have really got there is a generic tree rather than a 'scene-graph', I dont see what your design can actually do [grin], but I assume you just havn't built any functionality in yet?

Ok,
As has been said your terminology is incorrect, leaf-nodes dont usually have children, this is the job of group-nodes. If you wanted to go down this road and distinguish between leaf and group nodes then read up on the composite pattern (and I think its definately worth a look, especially if you're using C++), this is actually what many scene-graph designs follow. But remember every design has pros and cons, lightbringer gave a valid argument against the composite pattern, allowing all nodes to have children can have benefits.

However, as for the design you have currently, I think there are improvements to be made...

Your use of pointers to BRANCH_NODEs seem a bit odd, are you planning on dynamically allocating them?
Can you justify dynamically allocating them separately to LEAF_NODEs rather than just having a leaf-node hold a regular instance to one? I.e.
BRANCH_NODE _branch;
BRANCH_NODE _child;

If you gave each LEAF_NODE an instance like this then you might decide to conceptualise the design like this:
struct LEAF_NODE{    // These were expanded out of BRANCH_NODE _branch;    LEAF_NODE* _branch_parent;    LEAF_NODE* _branch_leaf;    // These were expanded out of BRANCH_NODE _child;    LEAF_NODE* _child_parent;    lEAF_NODE* _child_leaf    LEAF_NODE* _prev;    LEAF_NODE* _next;    T          _data;};

Now then based on this, you might want to consider whether a node really needs to store a pointer to its childs parent? Surely this pointer just points to itself? So we can remove _child_parent;
Similarly, as a node why would we want a pointer to our parents child? Either this pointer will point to ourself or to one of our siblings (which we can access through _next and _prev or through _branch_parent->_child_leaf), so lets also rid outselves of _branch_leaf.
So actually, now we've changed things so much theres no need for BRANCH_NODE to exist at all (you said yourself that it held redundant data, but you were using it as a means to hold connectivity data for the tree, so at-least before it had a purpose).

What we're left with is a type of quadly-linked list, it doesnt store any redundant pointers and its faster to traverse.
Using a name(s) that I feel more comfortable with rather than the incorrectly termed LEAF_NODE but in keeping with your naming conventions, the code now becomes:

struct SCENE_NODE{    SCENE_NODE* _parent;         // Equivalent to _branch_parent    SCENE_NODE* _first_child;    // Equivalent to _child_leaf    SCENE_NODE* _next_sibling;   // Equivalent to _next    SCENE_NODE* _prev_sibling;   // Equivalent to _prev    T _data;};

This design works quite well for scene-graphs, it has an added bonus that as you seem to be using C++ in a somewhat C-type manner this design works well in both languages [smile].

Regarding your second question, yes static objects can be contained within the scene-graph, many people, myself included, tend to hold all static geometry in a different structure that holds geometry-level spatial-partitioning data and this structure is then a node in the scene-graph representing all our static geometry at once under a single node.

[Edited by - dmatter on August 13, 2007 6:13:36 AM]

##### Share on other sites
Quote:
 What you have really got there is a generic tree rather than a 'scene-graph', I dont see what your design can actually do , but I assume you just havn't built any functionality in yet?

Right on the money! I built a generic template class which only offers containment functionalities and an iterator class for traversing the tree in the spirit of STL. So the actual scene graph container is still a long way away... :)

Quote:
 As has been said your terminology is incorrect, leaf-nodes dont usually have children, this is the job of group-nodes.

Agreed, leaves have no branches! LEAF_NODE now becomes GROUP_NODE, thanks.

Quote:
 Your use of pointers to BRANCH_NODEs seem a bit odd, are you planning on dynamically allocating them?

Yes, I'm dynamically allocating everything basically. The reason why I chose to go with the BRANCH_NODE design was merely to allow for some kind of containment of shared data for the hierarchy, i.e. the number of child nodes stemming from a parent node. But then again, due to my lack of experience developing 3d apps/games, I really have no clue whatsoever if there is any need for this kind of hierarchy-related data?

Anyway, the (generic) container I've come up with is quite fast. Running on a Centrino 2Ghz, 1GB RAM, with full optimizations on (SSE2, no frame pointer, etc), I can add 35000 nodes in under 15ms, and traverse the whole of it in under 0.5ms (~0.45ms/full iteration).

Quote:
 What we're left with is a type of quadly-linked list, it doesnt store any redundant pointers and its faster to traverse.

Alright! I think I'm going to adopt your design, as, I must concede, it is much more elegant and simple.
• Quote:
 Original post by hellraiserRight on the money! I built a generic template class which only offers containment functionalities and an iterator class for traversing the tree in the spirit of STL. So the actual scene graph container is still a long way away... :)

Yes, code re-use is an important thing. You may also want to consider that can be different ways to traverse a scene-graph (although depth-first is the most common) so you can write different iterators as and when you need to traverse in a different order e.g. breadth-first.

Quote:
 Yes, I'm dynamically allocating everything basically. The reason why I chose to go with the BRANCH_NODE design was merely to allow for some kind of containment of shared data for the hierarchy, i.e. the number of child nodes stemming from a parent node. But then again, due to my lack of experience developing 3d apps/games, I really have no clue whatsoever if there is any need for this kind of hierarchy-related data?

Separating the BRANCH_NODE could allow you to create some exotic links between nodes, whilst intersting, I cannot think of a situation where this would be useful more concernedly I can easily think of scenarios where memory management problems and dangling pointers are ripe.
I dont imagine you had actually planned to use the BRANCH_NODE in such a way as to create these exotic links but it does show you that potential head-aches could ensue.

I dont think containing and trying to share this data is especially useful anyway, you can store data like the number of child nodes stemming from a parent actually within that parent node; then this data is accessible from all its surrounding nodes and in-fact indirectly from anywhere within the hierarchy provided you know the traversal path from an arbitrary node to the parent node in question.

Quote:
 Anyway, the (generic) container I've come up with is quite fast. Running on a Centrino 2Ghz, 1GB RAM, with full optimizations on (SSE2, no frame pointer, etc), I can add 35000 nodes in under 15ms, and traverse the whole of it in under 0.5ms (~0.45ms/full iteration).

Oh certainly, what you had originally was very lightweight you wouldnt have found a performance issue with it, actually you're quite unlikely to find your scene-graph is going to be a bottleneck provided you treat it nicely.
The design I suggested does shave off a few pointer indirections but theyre cheap-as-chips anyway.

Quote:
 Alright! I think I'm going to adopt your design, as, I must concede, it is much more elegant and simple. KISS is the way to go. :)Thank you for everything, you have no idea how helpful you were to me.

No problem [smile]
The elegancy of it is quite attractive. There are of-course other elegant designs that a scene-graph could follow.

The quartic-linked tree I suggested is a popular approach, the child nodes are basically a doubly-linked list between themselves.
Alternatively you could choose to store all a nodes children in a std::vector, using a vector it would be trivial to know how many children a group-node has and you could jump direcly to a specific child node which cannot be done from a linked list. Whether or not random-access to child nodes is useful or not depends really on how you intend to use the scene-graph, using a vector could lead to continual memory re-allocation if nodes are moved around a lot and the vector needs to resize.

snk_kid once made an in-valuable resource post which is useful to all who are learning or implementing scene-graphs.