Although three-dimensional computer graphics have been around for many decades, there has been a surge of general interest towards the field in the last couple of years. Just a quick glance at the latest blockbuster movies is enough to see the public's fascination with the new generation of graphics. As exciting as graphics are, however, there is a definite barrier which prevents most people from learning about them. For one thing, there is a lot of math and theory involved. Beyond that, just getting a window to display even simple 2D graphics can often be a daunting task. In this article, we will talk about a powerful yet simple 3D graphics method known as

Figure 1. Ray traced image

As you may have guessed, our goal is find the color of each point on the view window. We subdivide the view window into small squares, where each square corresponds to one pixel in the final image. If you want to create an image at the resolution of 640x400, you would break up the view window into a grid of 640 squares across and 400 square down. The real problem, then, is assigning a color to each square. This is what ray tracing does.

Figure 2. The eye, view window, and world.

Figure 3. Tracing rays from the light source to the eye. Lots of rays are wasted because they never reach the eye.

In order to save ourselves this wasted effort, we trace only those rays that are

This, then, is how ray tracing works in computer graphics. For each pixel on the view window, we define a ray that extends from the eye to that point. We follow this ray out into the scene and as it bounces off of different objects. The final color of the ray (and therefore of the corresponding pixel) is given by the colors of the objects hit by the ray as it travels through the scene.

Just as in the light-source-to-eye method it might take a very large number of bounces before the ray ever hits the eye, in backwards method it might take many bounces before the ray every hits the light. Since we need to establish some limit on the number of bounces to follow the ray on, we make the following approximation: every time a ray hits an object, we follow a single new ray from the point of intersection

Figure 4. We trace a new ray from each ray-object intersection directly towards the light source

In the figure we see two rays,

If an object is reflective we simply trace a new

Figure 5. (a) Reflected ray. (b) Refracted ray

The directions of the reflected and refracted rays are given by the following formulas. For a ray with direction

c1 = -**dot_product**( N, V )

Rl = V + (2 * N * c1 )

Note that since
n1 = index of refraction of original medium

n2 = index of refraction of new medium

n = n1 / n2

c2 = **sqrt**( 1 - n^{2} * (1 - c1^{2}) )

Rr = (n * V) + (n * c1 - c2) * N

Figure 6. Recursive reflection and refraction

Figure 6 shows an example of objects that are both reflective and refractive (it does not show the rays from each intersection to the light source, for the sake of clarity). Note how much more complicated the rays become once reflection and refraction are added. Now, each reflected and refracted ray can strike an object which spawns another two rays, each of

```
```**Color trace_ray**( **Ray** original_ray )

{

**Color** point_color, reflect_color, refract_color

**Object** obj

obj = **get_first_intersection**( original_ray )

point_color = **get_point_color**( obj )

if ( object is reflective )

reflect_color = **trace_ray**( **get_reflected_ray**( original_ray, obj ) )

if ( object is refractive )

refract_color = **trace_ray**( **get_refracted_ray**( original_ray, obj ) )

return ( **combine_colors**( point_color, reflect_color, refract_color ))

}

where a

**Color**

is the triple (Figure 7. Intersection of a ray with a sphere.

Fig. 7 shows the geometry of a ray

- v

- d =

```
v =
```**dot_product**( EO, V )

disc = r^{2} - ((**dot_product**( EO, EO ) - v^{2} )

if ( disc < 0 )
no intersection

else
d = **sqrt**( disc )

P = E + (v - d) * V

In case the result of the dot product is zero or below zero, we still may not want that part of the object to be pitch-black. After all, even when an object is completely blocked from a light source, there is still light bouncing around that illuminates it to some extent. For this reason we add a little bit of ambient light to every object, which means that the

```
shade =
```**dot_product**( light_vector, normal_vector )

if ( shade < 0 )
shade = 0

point_color = object_color * ( ambient_coefficient +

`diffuse_coefficient * shade )`

While texture mapping produces very nice effects, it is not a difficult feature to implement. All that is needed is a routine which returns the coordinates of a texture pixel given the coordinates of a point on an object. The texture coordinates are refered to as (

Figure 8. Mapping a rectangular world map onto a globe

Figure 9. Mapping a texture image onto a sphere

First we find the two unit-length vectors

`phi = `**arccos**( -**dot_product**( **V**_{n}, **V**_{p} ))

**v** = phi / **PI**

```
theta = ( arccos(
```**dot_product**( **V**_{p}, **V**_{e} ) /
**sin**( phi )) ) / ( 2 * **PI**)

if ( **dot_product**( **cross_product**( **V**_{n}, **V**_{e} ), **V**_{p} ) > 0 )

u = theta

else

u = 1 - theta

```
```

The last comparison simply checks on what side of the equator vector
First, we need to define the scene we want to render. We create a text input file that describes the objects in the scene by specifying the location, attributes (such as radius for spheres), color, and optional texture map of each object. We then specify where the camera and the view window should be located. For simplicity, we can assume that the camera is always on the Z axis pointing towards the origin, and that the view window is located at the origin. We also need to determine the size of the view window, which is specified by a

Now that we have the top-left and bottom-right points, we divide the window into the resolution required for our output picture, e.g., 640 by 400. We step through each of the 640x400 points on the view window, defining a ray from the eye to that point. For each ray, we calculate its intersection with all the objects in the scene. If it does not intersect any objects, we set the ray - and therefore the corresponding pixel - to the background color. Otherwise, we choose the object with the closest intersection. If the object is reflective, we call the ray-tracing function again recursively, passing it the reflected ray direction. If the object is transparent, we do the same thing with the refracted direction. The calling function then computes the color for the object it is dealing with, and combines this color with the reflected and refracted rays' colors.

When the original ray-tracing call from the eye to the view window returns, the color will be the final color for that pixel - taking into account reflection, refraction, and shadows. This pixel color is then written out to the output file. When all points on the view window have been processed this way, you will have a finished ray-traced picture.

- There's a free, powerful ray tracing program called
*POV-Ray*(for Persistence of Vision Ray Tracer), available for almost every platform at http://www.povray.org. It comes in both binary and source form, and their web page has links to other ray tracing information as well as a beautiful gallery of images created with POV-Ray. - Radiance ( http://radsite.lbl.gov/radiance/HOME.html ) is a ray tracer geared towards analysis of lighting, rather than just making pretty pictures.
- Rayshade ( http://www-graphics.stanford.edu/~cek/rayshade/rayshade.html) is a fast ray tracer with support for parallel processing.
- The Blue Moon Rendering Tools ( http://www.seas.gwu.edu/student/gritz/bmrt.html) is a ray tracer that implements the Renderman shading language. This language is used by such companies as Industrial Light & Magic and Pixar to create just about every mind-blowing computer special effect in the last twenty years. The professional software is rather expensive, so this free package by Larry Gritz is an ideal way to play with the Renderman language.
- A good general ray tracing page can be found at http://www.cm.cf.ac.uk/Ray.Tracing/, with links to ray tracing information and more ray-tracing software.
- The Ray Tracing News ( http://www.acm.org/tog/resources/RTNews/html/index.html ) is a electronic publication with lots of good info on Ray Tracing.

**1**-
Cook, R.L., and Torrance, K.E. A Reflectance Model for Computer Graphics.
*ACM Trans. on Graphics*1, 1 (Jan 1982) **2**- Foley, J. D., and Van Dam, A.
*Computer Graphics: Principles and Practice, Second Edition.*Addison-Wesley New York, N.Y. 1990. **3**- Glassner, A. (ed)
*An Introduction to Ray Tracing.*Academic Press New York, N.Y. 1989.

**4**- Glassner, A. (ed)
*Graphics Gems.*Academic Press New York, N.Y. 1990. **5**- Watt, A., and Watt, M.
*Advanced Animation and Rendering Techniques.*Addison-Wesley New York, N.Y. 1990.