LCTS: Ray Shooting using Longest Common Traversal Sequences

Abstract

We describe two new techniques of ray shooting acceleration that exploit the traversal coherence of a spatial hierarchy. The first technique determines a sequence of adjacent leaf-cells of the hierarchy that is pierced by all rays contained within a certain convex shaft. This sequence is used to accelerate ray shooting for all remaining rays within the shaft. The second technique establishes a cut of the hierarchy that contains nodes where the hierarchy traversal can no longer be predetermined for all rays contained within a given shaft. This cut is used to initiate the traversal for all remaining rays contained in the shaft. The description of the methods is followed by results evaluated by their practical implementation.