Ray tracing on a connection machine

ABSTRACT

A new ray-tracing algorithm designed specifically for massively parallel hypercube connected processors is introduced. World space is subdivided according to a fixed size 3-D orthogonal grid. Rays are traced using ray-points which move along the rays, referencing the voxels intersected. One processor is assigned per ray, as well as one processor per object fragment. A pointerless data structure called an induced octree is used. This structure exists only as an ordering of the data in processor-address space, yet with it, all processors can determine the jump-distance to the nearest non-empty voxel in parallel to within a power of two. Ray-points move by large jumps whenever possible, and ray-object intersection proceeds in log time in the average ray length. Sorting via the network is the parallel analogue to octree-traversal. A code-scheduling mechanism is introduced which improves processor usage for SIMD architectures. Preliminary results are presented for an implementation using a CM-1 CPU equipped with 16k processors.

REFERENCES

• 1: W. Daniel Hillis, The connection machine, MIT Press, Cambridge, MA, 1986
• 2: Hall, R.A., and Greenberg,D.P. "A Testbed For Realistic Image Synthesis", IEEE Computer Graphics and Applications, Vol. 3(8), November 1983, pp.10-20.
• 3: 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]
• 4: James T. Kajiya, New techniques for ray tracing procedurally defined objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.91-102, July 1983
• 5: Robert L. Cook , Thomas Porter , Loren Carpenter, Distributed ray tracing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.137-145, July 1984
• 6: James T. Kajiya, The rendering equation, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.143-150, Aug. 1986
• 7: Glassner, A.S., "Space Subdivision for Fast Ray Tracing", IEEE Computer Graphics and Applications, Vol 4(10), October 1984, pp. 15-22.
• 8: James Arvo , David Kirk, Fast ray tracing by ray classification, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.55-64, July 1987
• 9: Thomas W. Sederberg , David C. Anderson, Ray tracing of Steiner patches, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.159-164, July 1984
• 10: 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]
• 11: Mark Dippé , John Swensen, An adaptive subdivision algorithm and parallel architecture for realistic image synthesis, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.149-158, July 1984
• 12: Gottlieb, A., and Schwalrz, j.T., "Networks and Algorithms for Very-Large-Scale Computation", Cc.rnputer, January 1982, pp. 27-36.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Single-instruction-stream, multiple-data-stream processors (SIMD)
          Nouns: CM-1
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers
          Nouns: CRAY-1

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms

General Terms:
Algorithms, Design, Theory