I have multiple question about ordering the scenegraph before rendering: 1) What is the benefit of ordering a scenegraph ? The only reason for me was to sort object by there distance from the camera because of blending problem without that and i was thinking that if we wants to sort the object we are going to increase the number of call to glRotate, glTranslate etc etc ... 2) How can we efficiently order the scenegraph at each frame without multiplying the number of call to glRotate glTranslate and so on ... ? 3) If we wants to do this kind of thinks we must calculate all the object position in a first pass and order the scene graph in a second pass and render the scene in a third pass ?

The best reason to order your graph is to avoid state changes (like sorting to group all like textures together).

The way I do this is by keeping two scene graphs, one holding the structure of your scene and another being a simple list of pointers to your renderable scene objects. You can traverse your scene graph normally to compute all world transforms and render state changes, and then traverse the sorted render list to draw your scene effeciently.

You can presort the render list so you don't have to do it per-frame. You can determine what to draw then by keeping a bool in each renderable that represents visibility.

Hope this helps.

That is exactly the problem I was dealing with a little while ago. I am still figuring out the best way to deal with my scenegraph. But I came to the conclusion that ordering it by, say, material as top priority isn't efficient. I thought that computing all the matrices would be slow, but I'm not sure anymore.

I'm going to do some tests soon. Maybe it is better to sort primarily by material, and compute all matrices like boebi.

Boebi: do you go through and compute all the matrices in opengl and then call getfloatv? Or do you use your own matrix class and then simply call loadmatrix?
Also, what happens when a position of a parent object changes? Do you traverse your spatial scenegraph every frame and recompute an object's matrix and all of its child matrices?

edit: rephrased

I'm using the DirectX Matrix class for all my transforms. I guess, in OpenGl, that would be like using your own custom class.

Each node has local and world transforms. I traverse my scene depth-first and use a matrix stack to concat my matrices as I go. Each node is assigned its world matrix at this time. I keep track of movements in a node (anything that'll change a transform) and I have that node tell all of its children that they need an update. I only perform matrix updates on those nodes that need an update themselves or have a parent that has been changed. This is done on a per-frame basis.

Sorting by texture and material/shader (in that order) has worked well for me. This isnt a per frame operation, so it doesnt take much CPU time. You only need to resort your render list when you add or remove nodes.

This approach has worked well for me in maintaining a complex scene graph while also being able to sort my rendering ahead of time. I have managed to increase my framerate on my test scene (which is pretty small) from about 100fps to 300fps on an ATI Radeon 9700.

Cool, that's exactly what I wanted to hear. Now that I know someone else has implemented the idea (and is pleased), I definitely want to try it out myself.

I'd be interested in hearing what happens in your test application when you increase the scene complexity, e.g. many many relatively small objects that each move around? It seems like the system might slow down here, whereas spatial ordering wouldn't be hit as much.

Then again, with spatial ordering, you always have to completely traverse through a tree (that is most likely going to be very complex). And with the increase of objects, that still means an increase of state switches, so it would probably get bogged down just as well.

With a material-based system, every frame traversing through the tree completely is a worst-case scenario. Most likely you only have to traverse parts of it. And then simply loop through a simple list. Now that I think about it, sorting by material would probably still save time even with the overhead of computing all the matrices.

That's very cool, I look forward to testing it. I've always hated being bound by the hierarchial transformations.

I implemented this algorithm specifically because of more complex scenes. I expect that in a scene with a large number of objects, the texture sorting will really help out on switches. The cool thing about this engine is it is spacially sorted and material sorted, because I maintain two scene collections.

Please let me make this clear, I don't sort the scene graph. The scene graph simply maintains the spacial relationships. I have a separate render list that is comprised of pointers to the renderable objects in the scene. That is what is sorted. And it only needs to be sorted when a node's texture is altered, or a node is added/removed. This is where the boost in speed is coming from.

If you combo this with some octree structure for fast collision and such, Im sure youll be in great shape.

EDIT: @Just like CoffeeMug said above

Quote:
The thing is that if you just add the node to the right place instead of actually sorting the loop, you get this practically for free

What is the right place? Are you talking about inserting it into the scenegraph or the ordered list? I'm not quite sure I follow if you mean the scenegraph, because you need to describe how you render your scenegraph with hierarchal transformations, yet primarily ordered by materials. I don't see any other way of doing this then what boebi suggested (or any other way that's drastically different).

That's a good point about shaders. I'm still deciding what is going to be the list of priorities, but I'm not too worried because the system should be built so that I can easily play around with them (change what it sorts by) for fine-tuned optimizations.

edit: I'm also researching how to incorporate offscreen renders. I think it will be a new 'scene' in the sense that at the highest level of of scene managing, I will have a list of needed rendering buffers. Associating with each buffer is a 'scene,' or simply a pointer to a head node of a tree. So for shadow mapping, I will register a new pbuffer, and basically register the whole scene with it also.