back to table of contents

Basics
download mac os x application and source code (60k)
First released wednesday october 17, 2001. Developed with apple's free developer tools on mac os 10.1
This document, images, source and application are the intellectual property of forrest briggs. You may freely use the source code i provide. Email me with questions or suggestions.

Introduction

A ray tracer is a piece of software that is used to represent 3 dimensional data as an image. Unlike traditional polygonal 3d engines, ray tracers excel at rendering curved surfaces, shadows and reflections. It is for these reasons that ray tracing has long been the method of choice for professionally rendered 3d graphics and movie special effects. This greater functionality comes at the price of speed, which is why until recently, Ray tracers could not be used in realtime. With todays home supercomputers, the days when ray tracing was relegated to use exclusively on ridiculously expensive machines that took days at a time to render a single frame are over.

Raytracing works by projecting a ray of vision through each pixel on the screen from the observer. Notice that where the rays through the screen intersect an object, it is projected onto the screen. Generally, raytracing uses objects that can be defined mathematically by 1st or 2nd degree equations. For every pixel on the screen, an equation involving the ray through that pixel from the observer and each object in the scene Is solved to determine if the ray intersects the object. Then, the pixel through which the ray passes is set to the color of the intersected object at the point of intersection. If more than one object is intersected, then the Closer of the intersections is taken.

Reflections and shadows are achieved through what is known as recursive ray tracing. When figuring out the color of the intersection, one important factor is whether that point is in shadow or not. To find this out, the same Techniques are used, but instead of the normal location of the observer, the ray starts at the point of intersection and moves toward any light sources. If it intersects something, then the point is in shadow. When a reflective Surface is intersected, a new ray is traced starting from the point of intersection. The color that this ray returns is incorporated into the color of the original intersection. The process is called recursive because reflected Rays can spawn more reflected rays as long as they keep intersecting reflective objects.

The focus of this series of tutorials is coding a highly optimized ray tracer in mac os x. I assume that you, the reader are familiar with linear algebra and vectors (flipcode has tutorials if you arent,) as well as c/c++. I will not spend time discussing the platform specific Details of the graphics implementation; i assume that you can figure these out and if necessary, adapt the code i present to your platform.

The Ray Tracing Algorithm

To generate an image, mathematical rays are "fired" from a common origin (the camera or observer) through each pixel on the screen. Each ray is tested against each object in the scene to determine if the ray Intersects the object. The distance from the observer to the intersections is calculated and the color of the closest intersected object is used for the pixel through which the ray is fired. After this, additional Steps are performed to shade the objects, but that is a topic for subsequent sections. A ray is defined as an origin and a direction, both of which are represented by a vector data structure.

The following code generates the direction of the rays: 
Vector* GenerateRayDirectionTable()
{
	Vector *direction = new Vector[640*480];

	For(int y=0; y<480; y++)
	{
		For(int x=0; x<640; x++)
		{
			Vector &currDirection = direction[x+y*640];
			CurrDirection.X = x - 320;
			CurrDirection.Y = y - 240;
			CurrDirection.Z = 255; // this value is fairly arbitrary and can basically be interpreted as field of view
			VectorNormalize(currDirection);
		}
	}
	Return direction;
}
The directions are stored in a lookup table that is accessed in the main loop of the program. Imagine that the observer is a point floating 255 units out from the center of the screen. The directions being calculated are the vectors From the observer, through every pixel. These vectors must be normalized, that is, their length be made 1, for them to work mathematically in the intersection algorithms. Normalizing a vector requires a square root, so a substantial Performance gain can be had by precalculating them (20fps on my machine.)

In the main loop, which traces a ray through every pixel on the screen, these directions are loaded and combined with an origin to form the ray through that pixel; 
Ray primaryRay;
PrimaryRay.Origin.X = 0;
PrimaryRay.Origin.Y = 0;
PrimaryRay.Origin.Z = -600;
    		
...
    
PrimaryRay.Direction = directionTable[x + (y<<9) + (y<<7)];
Notice that directionTable[x + (y<<9) + (y<<7)] means the same thing as directionTable[x + y*640]. PrimaryRay now contains all of the information necessary to trace it through the scene.

It is now time to determine which, if any objects intersect this ray and which of them is closest. 
Float closestIntersectionDistance = 1000000; // an impossibly large value
Int closestIntersectedSphereNum = -1;
TraceResult currResult;    

For(int currSphereNum=0; currSphereNum < numSpheres; currSphereNum++ ) // cycle through all of the spheres to find the closest interesction
{
	IntersectSphere(primaryRay,spheres[currSphereNum],currResult);
	If(currResult.Hit)
	{
		If(currResult.Distance < closestIntersectionDistance)
		{
			ClosestIntersectionDistance = currResult.Distance;
			ClosestIntersectedSphereNum = currSphereNum;
		}
	}
}
The IntersectSphere() function is called for every sphere with the primary ray. If the ray intersects the sphere, the function sets currResult.Hit to true and currResult.Distance to the distance from the origin of the ray to the intersection Between the ray and the sphere. Otherwise, it sets currResult.Hit to false. ClosestIntersectedSphereNum tracks which sphere has yielded the closest intersection. By default, it contains -1, indicating that no spheres have yet been intersected. After the IntersectSphere function is called, and if it did intersect the sphere, then if the distance to the intersection is closer than the closest intersection so far (which starts out as a value so far that any intersection at all will be Closer,) then the closest intersection data is updated to reflect the new closest intersection. Once all of the spheres have been tested, either closestIntersectedSphere will be equal to -1, in which case no spheres at all are intersected, or It will be equal to the number of the sphere that is closest in the ray and the distance will be the distance to that intersection.

It is now possible to assign a color to the current pixel. If no spheres were intersected by the ray through that pixel, then the color is the background color. Otherwise, it is the color of the closest sphere (later we will learn how To shade, reflect and shadow this color.)

The function that is most difficult to understand is the ray-sphere intersection function. There are two common ways to calculate whether a ray intersects a sphere and if so, at what distance. In the example code, i use the geometric solution, Which is faster. I will also describe how the algebraic solution works, because it may be helpful to your conceptual understanding of ray tracing and in deriving the intersection with objects besides spheres, but no sample code will be present.

The Algebraic Solution

The mathematical equation for a sphere is given as
(x-a)2 + (y-b)2 + (z-c)2 = r2
Where (x,y,z) is any point on the sphere, (a,b,c) is the location of the sphere's center and r is the sphere's Radius. We can also say that
X=xo+xdt
Y=yo+ydt
Z=zo+zdt
Where (xo,yo,yo) is the origin of the ray and (xd,yd,yd) is the camera ray's direction. Substituting the ray's equation into the sphere's equation, we get
(xo+xdt-a)2+ (yo+ydt-b)2+ (zo+zdt-c)2 = r2
Which simplifies to
(xd2 + yd2 + zd2)t2+ [2[xd(xo - a) + yd (yo - b) + zd (zo - c)]]t + [(xo - a)2 + (yo - b)2 + (zo - c)2 - r2] = 0
We can then solve for t in order to determine whether the sphere is intersected with the quadratic formula (At2 + Bt + C = 0) Where
A = xd2 + yd2 + zd2
B = 2[xd(xo - a) + yd (yo - b) + zd (zo - c)]
C = (xo - a)2 + (yo - b)2 + (zo - c)2 - r2
Then
T = -B+-sqrt(B2-4AC)
     ------------------------
                   2A
If B2-4AC<0, then ray and sphere do not intersect (the intersections are imaginary numbers)
If B2-4AC=0, then the ray intersects the sphere at exactly 1 point
If B2-4AC>0, then the ray intersects the sphere at exactly 2 points (the only result that we will continue to solve)
The two solutions to this equation are:
T1=-B+sqrt(B2-4AC)
     ------------------------
                   2A
T2=-B-sqrt(B2-4AC)
     ------------------------
                   2A
Let tc equal the lesser of t1 and t2 (as long as it isnt less than 0, which means that the intersection is behind the origin of the ray.) Tc is the distance from the origin of the ray to the closest intersection between the ray and the sphere.
Finally, from tc, we can find the point of intersection, which will be useful later:
Xi = xo + xdtc
Yi = yo + ydtc
Zi = zo + zdtc
Where (xi,yi,zi) is the intersection

If this makes no sense at all, dont worry about it. The geometric solution has pictures! Later i will derive the intersection of a ray and a plane, which is like the above, but simpler. Once you understand that, come back to this.

The geometric solution

First, even though i said i would assume you know vectors, i will briefly explain how to get the dot product between two vectors (though not what the dot product is. Ill give a little more when we go into shading.) The dot product is an operation performed on two vectors that returns a scalar (non-vector) number. If vector a is defined by the components (ax,ay,az) and vector b is (bx,by,bz) And s=a · b (that is, the scalar s is equal to the dot product of Vectors a and b,) then s = ax * bx + ay * by + az * bz.
The information we need to determine intersection is the ray's origin and direction and the sphere's center and radius (fig 1.)
Let the vector from the origin of the ray to the center of the sphere be oc. Oc = sc - ro, where sc is the center of the sphere and ro is the origin of the ray.
Let the closest approach of the ray to the sphere be tca. Tca = oc · rd where rd is the direction of the ray (fig 2.) If tca is less than 0, then the intersection with the sphere Is behind the origin of the ray and should be discarded
Let the length of oc squared be loc2. Loc2 = oc · oc
Let the distance from the center of the sphere to the closest approach be d. Because of the pythagorean theorem, d2 = loc2 - tca2 (figure 3.)
Let half of the length of the cord formed by the intersection of the ray and the sphere be thc. Thc2 = sr2 - d2 (figure 4.) If thc2 is less than 0 (which Is mathematically impossible,) then the ray misses the sphere. If not, then the distance from the origin of the ray to the closest intersection of the sphere (assuming that the ray does not originate within the sphere, which is a special case That i will leave as an exercise to the reader,) is equal to tca - thc. In other words, t = tca - sqrt(thc2)
If you examine the IntersectSphere() function, you will see that it follows these steps.