Occlusion Culling - Falmouth-Games-Academy/comp350-research-journal GitHub Wiki

Occlusion culling is a method of optimisation where the scene does not render in images that cannot be seen by the camera. An example of this is if the camera is looking at a cup against a wall, the area of the wall which has been blocked by the cup would not be rendered. This reduces the number of objects drawn in a scene and is very popular for mobile devices 1(http://www.gamasutra.com/view/feature/131801/occlusion_culling_algorithms.php) 3(https://developer.arm.com/graphics/resources/faqs). More on Mobile device optimisation here.

Modern graphics engines will draw objects which are furthest from the camera first and then work its way towards the camera location drawing closer objects over further away objects, this is called overdraw 4(https://docs.unity3d.com/Manual/OcclusionCulling.html). Unity and Unreal offer the ability for occlusion culling with some manual setup 2(https://docs.unrealengine.com/en-us/Engine/Rendering/VisibilityCulling) 4(https://docs.unity3d.com/Manual/OcclusionCulling.html). Note that occlusion culling is similar but not the same as frustum culling, which deals with objects out of the cameras viewing arc.

Occlusion culling requires two steps. First, for a given viewpoint, we must select a small set of good occluders to use. Second, given good occluders, we must use them to cull away occluded portions of the scene 7(https://wwwx.cs.unc.edu/~geom/papers/documents/technicalreports/tr96052.pdf).

8(https://www.researchgate.net/publication/2440562_A_Survey_of_Visibility_for_Walkthrough_Applications).

Differences between Occlusion Culling and Frustum Culling

Occlusion culling is different from Frustum culling, Frustum culling only disables the renders for objects that are outside the cameras viewing area but does not disable anything hidden from view by overdraw. Whereas Occlusion culling disables the rendering of when they are not currently seen by the camera because they are obscured (occluded) by other objects. Because of their differences they can be used in conjunction with each other, so in Unity when you use Occlusion culling you will still benefit from Frustum Culling. 4(https://docs.unity3d.com/Manual/OcclusionCulling.html)

Also see Back Face Culling & View Frustum Culling (VFC).

Different ways to use occlusion culling

When using occlusion culling there are several ways that developers can use culling that will benefit them and the game platform they are using. One of the ways is to get assistance from the GPU, more specifically using ‘depth buffer reprojection’. The idea with this technique is to use the depth buffer from the previous frame and reproject it to match the current frame. The main drawbacks with this method are that it’s not always a concrete approach and can affect the game especially when there are fast moving objects or the camera changes abruptly which brings down the efficiency of the culling process.12(https://www.gamesindustry.biz/articles/2016-12-07-overview-on-popular-occlusion-culling-techniques)

Another way is top delegate everything to the GPU. This means making the GPU as independent from the CPU, making the GPU handle the culling and rendering without the CPU. This method provides good results, both for dynamic and static geometry with minimal lag. But on the negative side, this technique requires modern hardware with some serious computing ability, which is why you would see it being used for games that are made for a top-level piece of kit.12(https://www.gamesindustry.biz/articles/2016-12-07-overview-on-popular-occlusion-culling-techniques)

Another technique would be to use a precomputed way, which is used most commonly for mobile phones as they don’t have the computing power compared to a gaming PC or even a console, which makes real-time occlusion culling look comfortable. On certain devices UE4 doesn’t use the GPU or the CPU at all, instead it falls back to an older technique using ‘precomputed visibility volumes’, where the scene is divided into several cells, and a set of visible geometry is calculated offline beforehand for each one. The culling is then performed at run time by checking the location of which cell the player is inside and then retrieving the list of non-occluded meshes. The major disadvantage of this technique is that to doesn’t work well with large levels/maps, the larger the map, the more cells are needed which has a major impact on performance 12(https://www.gamesindustry.biz/articles/2016-12-07-overview-on-popular-occlusion-culling-techniques). This method can be very effective in a closed map split into corridors or small rooms. A well known example is Quake. A developer revealed in a post-mortem that they changed the rendering problem of different viewpoints of different rooms to a clipping problem of potentially visable sets(other rooms) 13(https://www.youtube.com/watch?v=1AUxDCHaw84).

Z-Culling

Visibility determination can be performed using the z-buffer algorithm:

First of all, initialize the depth of each pixel.
i.e,  d(i, j) = infinite (max length)
Initialize the color value for each pixel 
as c(i, j) = background color
for each polygon, do the following steps :

for (each pixel in polygon's projection)
{
    find depth i.e, z of polygon
    at (x, y) corresponding to pixel (i, j)
    
    if (z < d(i, j))
    {
        d(i, j) = z;
        c(i, j) = color;
    }
}

5(https://www.geeksforgeeks.org/z-buffer-depth-buffer-method/)

As this algorithm must examine every triangle in the input scene, z-buffering can consume a significant fraction of graphics processing. One way to avoid needlessly processing invisible portions of the scene is to use an occlusion culling algorithm to discard invisible polygons early in the graphics pipeline 6(https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/coorg97.pdf). The graphics pipeline of Unity follows the structure suggested by 6(https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/coorg97.pdf). In Unity, only objects that are visible get sent to the render 9(https://docs.unity3d.com/Manual/OcclusionCulling.html ). From this, we can assume that in Unity Occlusion culling is done on the CPU, not the GPU. The problem with CPU based occlusion culling is CPUs cannot do rasterisation as fast as GPUs[10] however, the common issue with GPU based occlusion culling is syncing the data from the GPU back to the CPU 10(https://interplayoflight.wordpress.com/2017/11/15/experiments-in-gpu-based-occlusion-culling/). A development blog by Bazhenovc 11(https://bazhenovc.github.io/blog/post/gpu-driven-occlusion-culling-slides-lif/) details a way to overcome this by using a method called reprojection. Reprojection uses depth buffer values from previous frames to cull objects from the current frame 11(https://bazhenovc.github.io/blog/post/gpu-driven-occlusion-culling-slides-lif/). However, this can create visual errors when trying to render a fast moving camera.

Consideration should also be given as to when z-testing or occlusion culling is performed. If this is one of the final steps of the pipeline, then other graphics processing, like shading or texture mapping, will have wasted computation time on invisible portions of the scene 6(https://www.cs.princeton.edu/courses/archive/spring01/cs598b/papers/coorg97.pdf).

References

[1] Gamasutra, Occlusion culling algorithms, accessed on 5th Febuary 2019.

[2] Unreal Engine documentation, Visibility culling, accessed on 5th Febuary 2019.

[3] Arm, What is occlusion culling, accessed on 6th February 2019.

[4] Unity, Occlusion Culling, accessed on 6th February 2019.

[5] geeksforgeeks, Z-Buffer or Depth-Buffer method, accessed on 8th February 2019.

[6] Coorg, Satyan, and Seth Teller. "Real-time occlusion culling for models with large occluders." Proceedings of the 1997 symposium on Interactive 3D graphics. ACM, 1997.

[7] Hudson, Tom, et al. "Accelerated occlusion culling using shadow frusta." Proceedings of the thirteenth annual symposium on Computational geometry. ACM, 1997.

[8] Cohen-Or, Daniel, et al. "A survey of visibility for walkthrough applications." IEEE Transactions on Visualization and Computer Graphics 9.3 (2003): 412-431.

[9] https://docs.unity3d.com/Manual/OcclusionCulling.html

[10] https://interplayoflight.wordpress.com/2017/11/15/experiments-in-gpu-based-occlusion-culling/

[11] https://bazhenovc.github.io/blog/post/gpu-driven-occlusion-culling-slides-lif/

[12] https://www.gamesindustry.biz/articles/2016-12-07-overview-on-popular-occlusion-culling-techniques

[13] Excerpt: Quake Postmortem - Optimizing Level Viewing, accessed 11th Febuary 2019.