Render Culling Optimization

Is anyone know the proper way to do culling for the rendering object. Which way is Faster?
The process below will run on every single frame.

E.g 1
Step

  1. Clear List<>
  2. Check camera frustum intersects with the Object
  3. Add to List<>
  4. Do render base on the List<>

E.g 2
Step

  1. Check camera frustum intersects with the Object
  2. Check is the List<> already contain the object. If Not, Add to List<>
  3. Do render base on the List<>

I don’t know why you need to check if the object already exists in the List<T>, but it would be an O(n) operation.

You might also want to try just using an array of fixed size (you know the maximum amount of render objects?).

The game I am currently working on uses the first approach, where we clear the render list each frame, then build it up according to what should be drawn. So I’d say this is a valid technique.

With the second one I’m not so sure, wouldn’t you need to also remove the object if it is not in the frustum? This would worry me if it meant shifting elements a lot.

size is dynamic…

i did some research before, and found List<> Contain() actually consume more resource compare to clear and add

Ya accessing a array takes time more time then pushing a struct onto the stack or even probably a bunch of structs. Clearing a whole array is of course accessing all the items in the array as well though its super optimized.

Say you have a list of items then you index to check then index to set a list of visible stuff.
So its two array accesses either way one to examine and check the other to place or mark.
And a third if you are clearing a list.

If its really that time critical i don’t even clear the lists.

I made my own pattern for this problem.

I use what i call a deadIndex on the list and move dead items past it and just use dead items for newly alive items by incrementing what amounts to a index used like a stack pointer.
(it will become a pattern eventually lol … no im serious some random dude will claim he invented the idea)

Dead and new items are moved as follows.
1)
For newly dead items i swap the alive item just before the deadIndex with it then decrement the deadIndex.
2)
For newly alive items i increment the deadIndex and re-set up the item i.e pool it.

  1. is the critical part i don’t swap the item that is about to be dead to the end of the list i swap it with the last alive item then move the index down i don’t clear or reset the dead item i just move the reference. If this was a visibilityIndex i could keep updating that items position and such only when i needed to and avoid unnecessary access.

The thing with this is you can have more then just a deadIndex you can also have secondary and even third indexs that determine were things are moved exactly. Like a visibilityIndex but the dead index is the primary array or list dividor any other indexs should be with it.

so this suggestion is basically to combine steps in the second case.

E.g 2
Step

  1. (Access +1) Check camera frustum intersects with the Object.
  2. (Skip the majority or swap two Access =+2 the minority) Move item or not depending on if it needs to move in the list as it has visibility markers.
  3. Do render base on the List<>

Typically far far less frame to frame is being swapped then could be in this manner skipped so the overall majority could be a single array access. Which amounts to check and render.

Not sure it really helps in this case but i have in the past drawn a pretty massive amount of items like that without problems.

Though in all honesty i think the only way to know is to benchmark.

1 Like

Remember that the update loop and the render loop normally run on different threads (actually on windows it seems to be always on different cores.)

So if you want to go multi-threaded at some stage you should double buffer the render list.

Update : ->
Get offscreen list from renderer.
Update as willmotil suggests (STRONGLY SUGGEST YOU USE THIS TECHNIQUE!!)
Tell renderer update complete

Renderer :->
Display onscreen list
When update complete , swap lists

@willmotil Most of us have been using this technique for particles for years. It is very handy

Just for reference, the pattern suggested is documented in object pooling; it’s called free list.