Ok, so I’ve read all kinds of stuff about scene-graph design. Then, using all kinds of really good object oriented techniques I’ve created my own. Now after many simple tests I’m ready to render a complex scene. Using my render visitor, I can easily iterate through the hierarchy getting all of the render states, geometry, lights, transforms, effects, and more in the correct order to draw the scene. Well… not really. The scene-graph is just a dependency graph which is not useful for culling and sorting of the geometry during the actual rendering. Obviously, some geometry needs to be rendered in correct Z-order for transparency and other geometry needs to be sorted by effect, or texture for efficient rendering. The scene-graph is a great tool to manage the relational and state information but obviously there are other components needed to make this system work. I have a few ideas on how to do a lot of this but I’d like to know how other people have done it. I’d also love to hear thoughts on how an octree could be used for culling and render order in conjunction with a scene-graph. [Edited by - Scythen on December 16, 2004 5:25:37 PM]

What I do is make the scene nodes that contain the transforms a separate class from the actual models being rendered. You can have a SceneNode object and can attach Renderable objects to it. What you do is traverse the scene graph and make a list of all renderables then sort those, after all the scene hierarchy transforms have been applied.

Quote:Original post by Scythen
The scene-graph is just a dependency graph but this is little use for culling and sorting of the geometry during the actual rendering. Some geometry needs to be rendered in correct Z-order for transparency. Other geometry needs to be sorted by effect, or texture for efficient rendering. I believe the scene-graph is a great tool to manage state information but obviously there are other components needed to make this system work.

I think you are a bit confusing about scengraph...

There are many part of scengraph:
but the first thing to keep in mind is that the scengraph store logical information and relation about the geometry.
So when you render, your engine should group the part of geometry that use the same material (for example) and sort the transparent object by z and so on.
The scenegraph is not used to resolve this type of problems.
Bye,
Davide

A scenegraph is a great tool for storing your 'world' in a manner that's intuitive to the developer(s). Things make sense, hierarchies are easily moved, relationship are logical.

Rendering requiers a different approach. So, basicly your walk the graph, like you do already, and sort out the geometries.

You could refer back to your scene nodes from within your renderer, but depending on your implementation of transformation, that link might grow stale soon: placing a rocket inside an octree might prove troublesome, for instance.

hth
CipherCraft

i found culling was very easy to implement in a scene graph.

as you traverse your graph you concatenate all transformations recursively and store the result. this gives you the camera space position of all your nodes. based on those coordinates you can use pre-canned arctan values to see if the node's bounding volume is within your camera frustum. I found that implenenting my transformations using the opengl matrix operations and stack offered high speed, and the ability to re-use the transformations in the rendering pass, removing some unnecessary redundancy. This also gives you Z-order for transparent objects (on an object basis though, not a poly basis).

furthermore, if you make a bounding volume node for each object node which is tight, and at every branch with object nodes as children have another bounding volume which tightly fits all the children, you can quickly cull entire object heirarchies from your scene with no spatial partitioning schemes. you can also use the camaera-space positions and bounding volumes to do fast object-based occlusion culling at little additional cost.

once you've determined the transformation for each object, and whether its visible or not, you can add it to a render-queue and then do your material sorting or whatever you need on that queue.

James Gregson

Quote:Original post by silvermace
TIP: use an std::list to store your rendering que, insert objects that need blending using push_back, and objects that dont use rendering using push_front. what you're left with is all the opaque objects in the front of the list with all the transparent objects at the back.

Your probably better off using std::deque for that as its constant time insertion and removal of elements at each end of the sequence, other alternatives are to use std::priority_queue, or if you need more flexiablity you can use STL heap operations with containers that support random access iterators.

Wow, some great suggestions here.

I particularly like the tip by silvermace and snk_kid on simply using a list or deque resulting in a list of renderables with opaque first then transparent.

Unfortunately, the simple deque solution by its self only deals with z-sorting which still leaves affect and texture sorting to be done later.

Then there is the suggestion to use a priority queue.
Thinking this one over, it may be the way to go.

The comparison used to sort the priority queue could be based on several values which would be weighted, so transparent objects would always have a lower priority than opaque objects. This would result in a priority queue sorted based on all of the relevant attributes.

Thinking about the octree again, maybe this would be useful after all. Depending on the scene layout, there may be a large number of objects at the root of the scene graph. Simply using bounding volume checks to frustum cull would mean a lot of work. If I were to set up a loose octree with the scene-graph nodes as the data I could use it to set visibility flags for the scene graph prior to the render traversal.

So rendering a frame would go something like this:
Update all dirty transforms and bounding volumes in the scene graph (not a full traversal).
Reset visibility flags for the last frames visible objects.
Traverse the octree turning visibility flags on for non occluded voxels.
Travers the scene graph visiting nodes with visibility set to true.
Concatenate transforms during traversal as suggested by Anonymous Poster.
Add visited renderables to the previously mentioned priority queue.
Render objects in the priority queue.

I guess the question then becomes which takes more time, upkeep and traversal of the octree or bounding volume occlusion checks for a large number of culled objects.