Occlusion Mapping

After reading through a small amount of papers during the last weeks, I spend the last couple of days implementing an idea for an algorithm to improve the probabilistic visibility estimation.

The idea

The idea is as follows: in a preprocessing step, a number of rays is traced from the light sources through the scenes. For each ray being traced, an empty list of primitives is created. After the first intersection, the intersected primitive is added to the list. Then the ray is traced further. Upon each following intersection, an occlusion photon is created, which stores the position of the intersection and the current list of occluding primitives. After the photon is created, the currently intersected primitive is added to the front of the list with occluding primitives.

The result is a map of "occluding photons", which contain an approximation of the occluding geometry at a position in the scene.

The following figures show the resulting occlusion map for a test scene.

Cornell box with two triangles	Hot-to cold representation of the density of the occlusion map with 1000000 photons.

When tracing camera rays through this test scéne, we can differentiate between four different situations:

• No occlusion
• Occlusion by the yellow triangle
• Occlusion by the green triangle
• Occlusion by both of the triangles

When there is no occlusion at all, we don't need to trace any shadow rays to the light source. When there is only one occluding primitive, we only need to trace rays to that primitive.

The occlusion map allows us to differentiate between these situations. When an intersection in the scéne is found, we perform a lookup in the photon map. When no nearby photons are found, we assume that the visibility is always one. When the nearby photons only have records of one primitive, we only trace shadow rays to that primitive. However, when the photons have references to multiple primitives, we use the probabilistic visibility estimator as described in the previous post about probabilistic visibility.

Results

The test scénes have been rendered with an increasing number of shadow rays using deterministic visibility and the proposed algorithm. When we plot the total number of intersection tests for both methods, we see that the number of intersection tests is much lower with the new algorithm. Furthermore the difference becomes even larger when more shadow rays are traced per pixel. This is because a large portion of the scéne is unoccluded by both the triangles. In these regions, no shadow rays have to be traced with the occlusion mapping method.

Graph displaying the number of intersection tests (in millions) for a given number of shadow rays.

The images below show the results of the rendering with different amounts of shadow rays. These images look a lot better than when we are using the regular probabilistic visibility estimation because the shadows in the penumbra and the unoccluded regions are now exact.

4 shadow rays

64 shadow rays

256 shadow rays

900 shadow rays

However, the occlusion mapping technique introduces one extra artifact in regions that didn't receive enough photons. An example is given in the figure below.

Artifact introduced by the occlusion mapping approach

The penumbra region here shows some gaps where there were no nearby photons. In the proposed algorithm, visibility will always evaluate to one, which is an incorrect result.

Conclusion

The proposed algorithm reduces the number of intersection tests by a great amount. Also the variance introduced by probabilistic visibility is reduced and now only visible in regions with multiple occluding objects.

Downsides of this technique are that a great number of photons needs to be shot. Furthermore, this photon shooting has to be done for every light source, which can an expensive preprocessing step in a real-time application with many light sources.

Storing the photons in a KD-tree for every light source seperately can also be a burden on memory. If this is the case we could use an implicit object presorting to create an acceleration structure as described in M. Eisemann et al. - Geometry Presorting for Implicit Object Space Partitioning