Scene Graph. DAG or Tree With Mesh List?

I'd go with the second option. Store the world transform for a given scene node in that node, and have it point to the geometry (or geometry list) it uses; the geometry is not part of the tree.

If you want to have a DAG then to make it more manageable (and life easier) make it a restricted form of DAG where only leaf nodes are allowed to be shared, a common technique to implement this is to use the composite design pattern (i recommend googling it up lots of resources online, it's more typical for them to be n-ary trees though), basically instead of all node types being able to have children you make the distinction between leaf node types (terminal nodes in a tree/DAG that cannot have children attached) and grouping node types (nonterminal, internal nodes in a tree/DAG) only instances of leaf node types can be shared (i show you how in a moment). The grouping node types are the composites in the composite pattern and share the same interface as leaf node types hence recursive composition.

In this case a transform node will be a sub-type of a grouping node type and the mesh node would be a leaf node (sub-)type. This allows you to to share a mesh node instance by any number of transform node instances (and any grouping node type).

Some code to illustrate restricted form of DAG [grin]

#include <boost/shared_ptr.hpp>#include <deque>// Component, the interface into the composite patternclass scene_node {        // important! yes not parent pointers to scene_node but group nodes	friend struct group;public:	typedef std::deque<group*> parent_list;        // .......private:	parent_list parents;        // .......protected:	void add_parent(group* parent_ptr) {		return parents.push_back(parent_ptr);	}        // .......public:        // just to enforce scene_node is an abstract type	virtual ~scene_node() = 0;        // .......};inline scene_node::~scene_node() {}// The compositesstruct group : scene_node {	typedef boost::shared_ptr<scene_node> node_ptr;	typedef std::deque<node_ptr> child_list;// .......private:	child_list kids;// .......public:	void add_child(const node_ptr& n) {		n->add_parent(this);		kids.push_back(n);	}// .......};struct transform : group { /* .... */ };// this is a leaf node type!struct geo_node : scene_node { /* .... */ };int main() {	typedef boost::shared_ptr<scene_node> node_ptr;	typedef boost::shared_ptr<group> group_ptr;	group root;	group_ptr trans1(new transform()), trans2(new transform());	node_ptr mesh(new geo_node());	trans1->add_child(mesh);	trans2->add_child(mesh);	root.add_child(trans1);	root.add_child(trans2);}

so the DAG instance will look like this:

         root           |           |   -----------------   |                |   |                |trans1            trans2   |                |   |                |   ------------------           |           |         mesh

The other option is like what you mentioned in your second option, is to make nodes almost completely stateless but hold pointers to there state then they can be shared so it can be n-ary tree (this can also be applied to a DAG of course). This option has the advantage of being much more simplified, easy to manage/maintain.

note: The composite pattern doesn't have to be a DAG structure its more typical for it to be an n-ary tree.

[Edited by - snk_kid on September 16, 2005 2:43:26 AM]

Thanks for the reply snk_kid (what does that mean, btw?).

At the moment I have my m_worldTransform member in the base class and then I have a recursive function that walks down the tree calculating it from the m_localTransform member. Individual mesh objects (single nodes) are then queued ready to be sorted and rendered. If these mesh objects are shared as in the DAG, this will cause an issue. The only way round that is to queue the parent node (trans1&2), which is less optimal if it contains multiple meshes because then they cannot be sorted by material (for example) easily for rendering.

I was reading the Eberly game architecture book, and he seems to advocate making copies of the geometry objects instead of sharing them, and instead sharing the underlying vertices/indexes/uv's etc. (implicit with a copy of the smart pointers). What do you think to this approach? Seems to keep the scene graph nodes and queue to renderer much simpler.

Thanks again for your valuable insight.

[Edited by - Raeldor on September 15, 2005 7:56:25 PM]

i think i made a slight mistake about nodes in a DAG having the same parent more than once i guess i got confused with all the links flying around [grin]. I've updated my previous post.

Quote:

Original post by Raeldor (what does that mean, btw?).

Doesn't mean anything, i'm just a an SNK fanatic.

Quote:

Original post by Raeldor At the moment I have my m_worldTransform member in the base class and then I have a recursive function that walks down the tree calculating it from the m_localTransform member. Individual mesh objects (single nodes) are then queued ready to be sorted and rendered. If these mesh objects are shared as in the DAG, this will cause an issue. The only way round that is to queue the parent node (trans1&2), which is less optimal if it contains multiple meshes because then they cannot be sorted by material (for example) easily for rendering.

So here you are caching concatenated transforms getting them all prepared yeah there really isn't a clean way of doing the same with a DAG, you would have to do it outside of the structure.

Quote:

Original post by Raeldor I was reading the Eberly game architecture book, and he seems to advocate making copies of the geometry objects instead of sharing them, and instead sharing the underlying vertices/indexes/uv's etc. (implicit with a copy of the smart pointers). What do you think to this approach? Seems to keep the scene graph nodes and queue to renderer much simpler.

Yeah it's a good idea i would do that with some parts of DAG aswell, an n-ary tree does simplify things alot though.

In wild magic a geometry node can only represent a single geometry but you can take it further by having a geo node that represents a set of geometry/renderables (container of pointers). All this is of course applicable to DAGs aswell.

The only disadvantage of n-ary tree against a DAG or other graphs is that it's less flexible. I was speaking to Superpig the other night about this and he was saying that really what you want from a scene graph is a directed cyclic graph (DCG) which is slightly more general than a DAG. Despite that don't knock simplicity and you will read more people using n-ary trees.

[Edited by - snk_kid on September 16, 2005 3:15:32 AM]

In my scene graph i have one base class SceneNode that forms the hierarchy (can have one parent and any count of childs). Currently it only holds only transformation coordinates. Coordinates are given relative to parent node, ie in parent's object space, so if you move a node all child nodes are automatically moved too. It uses GetWorldTransform() method which calls parent's GetWorldTransform() and so on, this way traversing the tree upwards to get nodes world transform (which is cached). InvalidateWorldTransformCache() is called if the node is moved, it's called on each child too, so they invalidate their world transform caches too.

Now for model rendering i have a Mesh class which holds vertex/index buffers and material. Mesh'es are grouped by Model class, but it's used only as a blue print. There's a ModelInstance class which is derived from SceneNode. It holds smart pointers to meshes of corresponding Model class.

Wow, thanks all for your help, especially snk_kid. Check this out...

I went for a solution of having the geometry object instanced (duplicated) and sharing the arrays of vertices, uv's etc. via smart pointers (members of the geometry object). This means I can keep my local and calculated world transform in the geometry object and then queue individual geometry pieces into the render queue to be sorted already with their corresponding world matrix calculated.

I have a hierarchical scene graph which can now be a simple n-ary tree, which is walked when calculating world transforms and AABB etc. I then pass this scenegraph root node as a parameter to my quadtree class and build a static (will later be dynamic) quadtree using this information. From there I can use the quad tree to (for only those objects in the view frustum) tesellate (optional, for LOD pieces such as terrain) and place object pieces (individual geometry nodes) into the renderer queue ready for sorting and rendering.

I have this coded all this up now and it works GREAT! I created two resource types and manager classes (templates)...

-----

Shared Resources (Shared Resource Manager)

This is where the object itself is shared. The manager maintains a hash table by filename, and keeps the object and updates it’s usage count when it is created/reused/released. This is primarily used for textures right now.

Instanced Resources (Instanced Resource Manager)

This is where the object itself is created again, but the underlying data (vertices, uv’s etc.) are shared. This simplifies the scene graph and render queue code a lot. The manager maintains a hash table by filename, but for each entry is a list of pointers to objects that are created using the resource. No usage count is kept because only one usage exists per object instance. When the object is released it must be done using both name and pointer so the correct instance of the object can be removed. Because it keeps a list of all objects that use the resource, it doesn't matter if the first object is released because if you try to load the resource again it will just pick up the next object that was a copy of the original. This is primarily used for meshes right now.

-----

I think this scene graph/spatial tree hierarchy interaction is probably the biggest logical hurdle I have had to overcome yet. I hope that this simplified approach will pay off by making the code easier and less error prone.

Anyways, would be interested to hear comments.

Thanks again peeps!

Oh, BTW you will be able to see all this in action when I release the new version of my terrain editor (see http://raeldor.blogspot.com for previous coverage). You will soon be able to export models from 3ds (I have written an exporter too), and place them on the terrain and have all the information exported in simple XML ready for import into any engine.

Hi,

For those who may be interested, here is a shot from the latest build of my terraformer world editor. Using the new scene graph, quadtree and resource manager functionality I can now load complex objects (multi-part meshes) that have been exported from 3ds max.



Next stage is to put in a user interface to keep an object manifest and then be able to place objects from the manifest on the terrain complete with WYSIWYG scale, move and rotate functionality. This will then be exported to XML for import into an engine.

The same engine that drives this editor application will be used for my game. Next stage after the above is to add animation controllers, boned animation (with ability to share skeleton between meshes) and tagging.