A quick thought about sort...

[CodeGen]

Hi!
I just thought about little render queue sorting optimization. Usually, in each frame we find visible objects, put them into render queues, sort them in order to minimize render state changes and finally render them. But in typical scenes, maybe, about 80% of what was visible in the current frame is likely to be visible in the next frame. How can we use this information?
Wouldn't it be better to try to keep objects in the render queue and remove them from there only when they are culled? Renderables will form nearly sorted islands inside the render queue, there exist sorting algorithms which perform very good on partially ordered data (e.g. radix sort, insertion sort, some people say Timsort is brilliant in this aspect). And to sort transparent stuff properly we need to invalidate their sort keys whenever view changes and we will only need to loop through objects inside the render queue, no need to iterate over all scene entities. For effective caching of render entities we may need to enclose our conventional pyramid frustum with a cone superfrustum (so that it's easy to test objects' bounds against it), renderables will be removed from the render queue only if the corresponding entities are found outside the superfrustum (objects inside the superfrustum, but still not visible will be marked CULLED and we will skip rendering them). To quickly find if an object is in the render queue we can use hashing or bloom filters.
What do you think, will that improve speed?

[CuteAlien]

Sounds like it would improve speed in the typical case but make it worse in the bad cases. It probably would be good as long as your camera speed is guaranteed to be below a certain delta. I prefer to care more about the worst case because that is more important to get a fluent framerate.

So this sounds to me like a good optimization for some games, but not that good for a general engine.