problems with my raytracer / Phong Illuminat

I am having a few problems with a recursive raytracer.

It works fine for a local illumination model. I also got it to work for implementing shadows due to other objects.

However, when I start the recursive process of calculating specular reflections and refractions, the image gets extremely grainy no matter what I do.

I had been told that this was possibly due to numerical errors and that instead of floats, I should use doubles. When I changed all of the float types to double types, I get

“Debug Error!

Invalid allocation size: 4294967295 bytes.”

with the options to Abort, Retry (ends up crashing the whole program) or Ignore (then I just keep getting the same error).

I won’t post all of my code because it is quite long, but I will post what I believe to be relevant and if more information is needed, let me know.

Thanks for the help!!


ColorType Trace_Ray(RayType ray)
{
	double point[3];
	ObjectType object;
	ColorType color;
	object = Find_Object(ray);

	//At this point, Find_Object has gone through all of the objects in the scene to find the closest intersection and now we must find the color there.
	if (object.t > 0) //if the ray intersects with at least one object, we can find that objects color
	{
		point[0] = ray.x + object.t * ray.dx;
		point[1] = ray.y + object.t * ray.dy;
		point[2] = ray.z + object.t * ray.dz;
		color = Shade_Ray(ray, point[0], point[1], point[2], object);
	}
	else //this ray doesn't intersect with anything and should have the default color
	{
		color.r = 0.0;
		color.g = 0.0;
		color.b = 0.0;
	}
	return color;
}


ColorType Shade_Ray(RayType ray, double x, double y, double z, ObjectType s)
{
	ColorType color;
	double S = 1.0; //shadow tag

	///////////Phong
	//Compute the normal vector at the point of intersection and the vector pointing from there to the light source
	double nd[3], n[3], ld[3], l[3]; //normal direction, normalized normal, light direction, normalized light
	if (s.label == 0)//if object is a sphere
	{
		nd[0] = x - s.x;
		nd[1] = y - s.y;
		nd[2] = z - s.z;
		n[0] = nd[0] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
		n[1] = nd[1] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
		n[2] = nd[2] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
	}
	else if (s.label == 1)//object is a triangle
	{
		double u[3], v[3];
		u[0] = s.x1 - s.x0;
		u[1] = s.y1 - s.y0;
		u[2] = s.z1 - s.z0;
		v[0] = s.x2 - s.x0;
		v[1] = s.y2 - s.y0;
		v[2] = s.z2 - s.z0;
		nd[0] = u[1]*v[2] - u[2]*v[1];
		nd[1] = u[2]*v[0] - u[0]*v[2];
		nd[2] = u[0]*v[1] - u[1]*v[0];
		n[0] = nd[0] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
		n[1] = nd[1] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
		n[2] = nd[2] / sqrt(nd[0]*nd[0] + nd[1]*nd[1] + nd[2]*nd[2]);
	}

	ld[0] = light[0] - x;
	ld[1] = light[1] - y;
	ld[2] = light[2] - z;
	l[0] = ld[0] / sqrt(ld[0]*ld[0] + ld[1]*ld[1] + ld[2]*ld[2]);
	l[1] = ld[1] / sqrt(ld[0]*ld[0] + ld[1]*ld[1] + ld[2]*ld[2]);
	l[2] = ld[2] / sqrt(ld[0]*ld[0] + ld[1]*ld[1] + ld[2]*ld[2]);

	double dotNL;
	double check_dot = n[0]*l[0] + n[1]*l[1] + n[2]*l[2];
	if (check_dot >= 0)
	{
		dotNL = check_dot;
	}
	else
	{
		dotNL = 0.0;
	}

	double hd[3], h[3];
	hd[0] = l[0] + (eye[0]-x);
	hd[1] = l[1] + (eye[1]-y);
	hd[2] = l[2] + (eye[2]-z);
	h[0] = hd[0] / sqrt(hd[0]*hd[0] + hd[1]*hd[1] + hd[2]*hd[2]);
	h[1] = hd[1] / sqrt(hd[0]*hd[0] + hd[1]*hd[1] + hd[2]*hd[2]);
	h[2] = hd[2] / sqrt(hd[0]*hd[0] + hd[1]*hd[1] + hd[2]*hd[2]);

	double dotNH = n[0]*h[0] + n[1]*h[1] + n[2]*h[2];

	////////////////// ADD SHADING ///////////////////////////////////
	for (int i = 0; i < lights.size(); i++)
	{
		RayType lightray;
		lightray.x = x; lightray.y = y; lightray.z = z; 
		//The following will NOT BE ACCURATE when multiple lights are specified!!!!!! currently only one light source is being used
		lightray.dx = l[0]; lightray.dy = l[1]; lightray.dz = l[2];

		//Check for intersections with spheres
		for (int i = 0; i < objects.size(); i++)
		{
			SphereType current = objects[i];
			double init = -1.0;
			double t;
			t = sphere_intersection(lightray, current, init);

			if (t > 0.0001)
			{
				S = S * current.trans;
			}
			if (S == 0) //we can stop if/when s = 0
			{
				i = objects.size();
			}
		}
		//Check for intersections with triangles
		if (S != 0)
		{
			for (int j = 0; j < triangles.size(); j++)
			{
				TriangleType current = triangles[j];
				double init = -1.0;
				double t;
				t = triangle_intersection(lightray, current, init);
				if (t > 0.01)
				{
					S = S * current.trans;
				}
				if (S == 0)
				{
					j = triangles.size();
				}
			}
		}
	}

	//*EVERYTHING WORKS (AT LEAST ENOUGH FOR ME TO BE SATISFIED) UP TO THIS POINT.  This is the color information due to light sources and shadows.... 

	color.r = (s.amb * s.dr + S * (s.dif * s.dr * dotNL + s.spec * pow(dotNH, s.se)));
	color.g = (s.amb * s.dg + S * (s.dif * s.dg * dotNL + s.spec * pow(dotNH, s.se)));
	color.b = (s.amb * s.db + S * (s.dif * s.db * dotNL + s.spec * pow(dotNH, s.se)));

	//Update the value of recur to the number of surfaces for which the original ray has gotten a color contribution
	recur += 1;
	
	////////////// ADD REFLECTIONS FROM OTHER OBJECTS - IF MAX RECURSION HAS NOT BEEN REACHED /////////////////
	double vector_i[3], vector_r[3], vector_t[3], vid[3], vrd[3], vtd[3];
	double NdotI, angle, angle_t;
	vid[0] = ray.x - x;
	vid[1] = ray.y - y;
	vid[2] = ray.z - z;
	vector_i[0] = vid[0]/length(vid);
	vector_i[1] = vid[1]/length(vid);
	vector_i[2] = vid[2]/length(vid);
	NdotI = dot(n, vector_i);
	angle = acos(NdotI) * 180.0/PI;
	angle_t = (acos(sqrt(1 - ((s.iors/s.iorm)*(s.iors/s.iorm)*(1-(cos(angle*PI/180.0)*cos(angle*PI/180)))))))*(180.0/PI);
	vtd[0] = cos(angle_t * PI/180.0)*(-(n[0])) + (s.iors/s.iorm)*(cos(angle * PI/180.0)*n[0] - vector_i[0]);
	vtd[1] = cos(angle_t * PI/180.0)*(-(n[1])) + (s.iors/s.iorm)*(cos(angle * PI/180.0)*n[1] - vector_i[1]);
	vtd[2] = cos(angle_t * PI/180.0)*(-(n[2])) + (s.iors/s.iorm)*(cos(angle * PI/180.0)*n[2] - vector_i[2]);
	vector_t[0] = vtd[0]/length(vtd);
	vector_t[1] = vtd[1]/length(vtd);
	vector_t[2] = vtd[2]/length(vtd);

	if (recur <= MAX_RECURSION)
	{
		double length_a;

		length_a = cos(angle * PI/180);

		vrd[0] = 2*length_a*n[0] - vector_i[0];
		vrd[1] = 2*length_a*n[1] - vector_i[1];
		vrd[2] = 2*length_a*n[2] - vector_i[2];

		vector_r[0] = vrd[0]/length(vrd);
		vector_r[1] = vrd[1]/length(vrd);
		vector_r[2] = vrd[2]/length(vrd);

		RayType new_ray;
		new_ray.dx = vector_r[0];
		new_ray.dy = vector_r[1];
		new_ray.dz = vector_r[2];
		new_ray.x = x; new_ray.y = y; new_ray.z = z;

		//Now we must trace vector R to find the contribution from reflection
		ColorType temp_color;
		ObjectType temp_object;

		temp_object = Find_Object(new_ray);//Find_Object just returns the closest object (for positive t values)
		if ( temp_object.t > 0.001 )
		{
			double point[3];
			point[0] = new_ray.x + temp_object.t * new_ray.dx; point[1] = new_ray.y + temp_object.t * new_ray.dy; point[2] = new_ray.z + temp_object.t * new_ray.dz;
			temp_color = Shade_Ray(new_ray, point[0], point[1], point[2], temp_object);		
		}
		else
		{//didn't intersect an object, so we are done
			recur = MAX_RECURSION + 1;
			temp_color.r = 0.0; temp_color.g = 0.0; temp_color.b = 0.0;
		}
		color.r += temp_object.spec * temp_color.r; color.g += temp_object.spec * temp_color.g; color.b += temp_object.spec * temp_color.b;
	}
	///////////////////////////////////////////////////////////////////
	//////////// REFRACTION ///////////////////////////////////////////
	if (s.trans > 0.1) //s is current object, trans is its transparency
	{
		RayType new_ray_t;
		new_ray_t.x = x; new_ray_t.y = y; new_ray_t.z = z;
		new_ray_t.dx = vector_t[0]; new_ray_t.dy = vector_t[1]; new_ray_t.dz = vector_t[2];
		ColorType temp_color_t;
		ObjectType temp_object_t;

		temp_object_t = Find_Object(new_ray_t);
		if (temp_object_t.t > 0.001)
		{
			double point[3];
			point[0] = new_ray_t.x + temp_object_t.t * new_ray_t.dx; point[1] = new_ray_t.y + temp_object_t.t * new_ray_t.dy; point[2] = new_ray_t.z + temp_object_t.t * new_ray_t.dz;
			temp_color_t = Shade_Ray(new_ray_t, point[0], point[1], point[2], temp_object_t);
		}
		else
		{
			recur = MAX_RECURSION + 1;
			temp_color_t.r = 0.0; temp_color_t.g = 0.0; temp_color_t.b = 0.0;
		}
		color.r += temp_object_t.trans * temp_color_t.r; color.g += temp_object_t.trans * temp_color_t.g; color.b += temp_object_t.trans * temp_color_t.b;

	}

	color.r = 255.0*color.r;
	color.g = 255.0*color.g;
	color.b = 255.0*color.b;

	return color;
}

By really grainy, you mean just the areas that have reflection and refraction, correct? Can you post an image?

  new_ray.dx = vector_r[0];
  new_ray.dy = vector_r[1];
  new_ray.dz = vector_r[2];
  new_ray.x = x; new_ray.y = y; new_ray.z = z;
  //Now we must trace vector R to find the contribution from reflection
  ColorType temp_color;
  ObjectType temp_object;
  temp_object = Find_Object(new_ray);//Find_Object just returns the closest object (for positive t values)
  if ( temp_object.t &gt; 0.001 )
  {
  	double point[3];
  	point[0] = new_ray.x + temp_object.t * new_ray.dx; point[1] = new_ray.y + temp_object.t * new_ray.dy; point[2] = new_ray.z + temp_object.t * new_ray.dz;
  	temp_color = Shade_Ray(new_ray, point[0], point[1], point[2], temp_object);		
  }
  else
  {//didn't intersect an object, so we are done

Looking at your code the only problem I could see is you don’t offset your reflection ray from the surface. I think it’s typical to do so to avoid self intersection. Can I assume your Find_Object returns negative if it doesn’t hit anything?

I’m guessing you’re self-intersecting your original surface you’re reflecting off of. Try offsetting your ray position from the surface or decrease your threshold. If decreasing the threshold makes it less grainy, that’s probably you’re issue.

Yes, Find_Object returns negative unless it hits something…

I keep tweaking and I think you are right in that my reflection rays are self-intersecting… Is offsetting the ray position a common way to avoid this? (I thought that only accepting values of t > some small epsilon value would do the same? I do that in my code) …

Also, it occurred to me that refraction rays that go through spheres will hit their own back side. 1) Am I correct in assuming that this is not what I want? 2) Any suggestions as to how to avoid this? I’m working on that right now, but unfortunately the way my code is organized makes it tricky.

Anyway, as you can tell I am still slightly clueless in finding the problem, so if anything else occurs to you let me know! Thank you for the help!

That’s not really any other way around it than excluding the actual object you’re reflecting off of. The problem is that when you calculate the ray position based on how far the ray has traveled to get there, you’re new position doesn’t lie exactly on the primitive you intersect (due to floating-point limitations). The ray is then facing the correct direction since you calculate it from the normal, but its origin can be on either side of the surface. Usually you just have to calculate the position and add a small amount to it in the direction of the normal multiplied by some epsilon to keep it out of the way of hitting it again.

For refraction, you can just move the ray in the opposite direction of the normal, but then you have the problem along flat areas, where your displaced ray pops out of the object before refracting through it.

There’s a running joke “raster guys” have about ray tracers that as they get more and more complex, epsilons become littered everywhere and they get more and more difficult to tweak per scene.

It’s all about the epsilons! Hope that helps.

refraction rays that go through spheres will hit their own back side

And this is the correct way.
Though I have seen some “toy” raytracers that only counted front faces … :ugly hack:
In reality photons slow down when they enter a block of glass, then accelerate back to original speed when then exit … if, of course, total internal refraction do not prevent that.