A Ray Tracing Accelerator Based on a Hierarchy
of 1D Sorted Lists
Alain Fournier
and Pierre
Poulin
Proc. Graphics Interface, May 1993
Abstract
Since the introduction of ray tracing as a rendering technique,
several approaches have been proposed to reduce the number of ray/object
intersection 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.
BibTeX entry
@InProceedings{Fournier:1993:RTA,
author = "Alain Fournier and Pierre Poulin",
title = "A Ray Tracing Accelerator Based on a Hierarchy of 1{D}
Sorted Lists",
year = "1993",
month = may,
booktitle = "Proceedings of Graphics Interface '93",
publisher = "Canadian Information Processing Society",
pages = "53--61",
address = "Toronto, Ontario",
keywords = "efficiency",
}
Online Version
Postscript available here
