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.

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.

Octree

Since I will probably need to create or adapt an existing acceleration structure for ray tracing, I thought it was a good idea to implement a new acceleration structure to familiarize myself with the avaible methods and interfaces.

PBRT already comes with a Bounding Volume Hierarchy, Uniform Grid and kD-acceleration structure, so I decided to add an Octree to the list.

An octree subdivides the scene into eight equal sized voxels and each non-empty voxel is again recursively subdivided into eight voxels. Speedups are gained when a ray misses a voxel, since all of the children of that voxel no longer need to be checked.

Furthermore, an octree does not suffer from the "teapot in the stadium" problem, since it adapts to irregular placed geometry by only subdividing non-empty voxels.

The false-colour image below shows the number of intersection tests (including voxel intersections) for the stanford bunny scéne.

Stanford Bunny Scéne
(displaying the correctness of the octree implementation)

False color image when using the Octree. 
The maximum number of intersections is 2324 (red).
The total number of intersections is 102,265,467 

Next we compare the rendering times against the other acceleration structures:

	BVH with SAH	Uniform Grid	kD-tree with SAH	Octree
Stanford Bunny	2.9s	5.3s	3.1s	5.3s
Utah Teapot	27.7s	34.2s	31.6s	36.2s
Killeroo Scene	160.1s	415.7s	233.7s	669.5s

These results show that my implementation of the octree accelerates ray tracing, but still needs some tuning. I guess "make it work, make it right, make it fast" is the key here. The implementation already works and the "aggegratetest" tests assures that it is also right. Now I still need to make it fast.

Shadow photons

In my blog post about Occlusion Mapping I presented a method to reduce the variance in the probabilistic visiblity estimate. Since this method looked promising, my promotor encouraged me to do a bit more research towards photon mapping. Therefore I read the book Realistic Image Synthesis using Photon Mapping by Henrik Wann Jensen, which is cited in a lot of papers on photon mapping.

To my surprise, this books already proposes a similar method, using a photon map with "Shadow Photons" to reduce the number of shadow rays in a scéne. The description of their method is presented in the paper Efficiently rendering shadows using the photon map also by Henrik Wann Jensen.

Similar to my method they trace photons from the light source, which are only stored after a first intersection. These photons are the "Shadow Photons". In the paper they also trace the regular photons called "Illumination Photons" (see figure 1)

Figure 1: Shadow photon creation.
Courtesy: Henrik Wann Jensen, "Efficiently Rendering Shadow Using the Photon Map", 1995

These shadow and illumination photons are used to identify regions that are completely in shadow and completely illuminated. When a ray is traced through the scéne, a photon lookup is performed. Based on the number of shadow and illumination photons, three distinct cases can be identified:

1. there are only shadow photons: no shadow rays have to be traced since the point is completely in shadow
2. there are only illumination photons: no shadow rays have to be traced since the point is completely illuminated
3. there is a mix of shadow and illumination photons: shadow rays have to be traced.

Jensen also proposes to estimate the visibility v_i as n_i / (n_i+n_s) where n_i is the number of illumination photons and _s is the number of shadow photons. However, this requires a great number of photons.

The results from the paper indicate an average reduction in the number of shadow rays of 90%.

Introduction to PBRT

The algorithm(s) for my thesis will be developed in the PBRT ray tracer. I familiarized myself with the ideas, code and the used algorithms by reading the book Physically Based Rendering and today I spent some time going through the source code.

As a first test and as a usefull tool, I created a class which outputs a false color image of the number of intersection tests during rendering. Here is some of the output when run on the standard PBRT scénes:

The Stanford Bunny

False color image when using the Bounding Volume Hierarchy.
The maximum number of intersections is 963.
The total number of intersections is 31,468,464 

False color image when using a kD-tree.
The maximum number of intersections is 772.
The total number of intersections is 8,967,463.

False color image when using a uniform grid.
The maximum number of intersections is 3519.
The total number of intersections is 40,690,247.

The number of intersection also includes the number of box and voxel intersections for the bounding volume hierarchy and grid.

Next thing to do is setting up an svn or git repository for the code.

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

Mastering C++ - Transparent materials

This is my wrap-up for learning C++. I will stop implementing my own global illumination engine and focus completely on probabilistic visibility and acceleration structures.

I did manage to implement transparent materials and I was succesfull in seperating the calculation of direct light and indirect light. The results are shown below. The direct illumination was sampled with 256 samples per pixel, the indirect illumination was sampled with 5000 samples per pixel. It took 4,5 hours to complete.

Direct illumination only (256 samples per pixel)

Indirect illumination only (5000 samples per pixel)

The combined image (total rendering time 4,5 hours)