Exploring Occlusion Mapping

During my meeting with professor Dutré, we concluded that Occlusion Mapping could be a viable method for probabilistic visibility. In this blog post, I would like to elaborate a bit more on my thoughts of this technique. I will start by restating the idea, followed by a possible extension on it. I will conclude with some possible techniques to reduce memory usage and to increase performance.

Occlusion mapping

In a preprocessing step, occlusion photons are be shot from the light source. When these occlusion photons encounter their first intersection, nothing happens. However, on the second and on each subsequent intersection, an occlusion photon is created. An example of this process is shown in figure 1.

Figure 1: Occlusion photon shooting. Upon the first intersection, no photon is stored.
Only after the second and subsequent intersectons, occlusion photons are created. 

Each occlusion photon stores a list with the previously intersected occluders as shown in figure 2. This figure shows how occlusion photons are shot through a scene with 5 occluders and how the list of occluders is stored.

Figure 2: Occlusion photons are shot through a scene with 5 occluders and each
occlusion photon records the previously intersected occluders.

During the rendering pass, a lookup is done around the first intersection point of the camera ray. The occluders of the nearest photons are gathered and only they are used for shadow testing. When no occlusion photons are found, the point is said to be in light and no shadow rays are shot.

Occlusion mapping with light photons

Instead of only storing occlusion photons, we could also store light photons. Light photons are stored like regular photons. They are created only upon the first intersection. Figure 3 shows the same as figure 2, but extended with the light photons.

Figure 3: Shows the same scene as figure 2 but extended with light photons.

Light photons can be used to find areas that are completely in light and combined with the occlusion photons, they can be used to find areas that are completely in shadow. This is done in the following way.

During the rendering phase, a lookup is done around the first intersection point of a camera ray. The found photons can be either:

• Only light photons: the point is completely in light and no shadow rays have to be traced.
• Only occlusion photons: the point is completely in shadow and no shadow rays have to be traced.
• A mix of light and occlusion photons: visibility is determined by sending shadow rays to all the occluders in the occlusion photons.

This scheme limits shadow ray casting to the soft shadowed regions.

Reducing the memory requirements

The memory requirements of this technique are very high. For accurate results, a large number of photons have to be traced through the scene. Furthermore, a unique occlusion map has to be created for every light source present in the scene. Finally, each occlusion photon stores a list of occluders, which requires a lot of memory, especially for scenes with a large depth complexity. Therefore, I propose a couple of methods to decrease the memory usage.

Sparse storage of occlusion photons

During the creation of the occlusion map, we will only sparsely store an occlusion photon. For this to work we assume the set of occluders locally doesn't change much. As long as we trace enough occlusion photons, the result will be the same. 

Figure 4 shows this approach. In the left figure, we see that all the occlusion photons are stored. On the right side of the figure, we randomly discarded half of the photons (the discarded photons are grayed out). Photons which are colored the same store the same set of occluders.

Figure 4: Sparse storage of occlusion photons. Occlusion photons have the same color
when they store the same set of occluders. The grayed photons in the right side are the
discarded photons.

The figure shows, if we perform a lookup in the occlusion map with a large enough search radius, we would get the same results.

Sparse storage of occluders

Instead of storing the complete list of occluders, we can also chose to store a limited set of occluders. The choice and the amount of occluders is still a question, there are several options:

• only store the x previous occluders.
• only store the x largest occluders
• only store the x occluders closest to the light source
• store the occluders which are not yet found in other photons in the area
• ...

This will require some testing to see how the choice of occluders changes the result. There will not be one silver bullet, but it could be that for certain specific scenes, one choice of occluders will work great.

Linked storage of occlusion photons

For every occlusion photon, we could only store the previous intersected primitive and a reference to the previous photon. The full set of occluders can then be found by traversing the photons back into the direction of the light source. Figure 5 shows this approach to storing the set of occluders.

Figure 5: Storing the complete set of occluders by storing only one occluder
per occlusion photon and a reference to the previous occlusion photon.

Adaptive removal of occluders

Finally we could start with a complete set of occluders in each occlusion photon and maintain statistics. This allows us to remove occluders which have rarely been used.

Improving performance

To improve the performance of occlusion mapping we could use volumetric occluders. This approach would help in scenes with lots of detailed meshes. Instead of storing the reference to a small triangle, we could instead store the reference to a much larger volumetric occluder. This approach will help in a couple of ways:

• less intersection tests
• beter cache coherence
• less photons are needed

We will need less intersection tests because volumetric occluders are large and nearby occlusion photons will probably hit the same volumetric occluder, which improves cache performance. We will also need less photons. 

To see why we need less photons you have to imagine a scene with a large model (e.g. the Stanford Dragon). In order to be sure that there are no holes in the shadow of the final image, each triangle should have at least one occlusion photon containing it. In other words, every triangle should be in the occluder list of at least one occlusion photon. If this is not the case, it could be possible that a triangle is not intersected with a shadow ray and thus leaves a hole in the shadow.

Using volumetric occluders elevates that problem.

Conclusion

There are still a lot of open questions on Occlusion Mapping. At the moment, memory is a bottleneck and the methods to reduce memory consumption need testing. Therefore it is time to start on a first implementation.