A Survey of Geometric Data Structures for Ray Tracing
TR-CIS-2001-06
Allen Y.Chang

pdf version of this paper

Abstract:
Ray tracing is a computer graphics technique for generating photo-realistic images. To determine the color at each pixel of the image, one traces the path traversed by each ray of light arriving at the pixel back through several reflections and/or refractions. The most time-consuming phase of a ray tracer is ray traversal, which determines for each of a large number of rays, the first object met by that ray. Many data structures have been proposed to accelerate this process. This survey describes and compares the construction and traversal algorithms for a variety of commonly used data structures from practitioner's point of view.