Jump to content
  • Advertisement
Sign in to follow this  
Borgleader

Are scene graphs worth it?

This topic is 2507 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,

in the past for a school project we were given a game engine framework containing a render tree/scene graph for placing objects in the scene and rendering them. And until now I thought this was the way to go, but now that I'm working on a very simple engine of my own I started to do some research and I've come across contradictory reports. Some people seem to say that scene graphs are quite useful and some say the opposite.

So my question is, are they worth it? What are the trade offs of having them versus avoiding them? Is it possible to use acceleration structures such as octrees (for physics) further down the line if I don't use a scene graph?

Thank you.

P.S: I hope this is the right forum for this question.

Share this post


Link to post
Share on other sites
Advertisement
The definition of a scene graph is extremely fuzzy, so it depends on what you think a scene graph is and what you want to do with it.

In essence, a scene graph is just a hierarchy of entities or actors such that actors can be parented under other actors and the parent’s transform is added to them. This part is actually essential. You can’t put a sword in the enemy’s hand unless you can set the hand joint as the parent of the sword.

But does a simple hierarchy of entities/actors constitute a scene graph? For using a fancy term such as “scene graph”, people generally expect more functionality than that.

Enter OpenSceneGraph.
This library claims to speed up rendering, perform frustum culling, etc. Some scene-graph libraries claim to handle physics and OpenSceneGraph has tied-in support for OpenGL.

Did I miss something?
Where did the scene graph end and the game engine begin?


Physics is the job of the physics library.
Rendering is the job of the rendering library.
Spatial partitioning is the job of the scene manager, and is only used to feed information into the physics library in a more efficient manner.

I would never leave my rendering or physics in the hands of a library that was mainly designed to organize world objects in a parent/child manner.


In general, a scene graph is a horrible idea, because it is specifically designed to overstep its boundaries. The only thing it should do is provide a parent/child relationship between objects, but that isn’t a scene graph, it is just a hierarchy of objects.


Make a hierarchy.
Make a renderer.
Make a spatial partitioning scheme (yes, you can, without a scene graph).
Make a scene manager.
And keep them separate. They work together but they are separate systems. Trying to tie them together to make a scene graph is simply wrong.


L. Spiro

Share this post


Link to post
Share on other sites
As a scenegraph is a graph or tree(a tree is just a specialised graph) representing your scene an octree storing your entities is a scenegraph, heck, even a linked list containing all your entities could be considered a scenegraph (a linked list could be considered a graph where each node is linked to at most one other node)

Making a scenegraph that is more than just a scenegraph however is a bad idea (single responsibility principle) and something far too many scenegraphs are guilty of.

Share this post


Link to post
Share on other sites
Good suggestions so far. But for all practicality, you could just consider the manager a graph.

We use our "SceneGraph" to manage the scene. This includes the transformation hierarchy, the spatial partitioning, the physics interface.
Our game logic operates on a scene graph, and so does the rendering engine.

Inside the renderer, things are very tree like. You have render targets, and view ports, and materials and shaders, and buffers and batches, constants and parameters, so on and so on. All of that stuff is isolated from your scene graph or scene manager. You could call it the render graph. Because indeed every frame you will render a graph of state changes.

If you want to know about accelerations structures then yes there are all kinds. You could use portals, quad trees, or we use this:
http://publications.dice.se/attachments/CullingTheBattlefield.pdf
http://research.scee.net/files/presentations/gcapaustralia09/Pitfalls_of_Object_Oriented_Programming_GCAP_09.pdf

I have implemented the transformation tree version of that. It's a little bit of a question mark still, since you can't store a reference to your transform. Which sounds like it might be difficult to avoid. And difficult to avoid causes bugs. however, we were able to recalculate the entire scene's transformation hierarchy in the time the previous implementation would update only the dynamic objects. that's another issue, separating dynamic and static objects. cache dynamic transform changes, and flush them all in an instant. complicates game programming a bit.

We use a Kd tree for fast triangle ray casting. Sweep and prune for overlapping pair lists. Structures of array frustum culling and displaylist generation. There are quad trees for generic instant queries. They all more or less connect through the scene graph.

The stupid idea about putting a texture in the scene graph should be forgotten about and scribbled out of history by now. That thing should be called the render graph. Render monkey has one. You put assets in a tree, you give it children to fill the assets. The scene is much different.

Sorry i just started spewing stuff i thought you might be interested in.

Share this post


Link to post
Share on other sites
Shameless plug:
http://www.beyond3d.com/content/articles/98/
http://www.beyond3d.com/content/articles/102/
http://www.beyond3d.com/content/articles/109/

I wrote that series about 3D Engine Architecture back in 2007, most of it is still relevant, there's a talk about scenegraphs at the beginning.
Most commercial engines follow a similar pattern. (Not all, I'm looking at you StarCraft 2 and your slow draw as you visit scenegraph nodes :P)

Share this post


Link to post
Share on other sites
Wow thanks for all the great answers :) And thanks for all the links, those two .pdfs were particularly enlightening. I had seen some of this in my Processor Architecture class 2 years ago (memory alignment, cache misses, branch prediction, ...) but I'm pretty blown away by the performance impact they can have, even a simple if(!dirty)

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!