Technical Reports

The ICICS/CS Reading Room

UBC CS TR-92-37 Summary

A Ray Tracing Accelerator Based on a Hierarchy of 1D Sorted Lists, October 30, 1992 Alain Fournier and Pierre Poulin, 9 pages

Since the introduction of ray tracing as a rendering technique, several approaches have been proposed to reduce the number of ray/object tests. This paper presents yet another such approach based on a hierarchy of 1D sorted lists. A bounding box aligned with the axes encloses an object. The coordinates of each bounding box are ordered in three sorted lists (one for each axis) and are treated as events. Traversing a scene with a ray consists of traversing each sorted list in order, intersecting an object only when for this object a first event has been encountered (entered) in every dimension before a second event has been encountered (exited) in any dimension. To reduce the number of events (entries and exits) traversed, a hierarchy of sorted lists is constructed from a hierarchy of bounding boxes. The results are favourable for scenes ranging from moderate to high complexity. Further applications of the technique to hardware assist for ray tracing and to collision detection are discussed.

If you have any questions or comments regarding this page please send mail to