View Frustum Culling (VFC) - Falmouth-Games-Academy/comp350-research-journal GitHub Wiki
What is a frustum?
A frustum consists of six planes, where two are parallel to each other. For orthogonal viewing, the frustum is a box and in the case of perspective viewing, as seen below, the frustum is a truncated pyramid 7(https://www.researchgate.net/profile/Ulf_Assarsson/publication/2614905_Optimized_View_Frustum_Culling_Algorithms_for_AABBs_and_OBBs/links/55f6cf0908aec948c462f514/Optimized-View-Frustum-Culling-Algorithms-for-AABBs-and-OBBs.pdf).
Frustum culling is the process of removing objects which are outside the cameras viewing arc, this reduces the number of polygons and objects present in a scene; speeding up load times and minimising CPU traffic 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/).
In this image, you can see that the green and yellow images are loaded, while the red images do not get loaded after being culled using viewing frustum techniques 2(http://www.lighthouse3d.com/tutorials/view-frustum-culling/). The red objects are not rendered due to more of the shape being outside the arc than in. The green sphere, although not visible to the camera, is still loaded in which results in unnecessary CPU memory being taken up. This can be rectified by using Frustum culling in conjunction with something like Occlusion culling and Back Face Culling. The below GIF shows the difference between View Frustum Culling and Occlusion Culling, two very common and often interchangeable techniques, that can actually be used together for great effect.
Methods of Frustum Culling
AABB & OBB methods
Frustum Culling can be performed in several different ways but all methods require an approximation of the object in world space. That is to say, a sphere or cube can be used to approximate whether a shape is in the camera's frustum or not. There are different kinds of boxes: world axis aligned (AABB) and aligned according to the local object's axis (OBB) as well as spherical primitives 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/)[3](/Falmouth-Games-Academy/comp350-research-journal/wiki/3)(http://old.cescg.org/CESCG-2002/DSykoraJJelinek/).
As you can see the OBB bounding box is a much better approximation of the shape and thus a more precise culling, but it also requires is also performs much worse than the AABB bounding box 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/).
Discrete Orientation Polytope (k-DOP) & Bounding Volume Hierarchy Trees
k-DOPs are a convex polytope whose facets are determined by halfspaces whose outward normals come from a small fixed set of k orientations 9(https://ieeexplore.ieee.org/document/675649). They are the most accurate bounding boxes as they are created to fit the meshes they represent. The rocks above show the generated k-DOPs around them, and closely they can be made to match the actual mesh. They can then be assigned a bounding volume hierarchy tree (BV-Tree), the update cost of which directly influenced speed of collision detection 10(https://link.springer.com/chapter/10.1007/978-3-642-29157-9_6). Many ways to increase the speed of which have been researched such as those shown by J.T Klosowski et al. 9(https://ieeexplore.ieee.org/document/675649) & W. Zhao et al 10(https://link.springer.com/chapter/10.1007/978-3-642-29157-9_6). Any form of bounding box can be assigned a BV-tree which is then used to sort the objects. If any bounding box is culled, all its child nodes are also culled.
Streaming SIMD Extensions (SSE)
Another Approach is SSE (Streaming SIMD Extensions) 5(https://www.intel.co.uk/content/www/uk/en/support/articles/000005779/processors.html). SSE includes in its architecture eight 128 bit registers and set of instructions to perform any operations on them. With this approach, 4 different objects are assessed at once, meaning that, theoretically this will give a 4x increase in performance, However, it appears that SSE actually gives a 3x increase 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/). As you can see the OBB bounding box is a much better approximation of the shape and thus a more precise culling, but it also requires is also performs much worse than the AABB bounding box 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/). If we then split this task across multiple cores using multi-threading we can actually achieve up to roughly an 8x increase in performance 1(https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/).
Origins of VFC
Study and research into User view and culling has been going on since the beginning of computer graphics and video games, it has been argued that the first development of an optimised VFC method was in 1976 by J. H. Clark 6(http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.145.691&rep=rep1&type=pdf) using a scene hierarchy. Mel Slater and Yiorgos Chrysanthou 8(http://www.academia.edu/download/46463900/View_Volume_Culling_Using_a_Probabilisti20160614-8954-y1btyl.pdf) have developed a VFC probabilistic caching scheme which is significantly faster but in some cases produces unacceptable errors.
Why is VFC important?
Frustum culling's importance has grown in recent years as large open world games have grown in prominence. This is because more assets are required to create these bigger worlds such as that in Horizon Zero Dawn, which can often massively decrease the performance of the game. The best way to avoid the massive rendering overheads of the larger worlds is to simply avoid rendering anything outside of the player's view as shown in this video of Horizon Zero Dawn 11(https://www.guerrilla-games.com/play/horizon). However, it should be noted that things that are concealed from the player, but that are still in the frustum will still be rendered 4(https://www.oreilly.com/library/view/unity-ios-essentials/9781849691826/ch02s04.html). This is where techniques like Occlusion Culling and Back Face Culling further reduce the rendering overheads.
References
[1] https://www.gamedev.net/articles/programming/general-and-gameplay-programming/frustum-culling-r4613/
[2] http://www.lighthouse3d.com/tutorials/view-frustum-culling/
[3] http://old.cescg.org/CESCG-2002/DSykoraJJelinek/
[4] https://www.oreilly.com/library/view/unity-ios-essentials/9781849691826/ch02s04.html
[5] https://www.intel.co.uk/content/www/uk/en/support/articles/000005779/processors.html
[6] Sunar, Mohd Shahrizal, Abdullah Mohd Zin, and Tengku MT Sembok. "Improved View Frustum Culling Technique for Real-Time Virtual Heritage Application." IJVR 7.3 (2008): 43-48.
[7] Assarsson, Ulf, and Tomas Moller. "Optimized view frustum culling algorithms for bounding boxes." Journal of graphics tools 5.1 (2000): 9-22.
[8] Slater, Mel, and Yiorgos Chrysanthou. "View volume culling using a probabilistic caching scheme." Proceedings of the ACM symposium on Virtual reality software and technology. ACM, 1997.
[9] Klosowski, J.T., Held, M., Mitchell, J.S., Sowizral, H. and Zikan, K., 1998. Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on Visualization & Computer Graphics, (1), pp.21-36.
[10] Zhao, W. and Li, L., 2011, August. A New K-DOPs Collision Detection Algorithms Improved by GA. In International Conference on Wireless Communications and Applications (pp. 58-68). Springer, Berlin, Heidelberg.