In my engine, I initially wrote a straight forward renderer that was the usual walk done the scenegraph tree => store in render queue => sort render queue => render.

Then I moved to a more advanced renderer that performs only "delta" updates. The rendering is now processed this way ;
1 - update culling and call enterRenderFrame / exitRenderFrame on nodes entering/exiting the visible area (they usually add render item to the render queue),
2 - process update queue (nodes that are in render frame are allowed to ask for updates, when they do so, they are stored in this queue),
3 - sort render queue
4 - render.

This modification gave me a huge speed boost on my game. Here is the way I can explain it ;
- The step 1, allows me to use custom culling method adapted to the game.
- The step 2 is better than in the straight forward renderer since you only process updates od nodes that have changed since the last frame, in my game, this is usually a very small part.
- For the step 3, I use a quicksort algorithm which is O(n) when elements are presorted which is the case for most frames due to frame to frame coherence. It is enough for my needs but you are right in your post ; this could be made better by performing part of the sorting each frame, therefore allowing advanced sorting schema (I only sort by shader / texture since it appeared that evaluating other state, distance to camera happened to make me loose performance, this could change if sorting is performed accross a few frames).
- Memory wise, you avoid to allocate / free loads of objects.

Note that the change to the "delta" renderer was a rather big task ; it is fairly difficult to have a bug free synchronisation system, to ensure this I had to add an assertion system that check that after the update (step 2) all visible nodes are up-to-date.

In short, I would answer to your original post that, yes, for me, reusing the render frame happens to be very efficient, but if the performance you get with a straight forward renderer are enough don't go this way because it makes the engine far more difficult to maintain.

Vincent

Quote:Original post by shaquill
...

1. Sorting can hardly be the bottleneck, or even take some noticeable time. If implemented right - having all keys packed into aligned structure, don't use floats, pointers, etc. Don't copy objects, just move these small keys around, when sorting - you'll need a index to the key's object, of course.

2. You can do sorting every N frames, and between them simply add new objects at the end of queue. N can vary dynamically, based on the movement of the viewer, for example.

After searching a bit more on sorting ;
- First, I was wrong stating that quicksort has a best case of O(n) ; the best case is O(n.log(n)).
- Second quicksort is not stable which is not that good since this means that you keep performing useless swaps.

I found reading the wikipedia article very interesting. I think the perfect sort algorithm in this design would be a stable sort, that can be processed incrementally (i.e. process 10% of the nodes each frame for example), with a best case of O(n).

Anyway, the fact is that, as Zemedelec stated, sorting is not that costy. In my game, the main interests of keeping the render frame are mainly the other ones I have stated in my previous post.

Vincent

Quote:Original post by Niwak
- For the step 3, I use a quicksort algorithm which is O(n) when elements are presorted

Ouch, feel the pain.
Quicksort runs O(n lg n) in the average case, but O(n^2) on presorted data.

That's about the least efficient sorting algorithm you could possibly use in this case. A simple bubblesort or something would be much more efficient (Since that approaches O(n) time on presorted data)

Quote:Original post by Spoonbender
Ouch, feel the pain.
Quicksort runs O(n lg n) in the average case, but O(n^2) on presorted data.

That's about the least efficient sorting algorithm you could possibly use in this case. A simple bubblesort or something would be much more efficient (Since that approaches O(n) time on presorted data)

I think the topic is slightly away from a discussion about sorting algorithms... :)
Bubblesort will do fine, only if applied over the data from the previous frame, but then we must implement removing of not-seen-anymore elements and adding new ones.

Quote:Original post by Zemedelec

Quote:Original post by Spoonbender
Ouch, feel the pain.
Quicksort runs O(n lg n) in the average case, but O(n^2) on presorted data.

That's about the least efficient sorting algorithm you could possibly use in this case. A simple bubblesort or something would be much more efficient (Since that approaches O(n) time on presorted data)

I think the topic is slightly away from a discussion about sorting algorithms... :)
Bubblesort will do fine, only if applied over the data from the previous frame, but then we must implement removing of not-seen-anymore elements and adding new ones.

I would say that once you're beyond discussing using temporal coherency to optimize multi-frame sorting, the efficiency of the sorting algorithm you choose is of primary importance. Quicksort, as mentioned, has pretty much its worst performance on data that's already sorted. Choose something else.