Overview

Ray tracing is the heart of modern day graphics. In this project, we implement its basic algorithms and optimizations. In Part 1, we simulate rays emanating from the camera to the scene, and we use normal shading to render the scene. In Part 2, we use Bounding Volume Hierarchies (BVHs) to accelerate the simulation of ray intersections. In Part 3, we introduce lights to the scene, and simulate direct illumination as paths from the camera to light sources. In Part 4, we allow rays to "bounce" off surfaces as calculated via BRDFs, which creates global illumination and reflections. Finally, in Part 5, we use adaptive sampling to greatly reduce the number of rays cast.

Part 1: Ray Generation and Scene Intersection

In the 3D environment, we simulate a camera with an image plane in front of it. For each pixel of the image, millions of rays are cast from the camera through the corresponding point on the image plane into the scene. We check for intersection with the primitives in the scene, specifically using either triangle or sphere intersection algorithms.

We find the closest intersection between a ray and a primitive, if it exists. This intersection is used to determine how the pixel is shaded. For now, we use normal shading.

The implementation we use relies of using dot and cross products to speed up calculations. In particular, we first calculate if the ray is moving parallel to the plane containing the triangle; if it is, we know there is no intersection. Otherwise, we find where the ray intersects the plane using the plane formula $(p-p^{\prime })\cdot N$. Next, we can use cross and dot products of the vectors defining the edges of the triangle to check whether the intersection is to the left or right of each edge. Using a consistent orientation, e.g. that edge is defined to be clockwise w.r.t. the direction of the normal vector, allows us to check if the intersection is inside the triangle simply if it is to the left of each edge.

We implemented sphere intersection by solving the quadratic equation involving a ray and a sphere. We then return the smallest valid root as our intersection point.

Examples of normal shading:

Part 2: Bounding Volume Hierarchy

We use a recursive BVH construction algorithm that splits each box in two along some axis. In particular, the splitting algorithm we use splits each box based on the axis that most evenly divides the volumes of its children. Specifically, we

1. Use the centroid of each axis at a potential split point.
2. Calculate the approximate volume present to the left and right of each split point (this was found by summing the normal of the extent of each primitive).
3. Splitting along the axis with the most even split.

This heuristic turned out to be pretty good, and was better than our initial approach of simply counting the number of primitives to the left and right of each split. The idea is that children of each node should have an approximately balanced volume.

Care needs to be taken to ensure that these split points are not all degenerate. When no split points are good, we can take an arbitrary split.

BVH reduced the number of intersections per ray for each of the previous renders:

We can easily render much more complex geometries:

We seriously reduced rendering times by reducing the number of rays per intersection needed. Each moderate geometry experienced an over 100x decreased in the total number of intersections calculated. In fact, for a complex geometry like CBlucy, a benchmark test found that there was a 15514x reduction in the number of intersections that we needed to calculate. This is because in a balanced BVH tree, search times should be logarithmic in the number of primitives, rather than linear. Each of the renders with BVH acceleration were very fast. In the aforementioned benchmark, CBlucy with no optimization took 358 seconds to render, whereas with the optimization, the render took ~0.0876 seconds.

Part 3: Direct Illumination

Direct lighting is our first attempt at illuminating our scene according to light sources. Direct lighting is a combination of "zero bounce" and "one bounce" illumination. The former is simply the light rays that are between the camera and light sources. The latter is where we trace our rays over a single bounce, and illuminate intersections according to the light sources that impact them.

The most naive implementation of this is Uniform Hemisphere Sampling, where the intersection point is randomly sampled over the hemisphere around the surface normal. We generate a number of outgoing rays and illuminate the intersection based on which of the outgoing rays intersect a light. The Monte Carlo estimate of the shading of this intersection is given by a weighted average according to Lambert's Cosine Law.

Importance Sampling is a smarter implementation of Direct Lighting, where we only bother casting bounces in the direction of light sources. We can consider this to be a heavily biased Monte Carlo sample. In particular, we have no need to sample parts of the scene where there will be no contribution to illuminance. This method will be equally as accurate as the Uniform Hemisphere technique (assuming we account for normalized for our sampling method), but will be significantly less noisy. This will make the total render more efficient since we can estimate direct illumination with less fewer samples per intersection.

Uniform Hemisphere vs Importance Sampling at the same number of samples per intersection:

Importance Sampling as we increase samples per intersection:

Our scene obviously becomes significantly less noisy as we increase the number of samples. The geometry of the scene becomes more apparent as well. One subtle effect is that increasing the number of light rays creates "soft shadows", e.g. areas of the scene where there is some but not total occlusion. This effect becomes more accurate with more samples, and shadows form gradients rather than harsh and noisy cutoffs.

While Uniform Hemisphere Sampling and Importance Sampling should converge in the limit, the former is an extremely naive approach. Mathematically, if we understand Direct Lighting as approximating an integral, the latter approach sends no samples to areas where the function is zero, whereas Uniform Hemisphere Sampling samples the integral equally everywhere. The effect is that our renders are much more noisy. Each pixel will take longer to converge. Subtle geometries and soft shadows do not appear without significantly more samples.

Part 4: Global Illumination

Global illumination introduces indirect lighting to the scene; in particular, we allow an arbitrarily high number of bounces per ray. This can be implemented by adding recursive calls to our PathTracer. Each ray has some probability of spawning another ray when it has intersection. This new ray has a weight given by the BRDF of the intersection surface, as well as by Lambert's Cosine law.

In order to avoid infinite recursion, we keep track of the depth of each ray. Once we hit a specified maximum recursion depth, we stop our traversal. For

For our implementation, the only BRDF that surfaces can have is the diffuse BRDF: e.g., a ray will bounce according to the Uniform Hemisphere distribution.

Global illumination:

We can calculate the scene lit by "only indirect illumination" by finding the global illumination and subtracting off the direct illumination (and the "zero bounce" illumination):

Direct illumination appears to contribute sharp, well-defined shadows and the overall precise geometry of the scene. Indirect illumination adds brightness to the scene, color bleeding, and subtle shading (for example, at the bottom of spheres). Together, the composite image is a beautiful, photorealistic render.

Impact of maximum ray depth:

The image takes on increasingly complex shading patterns as we increase the maximum ray depth. When the depth is 1, we have only direct lighting. As we increase the amount of indirect lighting in the scene, the image gets brighter, and more textures on the bunny begin to appear. We note that the difference between a maximum ray depth of 3 and 100 is fairly minimal. In particular, due to the Russian Roulette termination of rays, many rays will never reach a depth as high as 100, and we will get convergence much sooner.

Increasing number of rays-per-pixel:

Increasing the number of samples per pixel will obviously only improve our Monte Carlo estimate of the color of each pixel. Image noise decreases in proportion to the number of samples we cast. Fine geometries, such as the complex texture of the rabbit's skin, begin to appear at a high number of samples. Each element of the scene increases in fidelity at a high sample rate. There is essentially no noise in the final image that is visible to the human eye, and the resolution seems to be a maximum given the dimensions (480 x 360) of the image.

Part 5: Adaptive Sampling

Adaptive sampling is a simple technique to dynamically update the number of rays we cast per pixel. In particular, we simply measure the variance of a pixel across the samples we have cast at it so far. If the variance is sufficiently low, if we have a high enough confidence level, we determine that the pixel has converged to its true mean. In order to implement this efficiently, we only check for convergence in batches, e.g., after 32 rays have been cast. This technique gives large improvements in rendering time:

It is clear that the adaptive sampling rate heavily biases samples in highly-detailed regions of the scene. Additionally, it has no problem rendering less-frequently sampled regions of the scene at a high level of fidelity. This indicates that our technique for determining whether a pixel has converged is accurate.