I loved whole L. Spiro's post, but I have something to correct

Sorting 2 smaller queues is faster than 1 big one.

This is a half truth.
Sorting can take:

• Best Case: O(N)
• Avg. Case: O( N log( N ) )
• Worst Case: O( N^2 )

1. In best case, N/2 + N/2 = N; so in theory it doesn't matter whether it's split or not. But there is the advantage that two containers can be sort in separate threads. So it's a win.

2. In the average case, 2 * (N/2 log(N/2)) > N log(N); having one large container should be faster than sorting two smaller ones (though there remains to be seen whether threading can negate the effect up to certain N)

3. In the worst case, 2 * (N/2)^2 < N^2; which means it's much better to sort two smaller containers than a large one.

In the end you'll have to profile as it is not a golden rule.

Spiro's suggestion of using temporal coherence assumes that most of the time you can get O(N) sorting using insertion sort; thus most likely having two smaller containers should be better (if you perform threading).

Update: Stupid algebra mistake. See lunkhound's post. Avg case is better when dividing and conquering.

Ooops. My bad. You're right. I've updated my post.

Cull objects through the spatial partitioning system (or even just brute-force if you are just testing things) using the camera’s frustum. You can populate the render-queue directly as you do this.

Or if you care about cache coherency, branch misses, ... the list goes on. Spacial partitioning is not useful except as a means of dividing up large (i.e. > 20k) objects into smaller lists which will still number objects in the thousands (or more). Once again, a link for those considering spacial partitioning.... here's why you probably shouldn't unless you have a LOT MORE than 20k objects...

I especially like the part where it says:

The new culling
> Uses the computing power

What if I don't want my computing power to be used? :)

Sleep(1000);
for(int i=0; i!=1000; ++i) printf("", sqrt(i*42.0));

This is interesting, although I'm a little confused about how the scheme outlined by L Spiro works, specifically:

If the new total is the same as the last total, do nothing. Leave indices as they are.

Is it not possible that the total could be the same between two frames, but that items in the render queue (after culling) are different? In this case the indices won't necessarily point to the same items as in the previous frame, and the queue would need to be re-sorted.

If the same number of items end up in the list but they are different items, the logic above applies.

#1: Do not mess with the indices. Leave as they are.

#2: The sorting pass will reorder them according to the new data.

Since the sort is performed every frame it automatically fixes any cases where objects are not in sorted order after filling the render-queue. They will be sorted before rendering, and then that order will be there for the next frame.

L. Spiro

#2: The sorting pass will reorder them according to the new data.

Ah, thanks for clearing that up. I was thinking that you were skipping the sort in this case.