Hi

I think that any engine would be "lazy" like haskell. So in low level you would have a directed graph where the nodes represent values (or attributes) and the edges represent the dependicies between attributes. Also each attribute would have a state (updated or outofdate). When one trys to read an attribute if its state is outofdate then a graph traverse is done to update the attribute. When theres a attribute change the state is set to outofdate and then its populated through the graph. This results in some overhead but prevents many recalculations per frame. Here the attributes would be primitive values (int, float, string, ...) and composite types (matrix, mesh, ...).

The scene graph would have nodes and edges (the same as before but with other semantic). The nodes would be functional entities (nodes that perform actions) and the edges define the path that the renderer performs. The scene nodes have attributes and can be connected to/from other attributes of other scene nodes.

There are some catches here specially if the graphs can be cyclic or acyclic.

Also, there is lots of inspirations here taken from the Maya's scene graph. If you have Maya installed check out the documentation.

João Barbosa

Quote:Original post by Promag
... there is lots of inspirations here taken from the Maya's scene graph.

And that is probably dangerous, Maya's internal representation as of current is most likely to be infeasible for games. Maya gives alot of slack/flexibility for artists, alot of "junk" is created in the background that eventually needs to be 'cleaned-up'/optimized an inheritantly slow & non real-time operation [wink].

Sure scene graphs are typically directed acyclic graphs (DAGs) or n-ary trees in game engines but trying to replicate alot/all of Maya's internal structure/s is most likely asking for trouble. At the end of the day the requirements for a 3d modeller are not quite the same as they are for a game/game engine even though the share some characteristics.

Saying that though re-using some of Maya's concepts like there shader system isn't half a bad idea.

Well yeah, Maya API was designed for modeling application, not for game engine. That "junk" is due to history system and and stuff like that not present in a game. But the lazy concept and the way the objects and shaders and transformations and "..." are shared in the dag is pretty good. This also requires a very good algorithm to traverse the dag.

The attribute graph itself is a nice way of caching and its usefull for scripting systems. Each scene graph node exposes its input/output attributes.

Also one could set diferent manager to diferent types of nodes and the traverse algorithm would use the proper manager when visiting a node. For example, a spatial node would have a manager that performs frustum culling. And if one sets a chain of managers then this would be like a rendering pipeline. Just a thought.

João Barbosa

@Zemedelec, let's not get into the sort of discussion we had before :) I picked "hardcode/hacking shadow mapping" from a post in this specific thread.

@paic: To me, "shader based" renderers (not the GFX API shaders) means simply "objects are assigned shaders and the renderer does what it has to do with the objects its given". Shadow mapping could be implemented by assigning a shader to an object saying "the object I'm on wants a shadow map from light #123 using a shadowmap shader". The renderer will queue that light with the shadowmap and in the final rendering traversal, all shadow maps will be computed and later used for other objects.
The only ways the scenegraph interacts with the renderer is by giving the renderer objects to render and maybe give shaders information about lighting close to objects.

@Paic: Overall your design sounds pretty good but you should be careful not to do too many "visits" of nodes that doesn't need to be visited. For example, if your scene-graph contains many nodes that should not/can not be rendered then it could introduce quite an overhead to visit them in the graph each frame to collect nodes for rendering. The same goes for an "update" pass through the graph - if you have many nodes that does not overload the update function from a base class (for example) then it'll be an overhead to visit them each frame. The overhead could come from the additional traversal time as well as the fact that you'll visit more memory and thus probably get more cache misses.

We just release our first 3d game for PC, PS2 and Xbox and one of the things we'll change for the sequel is exactly the way we traverse the scene graph. For this game we did it pretty much the way you described - but we have many "logical" nodes that are only used to implement some level design or to group nodes ("folder" nodes in the tree). There are several ms per frame wasted by doing a full tree traversal compared to when we extracted certain nodes to linear lists that we have beside the scene graph. For example we have a list of all those nodes that we know we'll call "update" on each frame and so on. For rendering we have a seperate tree that contains only the sub-tree of the scenegraph that are the nodes that can be rendered.

But you also loose some power by using extracted lists. For example it's harder to control the order of updates or for one update to trigger the update of its nodes children.

Regarding the sorting: this should *definately* be done after the visible nodes has been retrieved somehow. Why? Because different rendering techniques or even different rendering passes will want to sort the nodes/geometry-bits differently.

Hope this helps a bit..

- Kasper Fauerby

About the overhead; Yeah, that's exactly what I'm talking about. Of course it all depends on the scope of the engine you're creating. You need a pretty big scene tree before you'll see the overhead - probably a larger one than you'll create in any of your test scenes if you're not doing a full game. So it might very well be that you could ignore the overhead. On the other hand, assuming you do this as a learning process and with the intent of doing something that *would* be good enough for a full game (and I guess most hobbyists around here develop game technology for exactly this reason) then you might as well think of this problem now :)

One way to avoid the overhead could be to extract certain nodes to different lists. So for example you might have a list called: 'UpdateEveryFrame' where you add all nodes in the scene that needs to have their update function called every frame. Then you might have another list called 'UpdateThisFrame' that nodes can put themselves into (or be put into) if they want/need an update this frame. This second list you process each frame after you process the 'UpdateEveryFrame' list - but you clear it every frame after you've processed it (do a 'while not empty' loop instead of a for-loop as nodes in the list could add new nodes to the end of the list). This is *one* way to avoid the traversal overhead but as I mentioned it introduces other problems.

- Kasper