**[A Graphics Diary](../index.html)**
*Automatic Occluder Generation*
*15.11.19*
*[←](../index.html)*
**Properties of occluders**
Occluders are a variant, or alternative representation of a mesh. They are an essential part of an occlusion culling system, as their simplified representation allows the occlusion step to be more efficient than if it were to use the original and _high definition_ version of the mesh. To fully leverage them, they have to respect a few properties.
![](occluders-banners.png)
_Reduced complexity in comparison to the original mesh_, in terms of triangle count and shape. Occluders should be fast to draw. This can usually be done by using an aggregate of simpler convex shapes.
_Fully conservative_; its volume should be less than or equal to the real mesh volume and fully contained within. This property is required in order to not give false positive such as occluding more than expected, or discarding objects from the visible set. Conservative occluders may also allow for pre-z optimization. Drawing them in a depth only render pass before any fragment-costly shaders would leverage the hardware hierarchical z-culling and/or early-z fragment rejection [^early-z].
Large as in _occupy the largest possible volume of the original mesh_. This property guarantees that the mesh would discard as many elements as if the original mesh were to be used. To calculate the mesh efficiency, it could be imagined to render both the occluders and its original mesh and see if the rejection ratio of using one or the other is reaching a satisfying convergence. This property can also be viewed in terms of having a high screen-area coverage from different viewpoints. It is important to note that depending on which side your mesh will be drawn, it is possible to make specific optimizations therein. For example, in a car driving simulation where the viewpoint is known to be on the ground; a boxed-shape building would be most likely simplified as a box occluders where the box is only composed of its side faces, without the top and bottom. This would differ in an open-world game, where the level of freedom reduces the ability to make such assumptions.
[^early-z]: Refer to the manual of the GPU vendor you are working with, or chapter 18.3.7 of the book "Real Time Rendering" for more information about this type of optimization.
**Automatic generation of occluders**
The algorithm chosen to automatically generate occluders takes in a 3d mesh, and outputs a list of AABBs ensured to be contained within the input 3d mesh. The algorithm is composed of 4 main steps:
1. _Shell_ voxelization
2. _Inner_ voxelization using the previously generated shell voxel set
3. Generate a per-axis minimum distance to _shell_ voxel from each voxel in the _inner_ voxel set
4. Iterative box expansion using the per-axis minimum distances starting from voxels in the _inner_ set
To simplify comprehension, the algorithm will be first illustrated and described in 2d, and then extended to the 3d case. Note that the algorithm described in 2d is a simplification of the 3d algorithm and would most likely be optimized accordingly if it were to only be used in 2d.
**Box filling algorithm (in 2d)**
In 2d, voxelization is commonly named rasterization, and a voxel a pixel. The first two steps of the algorithm are _shell_ and _inner_ rasterization (also known as conservative rasterization). In order to simplify things, the mesh is represented by a single triangle. And instead of performing triangle-cube intersection, as we will see in 3d, we perform triangle-edge intersection against pixel-aligned AABBs.
*Shell and inner conservative pixelization*
To be able to generate a conservative set of pixels, we need to first generate the _shell_ pixel set. To do so, we snap the triangle AABB to the pixel grid; pixel snapping is the process of mapping any 2d position to a single pixel. Then, iterate over each pixel of that grid and perform triangle-edge to AABB intersection. This gives the first set of _shell_ pixels (overlayed in blue in the figure below).
![Figure [rasterization]: Shell and inner conservative rasterization](illustration0.png width=300)
Once the _shell_ pixel set is available, we perform a second pass over the pixel grid covered by the triangle, and look in each positive and negative direction of the unit axes, _(+x, 0)_, _(-x, 0)_, _(0, +y)_, _(0, -y)_. If from a given pixel, there are 4 _shell_ pixels visible from all of these directions, the pixel is marked as being part of the _inner_ pixel set; this essentially performs conservative rasterization.
*Minimum distance to shell pixel (On the positive unit axes)*
The next step of the algorithm takes in both the _shell_ and _inner_ pixel set, and calculates the minimum distance to _shell_ pixel for each pixel of the _inner_ pixel set. The distances are only calculated for the positive axis. The reason being that when doing the next expansion step, the expansion will only be done in both the _(+x, 0)_ and _(0, +y)_ directions.
![Figure [minimum distance set]: Per-axis minimum distance to shell pixel. This step helps answer the question: How far can each AABB expand on each direction before overlapping with any shell pixel? On the left, the minimum distance on the positive x axis, and on the right on the y axis.](illustration1.png width=600)
In the provided source code, this step is in fact done when marking the pixels as being part of the _inner_ pixel set as an optimization.
*Box expansion on positive unit axes*
At this point, we have all the data necessary to iteratively perform AABB expansion. At each step of the iterative process, the idea is to find the AABB which maximizes the covered area the most (or volume in 3d) and then clip that AABB to the _inner_ pixel set before repeating again. The clipping ensures that we reject any already processed pixel for the next iteration.
One step to find the maximized AABB area can be described as follows: For a given _inner_ pixel at _(x, y)_ and its minimum distances to _shell_ pixel $\d_{x}$ and $\d_{y}$ on the respective positive _x_ and _y_ unit axes, retrieve all _inner_ pixels within the range from _(x, y)_ to _(x, y + $\d_{y}$ - 1)_ and find $max(area(\d_{y}, \d'_{x}))$, where $\d'_{x}$ is the minimum distance on _x_ for any _inner_ pixel of the described range. This both maximizes the covered area of an AABB that would expand from _(x, y)_ and ensures the non-overlap with the set of _shell_ pixels.
Now that we have a way to find the AABB that maximizes the covered area for any given _inner_ pixel at _(x, y)_ we can find the pixel that maximizes the area for the current set of _inner_ pixels using the method previously described. Then, clip all _inner_ pixels that lay within the extent of the chosen AABB, and repeat the process again. We can stop the process when the sum area of all the AABBs reached a given percentage of the triangle area.
![Figure [minimum distance set]: Final set of conservative AABBs, each color corresponds to one AABB](illustration2.png width=300)
**Box filling algorithm (in 3d)**
To perform voxelization and generate the _shell_ voxel set, Akenine-Moller triangle-cube intersection is performed for the voxels covered by the 3d grid of the triangles. Note that similarly to 2d, the triangle is snapped to the voxel grid for a given voxel resolution.
We can then use the _shell_ voxel set, to do visibility test and distance field generation; a voxel is marked as belonging to the _inner_ voxel set, if and only if it can _see_ a voxel in the _shell_ voxel set on each of the unit axes _x_, _y_, _z_ in both the positive and negative direction. To give some intuition, imagine yourself in a room, you can convey yourself that you are inside if there is a wall/floor in front, behind, on the right, left, on top and beneath you. Whenever an _inner_ voxel _sees_ another _shell_ voxel on the positive unit axes, the distance to that voxel is updated if it is smaller than the currently stored distance. Only positive axes are used for distances as they are the extension direction used during the filling phase as we have seen in the 2d case.
![Example of result on a 3d tile of Manhattan, this type of geometry is rather complex as there is a lot of self-intersecting geometry. We can notice that the algorithm also fails to recover on buildings that are misaligned with the AABBs. This can be solved by reducing the voxel size and the fill percentage at which the algorithm should stop, or rotate the mesh and merge the different results given for each rotation angle.](tile.png width=500)
The box expansion is exactly the same as in 2d, with the exception that another axis must be iterated over when selecting the volume that maximizes the current iteration. In 3d, the mesh volume is approximated by the number of _inner_ voxels it contains, which is a common approximation when trying to find the volume of a mesh. Note that this approximation is better the higher the voxel resolution is. The box expansion process stops when the total volume of selected AABBs reaches a reasonable percentage of the total volume of the mesh.
The documented source code is available on [github](https://github.com/karimnaaji/melt/blob/master/melt.h).
The source code for the embedded example in this webpage is available [here](https://github.com/karimnaaji/melt-emscripten/blob/master/melt.cc).
**References & Further reading**