Recursive Raytracing, on GPU Hardware without Recursion

2010, Dr. Lawlor, CS 481/681, CS, UAF

It's really surprisingly easy to add true reflections to a raytracer.  If we start with the global "find_color" function, originally something like this:
// Look up the color of the world viewed along this ray
vec4 find_color(vec3 rayStart,vec3 rayDir) {
ray_intersection i = closest_hit(rayStart,rayDir); // geometric search
return light_intersection(i); // diffuse + specular
}
To support perfect mirror reflection, you just add a recursive call to "find_color", that searches along the reflected ray:
// Recursively look up the color of the world viewed along this ray
vec4 find_color(vec3 rayStart,vec3 rayDir) {
ray_intersection i = closest_hit(rayStart,rayDir); // geometric search
vec4 local = light_intersection(i); // diffuse + specular
vec4 remote = find_color(i.hit_location,reflect(rayDir,i.normal)); // recurse!
return local*(1.0-i.mirror) + remote*i.mirror;
}
Unfortunately, the current generation of GPU hardware doesn't support recursive functions.  This is a hardware limitation, due to the fact that functions are inlined, so there isn't a runtime call stack.

But luckily, we can actually transform recursion into iteration quite generally.  For example, here's a typical for loop, written with recursion:
void recursive(int i) {
if (i<10) {
cout<<"I'm at recursion "<<i<<"\n";
recursive(i+1);
}
}

int foo(void) {
recursive(0);

// Iterative version
for (int i=0;i<10;i++) {
cout<<"I'm at iteration "<<i<<"\n";
}
return 0;
}

(Try this in NetRun now!)

It's a little bit more complicated to support recursive functions that modify their return value, like this example.  The trick is to accumulate all the "0.5*i" multiplications into a single cumulative scale factor:
float recursive(int i) {
if (i<10) {
cout<<"I'm at recursion "<<i<<"\n";
return 0.5*i*recursive(i+1);
}
else return 1.0; // base case
}

int foo(void) {
cout<<"Recursive: "<<recursive(1)<<"\n\n";

float scale=1.0;
for (int i=1;i<10;i++) {
cout<<"I'm at iteration "<<i<<"\n";
scale*=0.5*i;
}
cout<<"Iterative: "<<scale*1.0<<"\n";

return 0;
}

(Try this in NetRun now!)

We can apply this same trick to transform a recursive raytracer into an iterative loop over ray bounces.
// Recursively look up the color of the world viewed along this ray
vec4 find_color(vec3 rayStart,vec3 rayDir) {
ray_intersection i = closest_hit(rayStart,rayDir); // geometric search
vec4 local = light_intersection(i); // diffuse + specular
vec4 remote = find_color(i.hit_location,reflect(rayDir,i.normal)); // recurse!
return local*(1.0-i.mirror) + remote*i.mirror;
}
Transformed to iteration, we need a "contribution" variable to account for all the recursive "i.mirror" factors from previous bounces:
// Iteratively look up the color of the world viewed along this ray
vec4 find_color(vec3 rayStart,vec3 rayDir) {
vec4 finalColor=vec4(0.0);
float contribution=1.0; // fraction of my color to add to finalColor
for (int raybounce=0;raybounce<max_bounces;raybounce++) {
ray_intersection i = closest_hit(rayStart,rayDir); // geometric search
vec4 local = light_intersection(i); // diffuse + specular
finalColor += local*(1.0-i.mirror)*contribution;
contribution *= i.mirror; // <- scale down all subsequent rays
rayStart=i.hit_location; // set up for next bounce
rayDir=reflect(rayDir,i.normal);
}
return finalColor;
}
This iterative version works great on the GPU, and the cumulative "contribution" scale factor even suggests an optimization: stop looping when the cumulative impact drops below some quality threshold:
// Iteratively look up the color of the world viewed along this ray
vec4 find_color(vec3 rayStart,vec3 rayDir) {
... as before ...
for (int raybounce=0;raybounce<max_bounces;raybounce++) {
... as before ...
if (contribution<0.01) break; // give up--no impact on final color
}
return finalColor;
}
See the example code for a worked-out example.