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