Paper summary - continued

The following papers describe some more algorithms that could be combined with probabilistic visibility. The first algorithm reduces the number of shadow rays that need to be traced. The second paper describes a novel representation for the Bounding Volume Hierarchy (BVH) that uses 0 bytes of memory. The third also describes a compact representation of the BVH that maintains a comparable performance.

The final summarized paper uses advanced caching strategies and an interesting combination of Instant Global Illumination and Instant Radiosity to exploit spatial coherence. Furthermore it reuses the cache between frames to achieve temporal coherence. Especially this paper looks very interesting to me, since we can use the cache to make valid guesses about the probabilities in probabilistic visibility.

Adaptive Shadow Testing for Ray-tracing

This paper presents a method to reduce the number of shadow rays by testing the most important light sources first and quit testing the remainder of the lights which have a low contribution. This approach trades accuracy for speed.

During rendering a global statistic is build up in the scene that keeps track of the number of hits versus the number of shadow ray tests for each light source. This statistic is used to discard unimportant light sources that have been invisible most of the time.

The only incurred memory overhead is some extra integers per light source to keep track of the number of hits versus the number of tests. 

However for each shadow ray, the potential contributions from all the light sources have to be calculated, in order to know which ones will have a higher contribution.

Reference: Greg Ward. Adaptive shadow testing for ray tracing. In Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering, pages 11–20. Springer Verlag, New York, 1994.

Implicit Object Space Partitioning: The No-Memory BVH

The authors present a new algorithm that allows a BVH to be represented implicitly. The main observation is that the geometry defines the BVH. The BVH is represented by ordering the list of the triangles of the scene. From this ordering, the bounding planes are reconstructed during the traversal of a ray.

Construction is top-down, switching between the axes in round-robin fashion (xyzxyz...). The hierarchy is represented as a complete, left-balanced, binary tree ordered in breath-first order. This allows to index the list with triangles as a heap (hereby saving explicit storage of pointers).

During traversal, the bounding planes are reconstructed from the two triangles that represent the current node in the hierarchy.

The result is that this representation requires no memory at all (except for a list with all the geometry of the scene). However there is a slight performance decrease compared to state of the art BVH's. This drawback can be alleviated partially by using a real BVH structure for the top levels, and by representing the nodes of that tree by No-Memory BVH's.

Being able to create an acceleration structure using 0 bytes of memory can be quite important, since an acceleration structure usually takes up a lot of space. For large scenes, this could mean that the acceleration structure would not fit into main memory, decreasing performance dramatically because of slow disk IO.

Reference: M. Eisemann, P. Bauszat, S. Guthe, M. Magnor, 2012. Geometry Presorting for Implicit Object Space Partitioning. Eurographics Symposium On Rendering 2012, Volume 31, Number 4

Ray Tracing with the Single Slab Hierarchy

By noting that a child of a BVH node shares a lot of planes with its parent. Therefore, the authors propose a BVH hierarchy that only uses one bounding plane. Similar to BVH, the hierarchy is traversed in a top-down fashion and complete subtrees can be skipped if a ray misses a node.

Construction is almost identical to a regular BVH. This time two splitting planes will be chosen (preferably using different axis to get tighter bounds). Any construction technique can be used (e.g. SAH, spacial median cut,...).

Traversal resembles BVH traversal, but with the complexity of kD-tree traversal. In each step, the active ray interval is maintained and updated. Nodes outside this interval can be skipped.

The results from the implementation show that this BVH algorithm is comparable in speed (and sometimes even faster) than state of the art implementations. Furthermore, the Single Slab Hierarchy (SSH) requires only 25% of the memory of a complete BVH. The tests show that the number of node traversals is twice as high as with regular BVH's. This is not much of a problem since the intersection tests for nodes in the SSH are six times less expensive. Also the slabs do not fit the geometry as tightly compared to regular BVH's, which slows down rendering. The results indicate however that only one extra primitive needs to be intersected per ray.

Reference: M. Eisemann et al, 2011. Ray Tracing with the Single Slab Hierarchy.

Instant Caching for Interactive Global Illumination

This paper proposes an interesting combination of irradiance caching and instant radiosity to accelerate the global illumination computation. Furthermore, they exploit temporal coherence in animations by identifying the cached calculations that are invalid due to movement of geometry. This allows to achieve great improvements in animations.

The algorithm starts by shooting photons from the light sources to create the Virtual Point Lights (VPL's) and subsequently performs a gathering pass. In the gathering pass, the irradiance from the VPL's is evaluated at a sparse set of points (in contrast to the Irradiance Cache in which the complete hemisphere is sampled). Computation of the indirect diffuse component however is similar to the Irradiance Cache.

Further performance is gained in animations by reusing the cached samples. At each frame the samples have to be checked whether they have become invalid. Five cases are identified for a cached sample:

1. VPL is occluded by moving object
2. VPL is deoccluded by moving object
3. Cached sample is occluded by moving object
4. Cached sample is deoccluded by moving object
5. Sample/VPL is on a moving object

At the start of each frame the VPL's are retraced, solving case 1 and 2. Case 3 is solved by tracing rays from the cached samples towards the light sources and only intersecting the moved objects (a cheap acceleration structure could be built over those objects).

For case 4, all objects of the scene should be intersected again. However, we only have to do this when the occluder of the sample is a dynamic object. For case 5 the sample simply has to be discarded.

The results show an average 2x speedup when compared to Instant Global Illumination (IGI) in static scenes and a 4x speedup in dynamic scenes. This speedup is the result of stronger spatial and temporal coherence.

The resulting images are also validated with a perceptual metric. For this they use the HDR-VDP metric, which visualizes the areas that humans are most likely to be detect as different. Compared to IGI, the difference is never larger than 0.33%. This shows that there is no tradeoff in quality for the speedup. Comparison against ground truth path traced images shows that the error is never larger than 2,11%.

Reference: K. Debattista et al. 2009. Instant Caching for Interactive Global Illumination. Computer Graphics Forum Volume 28 (2009), number 8 pp. 2216-2228.