Hello, I have a few questions about hierarchical view frustums and efficient view frustum culling. Ok, so I have an octree that contains the entities of the world and now want to cull (recursively) the octants against the view frustum as normal to determine visible entities. There are many early out tests that could be used here and there are many ways one could go about tackling this. For example, one could cull the octants in question against a sphere encompassing the frustum, then if that passed, against an AABB encompassing the frustum, then if that passed, against an OBB encompassing the frustum, then if that passed the frustum itself. Other shapes could be used as well ... cones etc. Spheres around the octants could also be used in this matter for early out tests. For example you could go ... octant's sphere against frustum's sphere ... then, if that passed go octant against frustum. There are so many combinations of geometrical shapes that could be used for early out testing and many different combinations of tests. It seems to me that SOME early out tests (frustum's sphere to octant perhaps) could in theory speed up the scene culling, but that too much or the wrong ones would slow it down. I have no experience in this matter and would love some input. Question 1) Is there a common concensus in this matter in professional FPS game engines? If so, what is it? Question 2) If there is not common concensus, what do you personally suggest along the lines of what early out frustum/octant shapes to use? Question 3) If anyone has any definitive testing in this matter I would love to hear your results. Oh, this is for a 3D game engine so the solution will need to be general, flexible and as versatile as possible (the solution will not be application specific). Thank you for your help. Jeremy

Update -

It seems to me after a bit of speculation that planar coherency on the frustum planes and octants might COMPLETELY eliminate the need for ANY early out tests with the exception of possibly an octant's planar coherent sphere to the frustum itself, and if that passes, then the planar coherent octant to the frustum. My reasoning is that a sphere to a plane collision check is about as simple as it gets if my understanding is correct, and with planar coherency that IS the early out since other even more simple geometric shapes than a frustum will actually be more computationally expensive since the coherency provides a more effective early out as it likely boils down to a single plane check.

Any thoughts?

Jeremy

Update -

After a bit more research I found that a sphere to a plane intersection takes 1 dot product and that an AABB to a plane takes 1 or 2 dot products depending with some other minimal overhead.

So, if my assumptions are correct the best early out is NOT in adding more trivial geometric tests to the frustum itself (sphere/AABB etc.), but using planar coherency resulting in most cases a single plane test (the early out).

Ok, so now from my point of view it makes more sense to ONLY use planar coherency and avoid the rest since planes are themselves more computationally trivial than even a sphere.

So now it just depends on whether it is worth it to add an octant's planar coherent sphere versus the frustum as an early out test. If that passes, use the octant's planar coherent AABB versus the frustum.

I believe that only extensive testing (or additional feedback) would prove whether this is a worthwhile test to add or even support.

So, my final thoughts without any further input is that ...

Planar Coherency eliminates the need for any early out tests along the lines of geometric simplifications of the view frustum, as planar coherency by definition provides an even more simple early out (results likely determined by a single plane). It may be worthwhile to use a planar coherent octant's sphere to early out with the frustum but that only extensive testing would provide the determination of that tests worth.

Please, I would LOVE some feedback on this and confirmations on the accuracy or inaccuracy of my assumptions.

Jeremy

Great ... it is great to hear that my initial assumptions are correct.

Ok, so I currently have a list of dynamic objects (moving) that are not in the octree at all and just maintained in a list, and an octree that maintains all objects that are stable. When an object becomes stable (based on physics) then it is removed from the dynamic list and added to the octree of static objects. Likewise when an object becomes dynamic it is added to the moving list and removed from the octree. I do this because adding/removing from the octree every frame seems pretty pointless for dynamic objects.

Now ... objects are inserted into the octree using their OBB to the octant collision test for as tight a fit as possible.

Now, when an octant is deemed visible by the view frustum, if it is COMPLETELY contained by the frustum, all objects are added to the visible list and no further processing is required. If it intersects, the object's OBB's are tested against the frustum and added/removed to/from the render list accordingly. If the octant is not visible, obviously they are removed from the render list. Dynamic objects in the list are simply checked against the frustum each frame using their bounding spheres.

My thoughts are that by bypassing the insertion/removal of dynamic objects from the octant each frame you are saving time by simply testing thier spheres linearly against the octant. Octant to OBB tests are more costly and during insertion their can be more than one of those tests.

This seems to be a fairly effective strategy to all of this.

I really would like some input into this overall process as well if at all possible.

Also, I would love to hear your thoughts on whether adding an octant's planar coherent sphere check against the frustum would be worth it as an early out during octant to view frustum culling. Again, without further input from people with experience or exclusive testing I personally could not say.

Thank you again for your help.
Jeremy

Thank you,

That is good advice.

That is a good point that a dynamic object only needs to be reinserted to the octree if it exceeds containment of the octant it is CURRENTLY in.

I still think that it may be best to simply keep dynamic objects in a list of their own. The grouping has nice side benifits in that operations can be performed linearly like the calculation of dynamic object shadow volumes (static objects do not need theirs re-calculated each frame) etc. and is simple.

Some form of dissection of the dynamic object lists would be desirable though as like you say the list can grow large.

My thoughts are that some kind of ZONE concept might work. For example, objects in a certain zone can be enabled for updating/processing/rendering and disabled as well with a simple flag. Rather than update all dynamic objects every frame with the elapsed time, update them with the elapsed time since the zone they are in was last activated.

For example, a city is off in the distance so its inhabitants should not be updated/moved/rendered or even processed at all. So you turn that zone off once you leave the city and the gates close behind you. Then, when you come back to the city 4 hours later and open the door, you update once with 4 hours of elapsed time. As long as your calculations enable this massive time delay which shouldn't be difficult the city is in theory still 100% intact instantaneously. So, if the zone is active it is simply updating as usual but it has a time stamp of when it was last turned OFF. Then when it is turned on you can have a one time massive update then just process as usual.

This concept does not require any collision checks, just a simple flag to enable/disable the zone.

As long as you structure your levels correctly this should reduce a lot of calculation times. For example, your cities should have walls with doors. The reasoning is ... if you are outside, nothing is processed in the city because you cannot see that the inhabitants are not walking/moving or rendered. Once you open the city doors and the doors close behind you, you can disable EVERY (or most) zones outside of the city etc.

Just a concept I have been considering.

It is in theory just a hierarchical culling system handled with a simple flag for off/on. Zones could then maintain their own octree and dynamic object list.

Any thoughts/ideas?
Jeremy