Paper summary

The past month, I've been reading a lot of papers, first specifically about acceleration structures and the past weeks more broadly about other means to accelerate global illumination. My goal was to find suitable algorithms or ideas to combine with probabilistic visibility.

I'm going to present the first batch of papers I've read and give a little summary:

Instant Ray Tracing: The Bounding Interval Hierarchy

This paper presents a new acceleration structure which is a cross-over between kD-trees and bounding volume hierachies (BVH). It combines the best of the two world, leading to a lower memory consumption and a fast kD-tree like traversal.

It works by not storing six planes for each node (like a BVH), but only two perpendicular planes. Traversal is like in a BVH, but since the nodes are spatially ordered, traversal can be made more efficient by intersecting the closest child along the ray first (like in kD-tree traversal). Analogous to the BVH it is possible to not intersect any node at all when the ray is between two non-overlapping children (see figure 2).

Figure 1: Situation when the ray (blue line) misses the left and the right child.

Construction can be done in O(N log (N)) time and the constants can be reduced by a bucket sorting preprocess. Furthermore, it is also possible to do a lazy construction of the hierarchy to further reduce the memory footprint, since construction will be avoided in unvisited elements of the scéne.

The number of object references in this technique is equal to the number of objects. This is an advantage since this restriction is not guaranteed by kD-trees in which a primitive is referenced multiple times.

Reference: Carsten Wächter and Alexander Keller, 2006: Instant Ray Tracing: The Bounding Interval Hierarchy. Eurographics Symposium on Rendering

Visibility driven BVH build up algorithm for ray tracing

The heuristic for creating BVH and kD-trees is usually the surface area heuristic or SAH and this heuristic performs well. However, the assumptions for the cost function are rather unrealistic. The assumptions are:

• A uniform distribution of rays in scene space
• Shadow rays do not terminate after their first intersection

The paper modifies the cost function to include visibility information. If the visibility assumptions are (mostly) valid, (on average) the algorithm will perform better.

The proposed method is usefull in animations, where we have knowledge about visibility from previous frames and in scenario's were a large number of rays needs to be traced.

With the infomation about the approximate visibility, a cost function is defined that accounts visibile and invisible triangles differently. This seperates the visible and invisible geometry in the hierarchy which results in shallower trees in the part with the visibile triangles. Figure 2 visualizes how the SAH would possibly generate a BVH (on the left) versus the new heuristic called OSAH. The blue triangle represents a visible triangle while the gray are invisible.

Figure 2: SAH vs OSAH hierarchy

Reference: Marek Vingkler, Vlastimil Havran, JiriSochor, 2012: Visibility driven BVH build up algorithm for ray tracing. Computers & Graphics 36 (2012) p. 283-296

Accelerating Shadow Rays Using Volumetric Occluders and Modified kD-tree traversal

An algorithm is described that marks nodes of a kD-tree using two additional bits. These bits are used to differentiate between three possible situations. The node is either:

1. Opaque (completly inside the model)
2. Boundary (contains a triangle of the model)
3. Clear (is completely outside the model)

Traversal down the kD-tree can be stopped when an opaque node is reached. The traversal of the kD-tree is also modified to favor opaque nodes, since for a shadow ray, any intersection is good, not necessarily the closed. 

Performance is gained here because the opaque nodes are larger and less deep in the tree. Further performance can be gained by using a cache of used volumetric occluders to exploit ray coherence. 

The downside of the technique is that only watertight models can be used. When open models are used, no difference can be made between opaque and clear nodes. In addition the bounding boxes of the volumetric occluders are not explicitly known since, they are discovered by traversing the kD-tree.

Dispite this fact, the idea of volumetric occluders is very interesting for probabilistic visibility, since we can use the larger occluders as stand-in's for smaller geometry, perhaps reducing the variance.

Reference: Peter Djeu, Sean Keely, Warren Hunt, 2009. Accelerating Shadow Rays Using Volumetric Occluders and Modified kD-tree traversal. High Performance Graphics 2009 p. 69-76

Memory-conserving Bounding Volume Hierarchies with Coherent Ray Tracing

The authors propose to store the bounding boxes of the nodes using unsigned 8-bit integers instead of floating point numbers. They achieve this by dividing the bounding box of the parent in 256 pieces and placing the bounds of the bounding boxes at these discrete positions. This will result in a slight loss of performance, since the bounding boxes will tend to be slightly larger. However, the savings in memory allow the nodes to be aligned with the caches and to be more compact, improving cache coherence.

They also recommend using coherent ray tracing, so that decompressing the hierarchy from the 8-bit unsigned integers only needs to be done once per packet.

Test results display a decrease of 79% in memory usage when using double precision and 63% when using single precision floating point numbers. However there is a 41% increase of rendering time because of the overhead of decompressing the nodes during ray traversal and because of a small excess in ray traversal since the bounding boxes are larger. This can be solved using coherent ray tracing, which amortizes the calculations over entire packets of rays.

Reference: Jeffrey A. Mahovsky, Brian Wyvill, 2006. Memory-conserving Bounding Volume Hierarchies with Coherent Ray Tracing. IEEE Transactions on visualization and Computer Graphics.