Parallel object-space hidden surface removal

ABSTRACT

A parallel object-space hidden surface removal algorithm for polyhedral scenes is presented. The uniform grid technique is used to achieve parallelism for the hidden line removal. A conflict-detection and back-off strategy is then used to obtain parallelism for the visible region reconstruction from the visible segments. The algorithm has been implemented on a Sequent Balance 21000 shared-memory parallel computer. An average speedup of 10 has been obtained using 15 processors.

REFERENCES

• 1: 1. Ajjanagadde V. G. and Patnaik L. M., "Design and Performance Evaluation of a Systolic Architecture for Hidden Surface Removal", Computers & Graphics, 12, 1 (1988), 71-74.
• 2: Kurt Akeley , Tom Jermoluk, High-performance polygon rendering, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.239-246, Aug. 1988
• 3: V. Akman , W. R. Franklin , M. Kankanhalli , C. Narayanaswmi, Geometric computing and uniform grid technique, Computer-Aided Design, v.21 n.7, p.410-420, Sep. 1989 [doi>10.1016/0010-4485(89)90125-5]
• 4: Edwin Catmull, An analytic visible surface algorithm for independent pixel processing, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.109-115, July 1984
• 5: 5. Chandrasekhar N. and Franklin W. R., "An Efficient Parallel Algorithm for Determining Boolean Combinations of Complex Polyhedra" (in preparation).
• 6: 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
• 7: Eugene Fiume , Alain Fournier , Larry Rudolph, A parallel scan conversion algorithm with anti-aliasing for a general-purpose ultracomputer, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.141-150, July 1983
• 8: Wm Randolph Franklin, A linear time exact hidden surface algorithm, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.117-123, July 1980
• 9: W. Randolph Franklin , Varol Akman, Reconstructing visible regions from visible segments, BIT, v.26 n.4, p.430-441, Jan. 1986 [doi>10.1007/BF01935050]
• 10: Henry Fuchs, Distributing a visible surface algorithm over multiple processors, Proceedings of the 1977 annual conference, p.449-451, January 1977 [doi>10.1145/800179.810237]
• 11: Henry Fuchs , John Poulton , John Eyles , Trey Greer , Jack Goldfeather , David Ellsworth , Steve Molnar , Greg Turk , Brice Tebbs , Laura Israel, Pixel-planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.79-88, July 1989
• 12: 12. Haines E., "A Proposal for Standard Graphics Environments", IEEE Computer Graphics & Applications, 7, 11 (November 1987), 3-5.
• 13: 13. Hornung C., "A Method for Solving the Visibility Problem", IEEE Computer Graphics & Applications, 4, 7 (July 1984), 26-33.
• 14: 14. Hu M. and Foley J. D., "Parallel Processing Approaches to Hidden Surface Removal in Image Space", Computers & Graphics, 9, 3 (1985), 303-317.
• 15: Kenneth I. Joy , Charles W. Grant , Nelson L. Max , Lansing Hatfield, Tutorial: computer graphics; image synthesis, Computer Science Press, Inc., New York, NY, 1988
• 16: Michael Kaplan , Donald P. Greenberg, Parallel processing techniques for hidden surface removal, ACM SIGGRAPH Computer Graphics, v.13 n.2, p.300-307, August 1979
• 17: 17. Mulmuley K., "On Obstructions In Relation To A Fixed Viewpoint", Proc. 30th Annual Symposium on Foundations of Computer Science (Oct. 30 - Nov. 1, 1989), pp. 592-597.
• 18: 18. Overmars M. and Sharir M., "Output-Sensitive Hidden Surface Removal", Proc. 30th Annual Symposium on Foundations of Computer Science (Oct. 30 - Nov. 1, 1989), pp. 598-603.
• 19: Frederic I. Parke, Simulation and expected performance analysis of multiple processor Z-buffer systems, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.48-56, July 1980
• 20: Michael Potmesil , Eric M. Hoffert, The pixel machine: a parallel image computer, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.69-78, July 1989
• 21: 21. Rankin J. R., "A Geometric Hidden Line Processing Algorithm", Computers & Graphics, 11, 1 (1987), 11- 19.
• 22: J. H. Reif , S. Sen, An efficient output-sensitive hidden surface removal algorithm and its parallelization, Proceedings of the fourth annual symposium on Computational geometry, p.193-200, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73413]
• 23: 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]
• 24: T. Theoharis, Algorithms for parallel polygon rendering, Springer-Verlag New York, Inc., New York, NY, 1989
• 25: Richard Weinberg, Parallel processing image synthesis and anti-aliasing, ACM SIGGRAPH Computer Graphics, v.15 n.3, p.55-62, August 1981

INDEX TERMS

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

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