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]
