Jump to content
  • Advertisement
Sign in to follow this  
Xycaleth

OpenGL Temporal coherence and render queue sorting

This topic is 1450 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

I've seen this mentioned a lot in the past (and again more recently by L. Spiro in this thread) where you take advantage of temporal coherence between frames so that you don't have to perform a full re-sort (I'm not sure what the best terminology for this is) on the queue. The idea being that between frames, objects will be more or less in the same order as such a small time has passed.

 

But how is this achieved? If you use your already sorted list, how do you know which (renderable) objects in the list should be removed (e.g. because they were culled)?

 

My first idea would be something like this:

  1. Iterate through sorted list, check if culled. If not, keep it. If it is, remove it.
  2. Traverse through spatial tree (or however your scene is partitioned) and add objects which need rendering - have to check list for duplicates though!
  3. Then we can sort the queue.

But step 2 doesn't seem very efficient if you have to iterate the list a load of times to check if the object already exists.

 

As I write this, I realise you could add two extra fields to each of the objects to say in which frame it was last rendered, and when in which frame it was last removed. Then checking for existence in the list can be a simple lastRenderedFrame == currentFrame - 1 && lastRemovedFrame < currentFrame. You'd also need to update the lastRenderFrame field when you add it to the queue (step 2), and update the lastRemovedFrame when you removed from the queue (step 1).

 

Am I on the right sort of lines?

Share this post


Link to post
Share on other sites
Advertisement

Repeat the process from the light’s “camera” (view and frustum).  Store results in a render-queue assigned to that light.

 

 

L. Spiro

Share this post


Link to post
Share on other sites

How do you deal with sorting of transparent polygons that belong to the same sub-mesh?

 

Also, why do you have to reset the sort order to 0, 1, 2, 3, ... N when the new render queue is shorter? Wouldn't it be faster to just remove the no-longer present sub-meshes and leave the existing sub-meshes sorted?

Edited by tonemgub

Share this post


Link to post
Share on other sites

Wouldn't it be faster to just remove the no-longer present sub-meshes and leave the existing sub-meshes sorted?

Try to imagine what steps need to be taken to remove existing indices or to build a new array without these indices. Now compare that to creating an array from 1, 2, ... N.

Edited by Mussi

Share this post


Link to post
Share on other sites

How do you deal with sorting of transparent polygons that belong to the same sub-mesh?

You don’t with this algorithm.
In practice that level of accuracy is never needed.  It’s more important to draw triangles in the same order rather than in a specific order.  As long as they don’t jitter the player won’t notice that the blending is slightly wrong just because they were drawn in the wrong order.
 

Also, why do you have to reset the sort order

See above (Mussi’s reply).
If you have 1,000 objects and then the next frame you have 1 object, the list is still sorted as long as the list is just index 0. Now, think about how to detect that. A generalized algorithm will only help in a few situations if you just happen to get lucky enough that all the removed indices are ones you didn’t need, and in every other case time spent trying to detect that is just time wasted.
Restarting the index list is a bit of a cost but it’s sorted again after only 1 frame, so it’s the best general case.
 
 
L. Spiro Edited by L. Spiro

Share this post


Link to post
Share on other sites

Try to imagine what steps need to be taken to remove existing indices or to build a new array without these indices. Now compare that to creating an array from 1, 2, ... N.

You can do both in a single iteration over the array. To remove an index, you find it's position in the array by comparing each array value with the index, then in the same iteration, move all subsequent elements back by 1 for each removed element. So you just do array = array[i + number_of_removed_indexes_found_so_far] instead of array = i (number_of_removed_indexes_found_so_far will initially be 0).

Assuming that that the number of indexes removed each frame is small in comparison with the total number of indexes, this might be faster than re-ordering all indexes and breaking the coherence?

 

Even if you don't want to keep the remaining indexes sorted, array = i seems like a waste of CPU cycles for some reason. Wouldn't it be faster to just keep something like a "mustSortAll" flag - set it to TRUE when indexes must be removed, and the next frame, if mustSortAll is TRUE, you use the i = 0...N indexes (the iterator values) directly in the sort, instead of setting and then reading back the vector values (which are going to be the same as the iterator values anyway)? smile.png

 

 

 


If you have 1,000 objects and then the next frame you have 1 object, the list is still sorted as long as the list is just index 0. Now, think about how to detect that. A generalized algorithm will only help in a few situations if you just happen to get lucky enough that all the removed indices are ones you didn’t need, and in every other case time spent trying to detect that is just time wasted.
Restarting the index list is a bit of a cost but it’s sorted again after only 1 frame, so it’s the best general case.

Good point. Then how about a middle-ground algorithm: If the number of removed items is relatively small, you just keep the remaining indexes sorted. Otherwise, you re-sort everything next frame (using my flag idea above).

Now all we need is the formula for the "relatively small" threshold - it could probably be determined by testing, though I think it's going to be a logarithmic value. (I'm not good with big O calculations).

Edited by tonemgub

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!