Recursive Raytracing, on GPU Hardware without Recursion

CS 481 Lecture, Dr. Lawlor

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. Until 2010 (Fermi) this was a hardware limitation due to the fact that functions are inlined, so there isn't a runtime call stack. Fermi and newer cards have a runtime call stack, but it's not supported in GLSL yet.

The Tail Recursion Trick

But luckily, we can usually transform recursion into iteration using a trick called tail recursion. For example, here's a typical recursive call:

int f(int i) {
	if (i<1) return 1;
	else return f(i-1)*i;
}

int foo(void) {
	for (int i=0;i<10;i++) std::cout<<"f("<<i<<") = "<<f(i)<<"\n";
	return 0;
}

(Try this in NetRun now!)

At runtime, "return f(i-1)*i;" has to push the return address, go off to the i-1 work, and when it returns, finally multiply by i. It's a lot more space and time efficient to get everything done first, then just jump back to f, like so:

int f(int i,int theAnswer) {
	if (i<1) return theAnswer;
	else return f(i-1,theAnswer*i);
}

In fact, many compilers will optimize the above "tail call" into a jump:

int f(int i,int theAnswer) {
start:
	if (i<1) return theAnswer;
	else {
		theAnswer=theAnswer*i;
		i=i-1;
		goto start;
	}
}

Swapping the goto with a while, this is basically just a loop:

int f(int i,int theAnswer) {
	while (!(i<1)) {
		theAnswer=theAnswer*i;
		i=i-1;
	}
	return theAnswer;
}

Hey! We just transformed recursion into iteration!

Recursion to Iteration in Raytracer

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 "frac" 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 frac=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)*frac;
		frac *= i.mirror; // <- scale down all subsequent rays
		rayStart=i.hit_location; // change ray origin for next bounce
		rayDir=reflect(rayDir,i.normal);
	}
	return finalColor;
}

This iterative version works great on the GPU, and the cumulative "frac" 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 (frac<0.05) break; // give up--not much impact on final color
	}
	return finalColor;
}

See the example code for a worked-out example.