Graphics Reference
In-Depth Information
2.5.3 GPU Ray Tracing
In 2002, Timothy J. Purcell, Ian Buck, William R. Mark, and Pat Hanrahan pub-
lished a paper entitled “Ray Tracing on Programmable Graphics Hardware” [Pur-
cell et al. 02] that describes how to do ray tracing entirely on graphics hardware.
This was a significant accomplishment, because GPU programming was still very
limited at the time. The algorithm works on scenes composed only of triangles
(this is not very restrictive; CG environments are often triangulated). An effi-
ciency structure is employed to minimize unnecessary ray intersection tests. The
structure is a uniform 3D grid consisting of 3D rectangular cells. Each cell con-
tains a list of the triangles that intersect the cell.
The paper describes the algorithm in terms of an abstraction of GPU pipelines
known as
streams
, which are essentially arbitrarily long sequences of data. In
general,
input streams
are converted to
output streams
, and the same computation
applies to each element in a stream. Operations can be performed on multiple
streams in parallel. The instructions that convert the input stream to the output
stream are called a
kernel
. In Purcell's approach, ray tracing is done in four steps,
each with its own kernel:
1. creation of rays (from the point of view),
2. traversing the efficiency (grid) structure,
3. ray-triangle intersection tests, and
4. shading.
The processes and associated data arrangements are illustrated in Figure 2.15.
In Step 1 a ray is shot from each pixel of the framebuffer. In Step 2 these
rays are traced through the grid cells. In Step 3 objects within each grid cell are
tested for intersection. If an intersection is found, the next step is Step 4, in which
the pixel color is computed, and then secondary rays are shot. Every time a pixel
value changes, the whole framebuffer is redrawn, and the process continues until
each ray has stopped.
Although the algorithm described above was well known at the time, Purcell's
paper showed how to implement it entirely on a GPU. A major limitation to GPU
programming is the lack of data structures. About the only structures available
are the framebuffer, stencil buffer, and texture maps. A
texture map
is a simply
a rectangular array of pixels, normally of three (RGB) or four (RGB) channels,
but other formats are available. Texture map pixels are known as
texels
.InPur-
cell's algorithm, the scene triangles are stored in texture maps. The grid is stored
sequentially in an integer-valued texture map, with one texel for each grid cell.
