Jump to content
  • Advertisement
Sign in to follow this  
shaquill

should I keep rendering queue?

This topic is 4345 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. I'm making rendering queue and sort by shader, vb, texture... First I thought I should renew the queue every frame. But I read that transparency sorting doesn't need to be sorted every frame for example. Becuase not so much different between current and next frame. Then I think I should keep previous rendering queue and add/delete when it changes and sort. Becuase if the queue is sorted at once, Next sorting time will be shortened I guess. So I'm thinking keep previous rendering queue and transparency queue, too. Is that right? I want to hear anybody's thought. thanks.

Share this post


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

Share this post


Link to post
Share on other sites
Seems a pretty good system Vincent.

One advice tho, quicksort is very inefficient with nearly sorted list (I don't remember it to be O(n) in that case, cause usually it will take the first element as splitter and thus it will divide the next recursion with most of the element on one side and nearly none on the other, not very efficient). You should consider randomly rearranging element before sorting, or search for a sorting algorithm optimized for "nearly sorted list".

Hope it will help...

Share this post


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

Share this post


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

Share this post


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

Share this post


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

[/quote]

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.

Share this post


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

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!