“Beam tracing polygonal objects” by Heckbert and Hanrahan

Ray tracing has produced some of the most realistic computer generated pictures to date. They contain surface texturing, local shading, shadows, reflections and refractions. The major disadvantage of ray tracing results from its point-sampling approach. Because calculation proceeds ab initio at each pixel it is very CPU intensive and may contain noticeable aliasing artifacts. It is difficult to take advantage of spatial coherence because the shapes of reflections and refractions from curved surfaces are so complex. In this paper we describe an algorithm that utilizes the spatial coherence of polygonal environments by combining features of both image and object space hidden surface algorithms. Instead of tracing infinitesimally thin rays of light, we sweep areas through a scene to form “beams.” This technique works particularly well for polygonal models since for this case the reflections are linear transformations, and refractions are often approximately so. The recursive beam tracer begins by sweeping the projection plane through the scene. Beam-surface intersections are computed using two-dimensional polygonal set operations and an occlusion algorithm similar to the Weiler-Atherton hidden surface algorithm. For each beam-polygon intersection the beam is fragmented and new beams created for the reflected and transmitted swaths of light. These sub-beams are redirected with a 4×4 matrix transformation and recursively traced. This beam tree is an object space representation of the entire picture. Since the priority of polygons is pre-determined, the final picture with reflections, refractions, shadows, and hidden surface removal is easily drawn. The coherence information enables very fast scan conversion and high resolution output. Image space edge and texture antialiasing methods can be applied.

1. Atherton, Peter K., Kevin Weiler, and Donald Greenberg, “Polygon Shadow Generation.” Computer Graphics (SIGGRAPH ’78 Proceedings), vol. 12, no. 3, Aug. 1978, pp. 275-281.
2. Catmull, Edwin, “A Hidden-Surface Algorithm with Anti-Aliasing.” Computer Graphics (SIGGRAPH ’78 Proceedings), vol. 12, no. 3, Aug. 1978, pp. 6-11.
3. Clark, James, “Hierarchical Geometric Models for Visible Surface Algorithms.” C. A. C. M. vol. 19, no. 10, 1976, pp. 547-554.
4. Crow, Franklin C., “Shaded Computer Graphics in the Entertainment industry.” Computer, vol. 11, no. 3, March 1978, p. 11.
5. Dadoun, Norm, David G. Kirkpatrick, and John P. Walsh, “Hierarchical Approaches to Hidden Surface Intersection Testing.” Proceedings of Graphics Interface ’82, May 1982, pp. 49-56.
6. Eastman, C. M., and C. I. Yessios, “An Efficient Algorithm for Finding the Union, Intersection and Differences of Spatial Domains.” Technical Report 31, Institute of Physical Planning, Carnegie-Mellon University, Sept. 1972.
7. Feynman, Richard P., Robert B. Leighton, and Matthew Sands, The Feynman Lectures on Physics. Addison- Wesley, Reading, Mass., 1963, vol. I, pp. 27-3, 27-4.
8. Fuchs, Henry, Zvi M. Kedem, and Bruce F. Naylor, “On Visible Surface Generation by A Priori Tree Structures.” Computer Graphics (SIGGRAPH ’80 Proceedings), vol. 14, no. 3, July 1980, pp. 124-133.
9. Hall, Roy A., and Donald P. Greenberg, “A Testbed for Realistic Image Synthesis.” IEEE Computer Graphics and Applications, vol. 3, no. 8, Nov. 1983, pp. 10-20.
10. Hanrahan, Pat, and Paul S. Heckbert, “Introduction to Beam Tracing.” Proc. Intl. Conf. on Engineering and Computer Graphics, Beijing, China, Aug. 1984.
11. Heckbert, Paul, PMAT and POLY User’s Manual. New York Inst. of Tech. internal document, Feb. 1983.
12. Jones, C. B., “A New Approach to the ‘Hidden Line’ Problem.” The Computer Journal, vol. 14, no. 3, Aug. 1971, pp. 232-237.
13. Kawaguchi, Yoichiro, “Growth: Mysterious Galaxy.” SIGGRAPH ’83 Film & Video Shows,p. 5.
14. Kay, Douglas S., and Donald Greenberg, “Transparency for Computer Synthesized Images.” Computer Graphics (SIGGRAPH ’79 Proceedings), vol. 13, no. 2, Aug. 1979, pp. 158-164.
15. Longhurst, R. S., Geometrical and Physical Optics. Longman, London, 1967.
16. Max, Nelson, “Computer Graphics Distortion for IMAX and OMNIMAX Projection.” Nicograph ’83 Proceedings, Dec. 1983, pp. 137-159.
17. Newell, M. E., R. G. Newell, and T. L. Sancha, “A New Approach to the Shaded Picture Problem.” Proc. ACM Nat. Conf., 1972, p. 443.
18. Newman, William M., and Robert F. Sproull, Principles of Interactive Computer Graphics, 2nd ed. McGraw-Hill, New York, 1979.
19. Nishimura, Hitoshi, Hiroshi Ohno, Toru Kawata, Isao Shirakawa, and Koichi Omura, “Links-1: A Parallel Pipelined Multimicrocomputer System for Image Creation.” IEEE 1983 Conf. Proc. of the 10th Annual Intl. Symp. on Computer Architecture.
20. Roth, Scott D., “Ray Casting for Modeling Solids.” Computer Graphics and Image Processing, vol. 18, no. 2, Feb. 1982, pp. 109-144.
21. Rubin, S. W., and Turner Whitted, “A 3-dimensional Representation for Fast Rendering of Complex Scenes.” Computer Graphics (SIGGRAPH ’80 Proceedings), vol. 14, no. 3, July 1980, pp. 110-116.
22. Sutherland, Ivan E., Robert F. Sproull,. and Robert A. Schumacker, “A Characterization of Ten Hidden-Surface Algorithms.” Computing Surveys, vol. 6, no. 1, March 1974, p. 1.
23. Walker, Jearl, “The Amateur Scientist: What is a fish’s view of a fisherman and the fly he has cast on the water?” Scientific American, vol. 250, no. 3, March 1984, pp. 138-143.
24. Walsh, John P., and Norm Dadoun, “What Are We Waiting for? The Development of Godot, II.” presented at the 103rd meeting of the Acoustical Society of America, Chicago, April 1982.
25. Weiler, Kevin, and Peter Atherton, “Hidden Surface Removal Using Polygon Area Sorting.” Computer Graphics (SIGGRAPH ’77 Proceedings), vol. 11, no. 2, Summer 1977, pp. 214-222.
26. Whitted, Turner, “An Improved Illumination Model for Shaded Display.” C. A. C. M. vol. 23, no. 6, June 1980, pp. 343-349.