Jump to content
  • Advertisement
Sign in to follow this  

some Scene Graph thoughts (again)

This topic is 4192 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

Hi, since I started with a new engine I am thinking about writing a new scene graph implementation I have read several threads about SGs from the past especially this one here Terrain and Scene Graphs Here a little example of what I thought would be a good SG representation of complex scenes
   1 digraph{
  2         root->lights;
  3         root->dynamic_objects;
  4         root->quadtree_root;
  6         edge [color=Red, style=solid]
  7         lights->{light1;light2;light3;light4;light5};
  8         light1->{terrainpatch1; crate; stones; wood; car};
  9         light2->{terrainpatch1; wood; tank};
 11         edge [color=Green, style=solid]
 12         quadtree_root->{ quad1; quad2; quad3; quad4};
 13         quad2->{ terrainpatch1; crate; stones; wood; car};
 14         quad3->{ tank};
 16         edge [color=Blue, style=solid]
 17         dynamic_objects->car;
 18         dynamic_objects->tank;
 19 }

It works like this, e.g.: (the car moves) - car notifies its parents light1, quad2 that it moved and its current state is invalid this works recursively upwards until you reaches the "quadtree_root" or "lights" node quad2 tries to fit the car into its current bounding volume, otherwise the nodes upwards will keep track of it the light1 node does a light volume check, otherwise lights will pass it to the other available lights the spatial division of the lightsources is contained in the "lights" node to simplify the graph a little in the quad nodes I will include a group node to seperate by shaders/materials thus building the material list of visible geometry will be easier what do you think about this seperation of logic("dynamic objects", "spatial scene representation","lights")? the spatial division of lights is seperated since its only needed to build the light<--*>object relation ship, the final list of visible lights is build out of the list of visible objects e.g.:
map< objectlist> ct;
for each visible object
  for each light parent

looks like this
  "light1" = {"car"}
  "light2" = {"other objects"}
the scene node hierarchy will use multiple inheritance and RTTI
class scene_node;
class pickable;
class cullable;
class lightcastable;
... many more
and the scene_node will implement a pre & post interface thus implement the visitor pattern pre: is called before visit post: after visit edges will be named edges to identify the relationship So what do you think about that design, are there any flaws in there I didn t detect already? Any suggestions to improve it further more?

Share this post

Link to post
Share on other sites
It looks a little unnecessarily complicated. Does there really need to be a root to hold all these different representations? I’d say it would be better to keep all different representations more separate & loosely coupled than what you have there.

Each subsystem will want it's own particularly type/kind of information, a view of the scene data organized in manner for efficient queries, some of those views can be shared between some subsystems.

Like take for instance a large static mesh, an efficient spatial data structure for rendering is going to be sub-optimal or poor for collision detection, in which case you'd be better off with two different kinds of spatial data structures which just references the same data using say indices into faces or similar, use events/signals to synchronize the views.

I'm not so sure if you need to logically separate out dynamic objects in an explicit manner unless this is a spatial organization and not a logical one. I'm also not sure if you really need a separate hierarchy of lights unless there is something obvious I missing here.

Personally i'd start with a typical scene graph which is has events/signals and then have multiple views referencing/indexing into the data, (which we kind of do at work).

I have to say though I have been thinking about the use of more general graphs for scene graphs (those not restricted to just DAGs/trees) and using edge/link annotations to denote the kind of link being made, like ParentChildLink, PortalLink, etc, etc. I would definitely be interested to hear what others think of this. I would still keep things like spatial data structures as separate *views* of the main graph.

Share this post

Link to post
Share on other sites
The reason I seperate the lights from the quadtree is that you only need the spatial hierarchy of the lights to determine the the light<--*> object relationship(whether a light affects an object or not)

Moving the lights into the quadtree would increase the number of type lookups via RTTI which slows down tree traversion in very large scenes

The quadtree there is just for graphical representation of dynamic and static objects.

As for physics, the way I see it is that physic engines hold their own SG like structure, so there s no need for me to do so.

you are right dynamic_objects could be removed for now, but on the other hand why not pack them into the SG, maybe you want to loop through all the dynamic objects, they don t really matter, they are just there until you delete them

Thinking a little more about my design and your suggestion of "views", actually my design is some sort of implementation of views, the seperated DAGs work like indices into a database and notification back to the parents represent the message/signal system you proposed

[Edited by - Basiror on May 20, 2007 10:56:28 AM]

Share this post

Link to post
Share on other sites
Since I am combining my shaders at runtime I could also put the whole render pipeline into the scene graph

Here you seen an example with bruteforce rendering and parallax mapping as potential light models.
Its of course only a rough overview of the real graph.

1 digraph{
2 root->lights;
3 root->dynamic_objects;
4 root->quadtree_root;
5 root->lightmodel;
7 edge [color=Red, style=solid]
8 lights->{light1;light2;light3;light4;light5};
9 light1->{terrainpatch1; crate; stones; wood; car};
10 light2->{terrainpatch1; wood; tank};
12 edge [color=Green, style=solid]
13 quadtree_root->{ quad1; quad2; quad3; quad4};
14 quad2->{ terrainpatch1; crate; stones; wood; car};
15 quad3->{ tank};
17 edge [color=Blue, style=solid]
18 dynamic_objects->car;
19 dynamic_objects->tank;
21 edge [color=Orange, style=solid]
22 lightmodel->{parallax; bruteforce};
24 edge [color=Gold, style=solid]
25 parallax->{shadow;view_cull;para_shader;atmosphere;ppl_shader};
26 bruteforce->{dot3_shader;fog_shader};
27 shadow->lights;
28 view_cull->quadtree_root;
29 }

All the seperate subtrees (children of root) can be considered seperate trees as suggested in
Scene Graphs: Past, Present and Future

Now all you had to do is to write a few classes that interpret the subtrees(not a big deal)

The named edge approach should take care about false notification, just filter notifications that don't have an influence on a relation between 2 objects.
The example underneath demonstrates the use of edges as notification filter, which reduces the overall graph traversal time to a minimum


void is_in_lightvolume_edge(light1,car)::notify(uint32 signalid)
if(signalid != sig_obj_moved || signalid != sig_obj_deleted)

void light::notify(uint32 signalid, obj_node)
if(signalid == sig_obj_deleted)
else if(signalid == sig_obj_moved)
//test against light volume, on failure notify parent node

void light_partition_node:notify(...)
//propagate up until the subtree root node "lights" in our case
// on failure the obj_node is not inside a light frustrum anymore

Share this post

Link to post
Share on other sites
My engine use the idea described by snk_kid, that is to say the scene is described by a scenegraph like data structure and all the interpretation of this data structure is delegated to views.

In particular, the scene data structure does not hold any information for culling (be it view culling, light influence culling, sound influence culling,...), or rendering.

I live happilly with this design (which has its limits like all designs) therefore I'm not too sure about your design proposal since it mixes lots of informations in the base data structure.


Share this post

Link to post
Share on other sites
Well my primary aim is to reduce the traversion cost to a minimum

How exactly do your "views" work? Like in databases? Where you declare a views a a query with some constraints?
If you don t you have to cache the results of view's query until it becomes invalid?

If so you would end with the same concept as my graph above, with one difference, invalidation of a tiny part of the data doesn t invalidate the whole result set of the view and thus costs less processing power to update the graph

So a view would be a DAG or in the language of databases an index.

Or do you query all the information each frame? If so isn t that a little costly?

Share this post

Link to post
Share on other sites
The design is based on the following definition of a node ; a node is an abstract object that has a parent, can be extended through flexible extension point, and which changes can be listened to.

All the rest of the game engine exploit this extension / listening system.

For example, the video renderer defines one extension point (per video renderer). This extension is dynamically created and is in charge of handling the rendering of the node (This extension may choose to listen to the node it extends and only react to change or to update its rendering commands every frame).

Another example is transformation ; transformation is although handled using the extension system. The extension is linked to a root matrix provider (most of the time it is the view matrix) and it provides the model-view for all nodes with minimal overhead.

Another example is culling ; there is no culling in the scene nodes ; culling is performed by an external culling system which likely will have to extend node in order to have them hold their culling information.

The node's extension instance are created through a per extension id factory. Lots of these factories defers to a plugin system to handle this instantiation ; they choose the plugin to use based on the class of the node and on the context (for example, which OpenGL extension are available).

The interesting thing with this design is that your scene node are very stable ; it's been 2 years I've been using my engine, there has been a lot of refactoring of its internals but the client application was very lightly impacted by these internal modifications.

Share this post

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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!