# 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 rayvec4 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 rayvec4 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 rayvec4 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 rayvec4 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 rayvec4 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.