“Ray tracing complex scenes” by Kay and Kajiya

A new algorithm for speeding up ray-object intersection calculations is presented. Objects are bounded by a new type of extent, which can be made to fit convex hulls arbitrarily tightly. The objects are placed into a hierarchy. A new hierarchy traversal algorithm is presented which is efficient in the sense that objects along the ray are queried in an efficient order.Results are presented which demonstrate that our technique is several times faster than other published algorithms. Furthermore, we demonstrate that it is currently possible to ray trace scenes containing hundreds of thousands of objects.

1. Apostol, Tom M., Calculus, Volume II, Wiley, New York, 1969, pp. 314-318.
2. Barr, Alan H., aSuperquadrics and Angle Preserving ‘lYaasformations,~ Computer Graphics arLd A pplications, 1 (1).
3. Cook, Robert L., Thomas Porter and Loren Carpenter, “Distributed Ray Tracing,” Computer Graphics, 18(3), July 1984, pp. 137-145.
4. Cyrus, M. and J. Beck, “Generalized two and three dimensional CUpping,” Computers and Graphics, 3(1), 1978, pp. 23-28.
5. Fujlmoto, Akira, Takayuki Tanaka, and Kansei lwata, ~ARTS: Accelerated Ray-Tracing System~, IEEE Computer Craphics and Applications, 6(4), April 1986, 16-26.
6. Giazsner, Andrew S., “Space Subdivision for Fast Ray Tracing,” IEEE Computer Graphics and Applications, 4(10), October, 1984~ pp. 15-22.
7. Kaplan, Michael R., “The Uses of Spatial Coherence in Ray Tracing,” ACM SIGCRAPH ’85 Course Notes 11, July 22-26 1985.
8. Kay, Timothy L., M.S. dissertation in preparation.
9. Kajiya, James W., “New Techniques for Ray Tracing Procedurally Defined Objects’, Computer Graphics, 17(3), July, 1983, pp. 91-102.
10. Rubin, Steve M. and T. Whigted., “A Three- Dimensional Representation for Fast Rendering of Complex Scenes,” Computer Graphics 14(3), July 1980, pp. i10-116.
11. Sedgewick, Robert, Algorithms, Addison- Wesley, Reading, 1983, pp. 127-142.
12. Toth, Daniel L., “On Ray Tracing Parametric Surfaces,~ Computer Graphics i9(3}, July 1985, pp. 171-179.
13. Wetghorst, Hank, Gary Hooper, and Donald P. Greenberg, “Improved Computational Methods for Ray Tracing,~ ACM Transactions on Graphics, 3{1}, January 1984, pp. 52-69.
14. Whirred, Turner, “Aa Improved Illumination Model for Shaded Display,~ Communications of the ACM, 23(6), June 1980, 343-349.