## Motivation

The aim of this project was to implement a fully dynamic frustum and occlusion culling algorithm. I have recently done a Light Propagation Volume implementation and feel that various passes in this technique could benefit from culling quite heavily. It is mainly the Reflective Shadow Map passes, one for every directional light, that could benefit from occlusion culling. The pre-depth pass and the forward pass would benefit from both frustum and occlusion culling as well. Aside from the above-mentioned reasons, frustum and occlusion culling algorithms are vital parts of modern renderers. Knowledge of how to implement and use them is almost mandatory for a modern graphics programmer.**Download Source:**culling_release.7z

## Frustum Culling

Frustum culling is a technique used the cull geometry that lies entirely outside of the frustum, and therefore cannot be seen by the camera. This is done by calculating the six planes of the frustum, calculating a bounding box of a mesh and checking if all 8 points of that bounding box lie entirely outside of the frustum. If all the points lie outside of the frustum the mesh cannot be seen and should be culled. Calculating the six frustum planes is done by extracting them from the MVP matrix. Extracting from the MVP matrix allows us to do the frustum-box intersection test in local space. This is perfect for us since our AABBs are already in local space.## Extracting the frustum planes

Let \(v = (x, y, z, w = 1)\) be a vertex and let \(M=(m_{ij} )\) be a 4x4 MVP matrix. Transforming \(v\) by \(M\) results in the transformed vertex \(v'=(x',y',z',w')\). And could be written as: \begin{equation} v^{\prime} = (v \cdot col_{1}, v \cdot col_{2}, v \cdot col_{3}, v \cdot col_{4}) \end{equation} After this transformation \(v'\) is in homogenous clip space, where the frustum is an Axis Aligned Bounding Box. The size of the AABB frustum is API specific but we will be focusing on DX12. If \(v'\) is inside this frustum, \(v\) is inside the**untransformed**frustum.

We can test if \(v'\) is inside the frustum by checking the following inequalities. \begin{align*} -w^{\prime} & < x^{\prime} < w^{\prime} \\ -w^{\prime} & < y^{\prime} < w^{\prime} \\ 0 & < z^{\prime} < w^{\prime} \\ \end{align*} Now, say we would like to test if \(x'\) is in the left halfspace of our frustum. \(x'\) is inside the half space if: \begin{equation} -w^{\prime} < x^{\prime} \end{equation} We can now rewrite this inequality to: \begin{equation} -(v \cdot col_{4}) < (v \cdot col_{1}) \end{equation} In turn we can rewrite this to: \begin{equation} 0 < v \cdot (col_{1} + col_{4}) \end{equation} Finally, we can expand this to: \begin{equation} x(m_{14} + m_{11}) + y(m_{24} + m_{21}) + z(m_{34} + m_{31}) + (m_{44} + m_{41}) = 0 \end{equation} This is exactly how we would represent a plane using the plane equation: \begin{equation} ax + by + cz + d = 0 \end{equation} We can now extract all six frustum planes from the MVP matrix and use the to check if all the eight points of a bounding box are outside the frustum. If all eight points are not in the frustum we do not render the mesh.