Ray tracing complex scenes

ABSTRACT

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.

REFERENCES

• Apostol 69: Apostol, Tom M., Calculus, Volume II, Wiley, New York, 1969, pp. 314-318.
• Barr 81: Barr, Alan H., aSuperquadrics and Angle Preserving 'lYaasformations,~ Computer Graphics arLd A pplications, 1 (1).
• Cook 84: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.137-145, July 1984
• Cyrus 78: Cyrus, M. and J. Beck, "Generalized two and three dimensional CUpping," Computers and Graphics, 3(1), 1978, pp. 23-28.
• Fujimoto 86: Akira Fujimoto , Takayuki Tanaka , Kansei Iwata, ARTSccelerated ray-tracing system, IEEE Computer Graphics and Applications, v.6 n.4, p.16-26, April 1986 [doi>10.1109/MCG.1986.276715]
• Glassner 84: Giazsner, Andrew S., "Space Subdivision for Fast Ray Tracing," IEEE Computer Graphics and Applications, 4(10), October, 1984~ pp. 15-22.
• Kaplan 85: Kaplan, Michael R., "The Uses of Spatial Coherence in Ray Tracing," ACM SIGCRAPH '85 Course Notes 11, July 22-26 1985.
• Kay 86: Kay, Timothy L., M.S. dissertation in preparation.
• Kajiya 83: James T. Kajiya, New techniques for ray tracing procedurally defined objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.91-102, July 1983
• Rubin 80: Steven M. Rubin , Turner Whitted, A 3-dimensional representation for fast rendering of complex scenes, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.110-116, July 1980
• Sedgewick 83: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• Toth 85: Daniel L. Toth, On ray tracing parametric surfaces, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.171-179, Jul. 1985
• Weghorst 84: Hank Weghorst , Gary Hooper , Donald P. Greenberg, Improved Computational Methods for Ray Tracing, ACM Transactions on Graphics (TOG), v.3 n.1, p.52-69, Jan. 1984 [doi>10.1145/357332.357335]
• Whitted 80: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms