Abstract: Shadow ray traversal is abig computation bottleneck in ray tracing. However, constructing an efficient tree to cull down redundant intersections is quite difficult. We propose a Multiple-index Tree based on shadow ray traversal algorithm, which adds indexes for nodes to accelerate traversal with acceptable pre-computation. First, since occluded rays try to intersect with primitive, we select primitives with high intersection probability from leaf nodes to store in inner nodes, which aims to stop traversal in upper tree. Second, since un-occluded rays try to find the nearest node, we create adjacency indexes between nodes in bottom tree, and use the indexes to access next node along ray direction directly. During traversal, by exploiting frame coherence, we estimate the occlusion type of rays and use corresponding method to reduce traversal cost. The experimental result suggest that the algorithm can improve traversal performance more than 20% for complex scenes. Even compared with tree reconstruction method, our method outperforms in reducing more intersections and only consumes 21% pre-computation time.

Key words: ray tracing, shadow ray traversal, hierarchy acceleration structure, branch decision