The geometry of beam tracing

ABSTRACT

A solution to the hidden surface elimination problem called Beam Tracing is described. Beam tracing is related to ray tracing but uses spatial coherence within the scene, and area coherence within the image to batch computations. Beam tracing is an object space solution to the hidden surface problem. Beam tracing is formulated in terms of its principal subprocesses: intersection, sorting, and clipping. A Hierarchical Scene Representation is proposed. This incorporates the space decomposition idea of the BSP tree [Fuchs, Kedem and Naylor, 80] along with the convex polytope intersection detection technique of [Dobkin and Kirkpatrick, 83] to interleave and efficiently solve the intersection and sorting subproblems of beam tracing.

REFERENCES

• 1: John Amanatides, Ray tracing with cones, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.129-135, July 1984
• 2: Bernard Chazelle , David P. Dobkin, Detection is easier than computation (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.146-153, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804662]
• 3: James H. Clark, Hierarchical geometric models for visible surface algorithms, Communications of the ACM, v.19 n.10, p.547-554, Oct. 1976 [doi>10.1145/360349.360354]
• 4: [Dadoun, 82] Dadoun, N. "Hierarchical Approaches to The Hidden Surface Problem", M.Sc. Thesis, University of British Columbia, Vancouver, Canada, December, 1982.
• 5: [Dadoun, Kirkpatrick and Walsh, 82] Dadoun, N., Kirkpatrick, D. G., and Walsh, J. P. "Hierarchical Approaches to Hidden Surface Intersection Testing", Proceedings Graphics Interface 82, NCGA, Toronto, May, 1982.
• 6: [Dadoun, Kirkpatrick and Walsh, 85] Dadoun, N., Kirkpatrick, D. G., and Walsh, J.P. "Hierarchical Methods for Beam Tracing", In Preparation, 1985.
• 7: [Dobkin and Kirkpatrick, 83] Dobkin, D. P. and Kirkpatrick, D. G. "Fast Detection of Polyhedral Intersections", Theoretical Computer Science, 17, 1983, pp. 241-253.
• 8: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.124-133, July 1980
• 9: Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.65-72, July 1983
• 10: [Glassner, 84] Glassner, Andrew S. "Space Subdivision for Fast Ray Tracing", CG&A, Vol. 4, No. 10, October, 1984, pp. 15-22.
• 11: Paul S. Heckbert , Pat Hanrahan, Beam tracing polygonal objects, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.119-127, July 1984
• 12: [Kirkpatrick, 83] Kirkpatrick, D. G. "Optimal Search in Planar Subdivisions", SIAM Journal on Computing, 12(1), 1983, pp. 28-35.
• 13: F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
• 14: [Roth, 82] Roth, S. D. "Ray Casting for Modelling Solids", CGIP, Vol. 18, February, 1982, pp. 109-144.
• 15: 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
• 16: Ivan E. Sutherland , Gary W. Hodgman, Reentrant polygon clipping, Communications of the ACM, v.17 n.1, p.32-42, Jan. 1974 [doi>10.1145/360767.360802]
• 17: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 18: [Walsh, 79] Walsh, J. "The Simulation of Directional Sound Sources in Rooms by Means of a Digital Computer" M. Mus. Thesis, University of Western Ontario, London, Canada, Fall, 1979.
• 19: [Walsh and Dadoun, 81] Walsh, J. and Dadoun, N. "The Design and Development of Godot: A System for Room Acoustics Modelling", presented at 101st meeting of the Acoustical Society of America, Ottawa, May, 1981.
• 20: [Walsh and Dadoun, 82] Walsh, J. and Dadoun, N. "What Are We Waiting for? Development of Godot II", presented at 103rd meeting of the Acoustical Society of America, Chicago, April, 1982.
• 21: Kevin Weiler, Polygon comparison using a graph representation, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.10-18, July 1980
• 22: Kevin Weiler , Peter Atherton, Hidden surface removal using polygon area sorting, ACM SIGGRAPH Computer Graphics, v.11 n.2, p.214-222, Summer 1977
• 23: 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

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Hidden line/surface removal

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Design, Performance, Theory