Ray tracing using dynamic subtree—algorithm and speed evaluation
Tadashi Naruse, Mikio Shinya, Takafumi Saito · Systems and Computers in Japan · 1993
Abstract For fast ray tracing computation, it is essential to determine efficiently which object is projected on each pixel of the image plane. The data structure plays a major role in this process, and a hierarchical tree data structure of the objects often is used. This paper proposes a very fast algorithm based on use of a subtree of given hierarchical tree. Experimental results show that the number of intersection computations can be reduced greatly by the use of subtrees and that the computation cost for dynamic construction of a subtree is low. Analysis of the algorithm supports the experimental results. Experimental comparison with Arvo's algorithm [6], one of the fastest existing algorithms, shows that our algorithm is faster for primary rays.