CS184/284A Spring 2025 Homework 3 Write-Up

Han Li & William Wu

Link to webpage: wu-yong-xuan.github.io/cs184/hw3 Link to GitHub repository: cal-cs184-student/sp25-hw3-m-0w0-m

Overview

In this homework, we made a suuuper cool pathtracer alongside acceleration structures so many computer doesn't explode. This pathtracer simulates direct and indirect light bounces for diffuse surfaces. This homework was super cool to do, albiet the amount of renders we had to do was kinda crazy.

Part 1: Ray Generation and Scene Intersection

In the beginning, there was darkness. Then, a voice said, let there be light! Fiat lux! Unfortunately, there were no eyeballs to witness the view. Thankfully, since we're CS majors, we don't need eyeballs. We can code a virtual camera to see the world for us!

In the real and scary world, rays of light emit from light sources and bounce around, some of which hit our eyeballs and the neurons and synapses in our brain register that as color. Unfortunately, we live in the matrix so that doesn't necessarily apply here. The real world is computationally expensive, so here in the matrix, we gotta find something more efficient.

Instead, let us shoot rays from our eyeballs out into the world and trace these rays backwards. This ensures we only do calculations that we can see. Given a camera origin and an image plane that lies in front of the camera, we can shoot rays from the camera origin to every pixel on the image plane. The number of rays we shoot out per pixel is based on our sample amount, and using a grid sample function, we can shoot rays uniformly randomly at different points of the pixel.

Shooting out rays like pew pew lasers star wars is cool and all, but if those rays can't collide with anything, then we can't collect the radiance from it. Specifically, we want to have our rays be able to collide with triangles.

A ray is defined with an origin vector and a direction vector, and it can written as follows \(r(t)=o+td\)

One neat thing to note is that a triangle is the only shape in 3 dimensions that is completely planar, and thus, can be defined uniquely by a plane. A plane can be thought of with the following equation \(p:(p-p')\cdot N=0\) Replacing \(p=r(t)\), we can then solve for \(t\) in the ray equation. With that, we can decide whether the \(r(t)\) lies within the triangle by doing a simple triangle test.

This is cool and all, but our robot overlords are complaining that it's too slow and they want an even more efficient method!

Introducing the Moller Trumbore Algorithm.

Given that we can define any point of a triangle with barycentric coordinates, we can find some unique properties. Note that when \(\alpha\) or \(\beta\) are negative, the point is outside of the triangle. Same with if \(\alpha + \beta > 1\). To determine these coefficients, we can note set the ray equation equal to the barycentric equation for the triangle, giving us \(\vec{O}+t\vec{D}=(1-\alpha -\beta)\vec{P}_0+\alpha \vec{P}_1+\beta \vec{P}_2\)

Rewriting this in matrix form (and screenshotting this from the lecture slides since I'm too lazy to rewrite the math in latex). Note that these images use \(b_1\) and \(b_2\) instead of \(\alpha\) and \(beta\). It's confusing, I'm not sorry.

Once we solve for the barycentric coordinates, we can do the check mentioned earlier, and if it's satisfied, then we can use the \(t\) value to solve for \(r(t)\). It's a simple algorithm in concept, but the math is a bit scary with all the fancy symbols.

The important thing here, is that after we intersect with a triangle, we want to set the max_t> to the t we found. That way we can ignore any future intersections with triangles that are farther away from the current closest intersection.

Intersecting a sphere is even simpler. A sphere can be defined as \(p:(p-c)^2-R^2=0\). Plugging in the ray equation for \(p\), we can simply solve a quadratic equation to get 2 values of \(t\). The math is left as an exercise for the reader.

The interesting thing to note is that here we get two \(t\) values, so we want to get the smaller one which is the side of the sphere that hits the ray first.

Here are some images rendered with normal based shaded!

Part 2: Bounding Volume Hierarchy

With our cool triangle intersection algorithm, we dazzled our cyber overlords with amazing spectacles. Unfortunately, it takes us 10 years to so each time and they want it harder, better, faster, stronger.

So it's time for us to work it, make it, do it, makes us, harder, better, faster, stronger.

We'll do something called constructing a BVH, or a bounding volume hierarchy. The high level overview is to partition the mesh into different bounding volumes, such that we can ignore all bounding volumes and thus, their subsequent triangles, that we do not hit with the ray.

The BVH itself is a recursive structure, thus the hierarchy of bounding volume hierarchy. Each bounding volume itself contains bounding volumes until the final volume contains at most our specified triangle limit. We construct our BVH by finding the bounding volume across first, the entire mesh. Then, we split it into two child volumes. The child volumes here are axis aligned, but how do we know what axis to split it?

Generally speaking, we want to split the bounding volume along the longest axis. We want to minimize having long thin strips. All we need to do is find the extend of each axis, find which axis is the longest, and split it that way. We can then partition all of the triangles within each resulting side of the split into their own corresponding BVHs.

To avoid having to create new data structures, we implemented an in-place sorting algorithm for the primitives. We keep a counter of the number of primitives on the left hand side as we iterate through all the primitives of the parent bounding volume. If the current index is greater than the counter for the # of primitives on the left bounding volume, AND the current primitive is supposed to be on the left bounding volume, then we simply need to swap those two positions. This algorithm will partition all the primitives such that all the ones on the left are grouped together and all the ones on the right are grouped together.

We repeat the construction until the BVH minimum triangle conditions are satisfied.

An important thing to note here is to make sure that there is never an instance where one side of the partition has 0 triangles or else it would cause an infinite loop. To resolve this, if that condition happens, we instead just split the primitives at half the length of the array instead.

Part 3: Direct Illumination

Yet, even with eyes on our head and objects in the cyber city, we still saw nothing. The darkness grew in our very souls and we began to lose hope. At our wits end, we remembered the first couple lines of task one: "In the beginning, there was darkness. Then, a voice said, let there be light!" We need lights! Thus, to create an image in our camera, we needed to shoot some rays, pew pew. To do this, we first needed to implement a diffuse BSDF, so we know how light interacts with objects in our frame. The BSDF tells us how much of the light coming from some solid angle \(w_in\) is redirected in a specific direction (w_out). A diffuse BSDF for a lambertian shader just disperses incident light equally across a hemisphere normal to the surface. Thus, the BSDF is given by \(f(\omega_i,\omega_o) = \frac{\text{albedo}}{\pi}\)

If both w_in and w_out are within the hemisphere and 0 otherwise.

Now that we have the BSDF, we implemented direct illumination. This consisted of finding the zero bounce radiance as well as the single bounce radiance a pixel on the camera receives. To find the zero bounce radiance, we cast a ray from the camera and check the first object it hits. Grabbing the emission value from the surface's BSDF, we get the radiance that goes into the camera directly from the lights.

But, this only lets us see the lights, which is quite uninteresting. Thus, we then implemented hemisphere sampling for direct illumination resulting from one bounce. We implemented it in the following way:

• Once we've casted our first ray and detected intersections, we pass that information into our one bounce function
• Repeat num_samples times
  • Sample a random w_i (in object coords) using hemisphere_sample->get_sample()
  • Create a new ray at the intersection point pointing in the w_i direction (in world coords)
  • Initialize min_t = EPS_F to avoid casting a ray into itself
  • Then cast this new ray and check for intersections
  • If it does intersect with something, we can find the emission of the object the ray hits
  • The radiance that is reflected at the point back into the camera is given by
    • \(\frac{f(\omega_i,\omega_o) \cdot \text{emission} \cdot \cos(w_i) }{pdf}\)
    • Where pdf is the probability density function of sampling the direction w_i
    • For a diffuse BSDF this is just \(\frac{1}{2\pi}\)
• We add up all the radiances from each sample and divide by num_samples to get the average radiance reflected back to the camera from the point we raycasted to.

This implementation was okay, but oh so noisy and it took a long time to converge. In order to create a more efficient implementation, we decided to use importance sampling. Our implementation is as follows:

• For each light
  • If it's a point source, only sample once otherwise set num_samples to ns_area_light
  • We used sample_L to sample an emission value given a hit point. This function also samples w_i (world coords) and outputs it along with the pdf of the sample and the distance to the light
  • We first convert w_i in object coords to see if the light source is behind the object. If it is, we know no light should reach the point
  • If the light source isn't behind the object, we create a new ray at the hit point in the w_i (world coords) direction
  • We initialize min_t = EPS_F and max_t = dist - EPS_F where dist is the distance from the hit point to the light
  • We then check if the ray intersects anything before the light source and, if it does, we return 0 radiance.
  • If it doesn't we get the radiance reflected back to the camera
    • \(\frac{f(\omega_i,\omega_o) \cdot \text{emission} \cdot \cos(w_i) }{pdf}\)
  • We do this num_sample times and then average the radiances

Hooray! Now we have direct illumination. We can now see lights and shadows.

You can clearly notice how in uniform hemisphere sampling, the image is incredibly noisy and especially with only 1 light sample, most of the pixels are in the dark. This is obvious since with only 1 light sample, the chance that a given point's ray hits the light in the entire hemisphere is very low.

Noise Level Comparison

Importance Sampling w/ 1 camera sample

Within the shadow of the bunny, you can notice how the more light samples there are, the better the result is for the creating the soft shadow. With low light samples, the result is very noisy.

Part 4: Global Illumination

In our effort to fly like icarus and bring the light of the sun in all its glory to our mangled cybercity, we need to do a better job at calculating the light rays. Specifically, we need to not stop those light rays from bouncing after just 1 bounce, but have them INFINITELY bounce! Just kidding, my potato laptop cannot handle that. Instead, we will sample the radiance at every given bounce object until a given limit.

To do this, for each bounce, we calculate the one bounce radiance as well as a recursive call to itself. This recursive call takes in a sampled ray direction at the point of intersection and increases the ray depth by one. The result of this recursive call is multiplied by *fracRadiance*cos_theta(win)/pdf/cpdf in order to normalize the radiance gained.

We multiply by the fractional radiance returned by the sample function as well as the the angle of the sampled ray. Dividing by the pdf ensures we normalize the light by the chance that particular direction was chosen

The cpdf is the chance that ray continues to live on via russian roulette. Russian roulette is the process of estimating the early termination of ray bounces in order to speed up render times. If we're at the max ray depth, we simply need to return the one bounce radiance.

You can see how in the only indirect light image, you don't get any of the light directly from the light source. However, there's still a sizeable amount of light contained in the image, showing just how important indirect lighting is to a scene

Ray Depth Comparison

You can see how as the ray depth increases, the unaccumulated light becomes less. This makes sense as the more light bounces, the less intense it will be. For example, you can notice how in depth 2 and 3, it gets darker. Overall, adding all these secondary bounces greatly contributes to the quality of the image. However, at a certain level (ex 5 ray depth), the unaccumulated light is so minimal that it hardly makes a difference.

Russian Roulette

Various sample rates

4 light rays

PHEW, that was a LOT of renders. My computer is smoking after this. We notice that with low pixel samples, the entire image is very grainy compared to high samples. This is different than the noise we saw with low light samples. Here, with low camera samples, the noise is uniform across the entire screen.

Part 5: Adaptive Sampling

With the light afire within our hearts, a bright light atop a pillar dubbed the sun was restored in our cybercity. Our overlords enjoyed the richness of illuminated daily life and began to hire artists to demonstrate the beauty of direct and global illumination. One such artist took inspiration from our sampling algorithms in a piece called "Costco free sample-ing". We had noticed the artist would consistently go back to solid colors they drew and draw more of the same color on top. We asked why and were told that our sampling algorithm worked the same way. Oh no! How inefficient! Our cyber overlords would certainly be pissed if they knew our global illumination was far from perfect. Thus, to honor "Costco Free Sample-ing", we implemented adaptive sampling.

Adaptive sampling selectively samples areas that converge slower more often than areas that converge quickly. It essentially will sample a pixel until it has converged or hit the max samples per pixel. To measure whether a pixel has converged, we used the standard error and compared it to the mean.

\(1.96 \frac{\sigma}{\sqrt{n}} \leq \text{max_tolerance}\cdot{\mu}\)

Where \(\mu\) is the mean and max_tolerance is defaulted to 0.05 (but is changeable). In our PathTracer::raytrace_pixel() function, every samples_per_batch samples we calculate the mean and variance to check whether the pixel has converged. To do this, we add each sample's illuminance to a sum and the square of its illuminance to another variable.

\(s_1=\sum_{k=1}^{n} x_k^2\)
\(s_2=\sum_{k=1}^{n} x_k\)
\(\mu = \frac{s_1}{n}\)
\(\sigma^2=\frac{1}{n-1}\cdot s_2-\frac{s_1^2}{n}\)

Once we find a pixel has converged, we terminate the loop and stop sampling the pixel.

(Optional) Part 6: Extra Credit Opportunities

GUI

Added a toggleable button to turn on and off Russian Roulette (the z button). Also added a toggleable button to switch between direct lighting only, indirect lighting only, and both (q button). This was done by modifying the application.cpp script and the raytyraced_renderer.cpp script to take in the additional keys during the RENDER VIEW to update booleans

BVH primative in-place partitioning

As mentioned in Task 2, the primative pointer vector, primatives, is sorted in place to partition all primative pointers associated with the left BVH node and the right BVH node. This paritioning groups the primative pointers together which eliminates the need to create new primative pointer vectors. Each BVH node then points to the start and end of their particular portion of the total vector.