Sign in to follow this  
Snatch

Ordering the scene graph

Recommended Posts

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 ?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Why sort the scene graph? Just use some spacial partitioning scheme with nodes pointing to scene graph objects to create a queue of objects you need to render. You then use the scene graph to add hierarchial dependancies to the queue. Once you're done creating the rendering queue, just sort it (or sort on addition if you like) according to whatever criteria you find appropriate (experiment) and then render the entire queue of objects in one shot.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by boebi
And it only needs to be sorted when a node's texture is altered, or a node is added/removed.

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 (O(log N) node addition aka *really fast*). You shouldn't sort by textures though. Modern graphics card have significantly more expensive context switches. You should look at the optimization docs from ATI and NVidia but switching shaders is slower than switching textures. Bottom line is, just sort by *material* (that includes shaders, textures, etc.), and then by lights. Another huge speedup is managing vertex and index buffer memory manually instead of using a small buffer per object. Buffer switches are slow, so generating large buffers for holding multiple objects that are usually rendered together can be a lot more efficient.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by okonomiyaki
What is the right place? Are you talking about inserting it into the scenegraph or the ordered list?

Into the oredered list. I call this a render queue. Every frame the list is cleared and objects that need to be rendered (according to visibility, occlusion and scenegraph) are inserted into the list. Upon insertion the list makes sure the object is inserted in the right place. Priority queues (heaps) are perfect data structures for this purpose. Once all objects are inserted, you simply grab them from the render queue/list and throw them at the GPU using your API of choice.

Share this post


Link to post
Share on other sites
Why not go the logic way?

Scenegraph - logical information about scene data. Note that not all data is renderable

Rendergraph - renderable data

Render queue - list of renderable items which can be sorted on some criteria (since this is multidimensional problem use any criteria and test, test, test)

Change in scenegraph issues rendergraph rebuild. Render queue is cleared, filled, sorted, flushed. Repeat.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this