[ Imager TR Home Page ]
[ Imager Home Page ]
[ UBC CS Home Page ]
A
Ray
Tracing
Accelerator
Based on a
Hierarchy of
1D
Sorted
Lists
Alain
Fournier and
Pierre
Poulin
Appeared in Graphics Interface '93 (pp. 53-61; Toronto, Ontario)
TR-92-37
ABSTRACT
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.