“Fast ray tracing by ray classification” by Arvo and Kirk

We describe a new approach to ray tracing which drastically reduces the number of ray-object and ray-bounds intersection calculations by means of 5-dimensional space subdivision. Collections of rays originating from a common 3D rectangular volume and directed through a 2D solid angle are represented as hypercubes in 5-space. A 5D volume bounding the space of rays is dynamically subdivided into hypercubes, each linked to a set of objects which are candidates for intersection. Rays are classified into unique hypercubes and checked for intersection with the associated candidate object set. We compare several techniques for object extent testing, including boxes, spheres, plane-sets, and convex polyhedra. In addition, we examine optimizations made possible by the directional nature of the algorithm, such as sorting, caching and backface culling. Results indicate that this algorithm significantly outperforms previous ray tracing techniques, especially for comples environments.

1. Amanatides, John., “Ray Tracing with Cones,” Computer Graphics, 18(3), July 1984, pp. 129-135.]]
2. Cook, Robert L., Thomas Porter, and Loren Carpenter., “Distributed Ray Tracing,” Computer Graphics 18(3), July 1984, pp. 137-145.]]
3. Fujimoto, Akira,, and Kansei Iwata., “Accelerated Ray Tracing,” Proceedings of Computer Graphics Tokyo ’85, April 1985.]]
4. Glassner, Andrew S., “Space Subdivision for Fast Ray Tracing,” IEEE Computer Graphics and Applications, 4(10), October, 1984, pp. 15-22.]]
5. Johnson, Lee W., and Riess, Dean R., “Numerical Analysis,” Addison-Wesley, 1977.]]
6. Kajiya, James T., “The Rendering Equation,” Computer Graphics 20(4), August 1986, pp. 143-150.]]
7. Kaplan, Michael R., “Space Tracing: A Constant Time Ray Tracer,” ACM SIGGRAPH ’85 Course Notes 11, July 22-26, 1985.]]
8. Kay, Timothy L. and James Kajiya., “Ray Tracing Complex Scenes,” Computer Graphics, 20(4), August 1986, pp. 269-278.]]
9. Kirk, David B., “The Simulation of Natural Features using Cone Tracing,” Advanced Computer Graphics (Proceedings of Computer Graphics Tokyo ’86), April 1986, pp. 129-144.]]
10. Newman, William M., and Robert F. Sproull., “Principles of Interactive Computer Graphics,” 1st edition, McGraw-Hill, New York, 1973.]]
11. Ortega, James M., “Numerical Analysis, A Second Course,” Academic Press, New York, 1972.]]
12. Preparata, Franco P., and Michael I. Shamos., “Computational Geometry, an Introduction,” Springer-Verlag, New York, 1985.]]
13. Press, William H., Brian P..Flannery, Saul A. Teukolsky, William T. Vetterling., “Numerical Recipes,” Cambridge University Press, Cambridge, 1986.]]
14. Rubin, Steve, and Turner Whitted., “A Three-Dimensional Representation for Fast Rendering of Complex Scenes,” Computer Graphics 14(3), July 1980, pp. 110-116.]]
15. Speer, L. Richard, Tony D. DeRose, and Brian A. Barsky., “A Theoretical and Empirical Analysis of Coherent Ray Tracing,” Computer-Generated Images (Proceedings of Graphics Interface ’85), May 27-31, 1985, pp. 11-25.]]
16. Warnock, John E., “A Hidden-Surface Algorithm for Computer Generated Half-tone Pictures,”, Ph.D. Dissertation, University of Utah, TR 4-15, 1969.]]
17. Weghorst, Hank, Gary Hooper, and Donald Greenberg., “Improved Computational Methods for Ray Tracing,” ACM Transactions on Graphics, 3(1), January 1984, po. 52-69.]]