Fundamentals of Computer Graphics, 3rd Edition

i

i

i

i

i

i

i

i

4

Ray Tracing

One of the basic tasks of computer graphics is rendering three-dimensional ob-

jects: taking a scene, or model, composed of many geometric objects arranged

in 3D space and producing a 2D image that shows the objects as viewed from

a particular viewpoint. It is the same operation that has been done for centuries

by architects and engineers creating drawings to communicate their designs to

others.

Fundamentally, rendering is a process that takesas its input a set of objects and

produces as its output an array of pixels. One way or another, rendering involves

If the output is a vector

image rather than a raster

image, rendering doesn’t

have to involve pixels, but

we’ll assume raster images

in this book.

considering how each object contributes to each pixel; it can be organized in two

general ways. In object-order rendering, each object is considered in turn, and

for each object all the pixels that it influences are found and updated. In image-

order rendering, each pixel is considered in turn, and for each pixel all the objects

that influence it are found and the pixel value is computed. You can think of

the difference in terms of the nesting of loops: in image-order rendering the “for

each pixel” loop is on the outside, whereas in object-order rendering the “for each

object” loop is on the outside.

Image-order and object-order rendering approaches can compute exactly the

same images, but they lend themselves to computing different kinds of effects

and have quite different performance characteristics. We’ll explore the compara-

In a ray tracer it is easy to

compute accurate shadows

and reflections, which are

awkward in the object-order

framework.

tive strengths of the approaches in Chapter 8 after we have discussed them both,

but, broadly speaking, image-order rendering is simpler to get working and more

flexible in the effects that can be produced, and usually (though not always) takes

much more execution time to produce a comparable image.

69

i

i

i

i

i

i

i

i

70 4. Ray Tracing

Figure 4.1. The ray is “traced” into the scene and the first object hit is the one seen through

the pixel. In this case, the triangle

T

2

is returned.

Ray tracing is an image-order algorithm for making renderings of 3D scenes,

and we’ll consider it first because it’s possible to get a ray tracer working with-

out developing any of the mathematical machinery that’s used for object-order

rendering.

4.1 The Basic Ray-Tracing Algorithm

A ray tracer works by computing one pixel at a time, and for each pixel the basic

task is to find the object that is seen at that pixel’s position in the image. Each

pixel “looks” in a different direction, and any object that is seen by a pixel must

intersect the viewing ray, a line that emanates from the viewpoint in the direction

that pixel is looking. The particular object we want is the one that intersects

the viewing ray nearest the camera, since it blocks the view of any other objects

behind it. Once that object is found, a shading computation uses the intersection

point, surface normal, and other information (depending on the desired type of

rendering) to determine the color of the pixel. This is shown in Figure 4.1, where

the ray intersects two triangles, but only the first triangle hit, T

2

, is shaded.

A basic ray tracer therefore has three parts:

1. ray generation, which computes the origin and direction of each pixel’s

viewing ray based on the camera geometry;

2. ray intersection,whichfinds the closest object intersecting the viewing ray;

3. shading, which computes the pixel color based on the results of ray inter-

section.