An efficient output-sensitive hidden surface removal algorithm and its parallelization

ABSTRACT

In this paper we present an algorithm for hidden surface removal for a class of polyhedral surfaces which have a property that they can be ordered relatively quickly like the terrain maps. A distinguishing feature of this algorithm is that its running time is sensitive to the actual size of the visible image rather than the total number of intersections in the image plane which can be much larger than the visible image. The time complexity of this algorithm is &Ogr;((k +n)lognloglogn) where n and k are respectively the input and the output sizes. Thus, in a significant number of situations this will be faster than the worst case optimal algorithms which have running time &OHgr;(n2) irrespective of the output size (where as the output size k is &Ogr;(n2) only in the worst case). We also present a parallel algorithm based on a similar approach which runs in time &Ogr;(log4(n+k)) using &Ogr;((n + k)/log(n+k)) processors in a CREW PRAM model. All our bounds are obtained using ammortized analysis.

REFERENCES

• 1: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• 2: Mehlhorn K. and Nailer S., "Dynamic Fractional cascading,".
• 3: Cole R. and Sharir M., Visibility problems for polyhedral terrains," Tech. Rept. No. 92, Courant Institute of Math. Sc., Dec, 1986.
• 4: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 5: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 6: Chazelle B., "A Theorem on Polygon Cutting with Applications," Proc. of IEEE FOCS 1982, pp. 339-349.
• 7: McKenna M., "Worst-case optimal hidden-surface removal," Tech. Rept JHU/EECS-86/05.
• 8: Wright T.J., "A Two-space solution to the hidden line problem for plotting functions of two variables," IEEE Trans. on Comput., vol. e-32, no. 1, pp. 28-33.
• 9: Lee D.T. and Preparata F.P., "Location of a point in a planar subdivision and its applications, SIAM Journal of Comput., 6(3), 1977, pp. 594-606.
• 10: F. P. Preparata, An optimal real-time algorithm for planar convex hulls, Communications of the ACM, v.22 n.7, p.402-405, July 1979 [doi>10.1145/359131.359132]
• 11: B. Chazelle , D. P. Dobkin, Intersection of convex objects in two and three dimensions, Journal of the ACM (JACM), v.34 n.1, p.1-27, Jan. 1987 [doi>10.1145/7531.24036]
• 12: Mehlhorn K., "Arbitrary weight changes in Dynamic trees," Theoretical Informatics, vol 15, 1981, pp 183-211.
• 13: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 14: Schmitt A., "Time and Space bounds for hidden line and hidden surface elimination algorithms," EUROGRAPHICS '81, pp 43- 5{}.
• 15: Goodrich M.T., "A polygonal approach to hidden-line elimination," Tech Rept 87-18, Dept of Computer Science, Johns Hopkins University.
• 16: Atallah M.J., Cole R. & Goodrich M.T., "Cascading Divideand-Conquer: A technique for Designing Parallel Algorithms," Proc. of the 28th Annual Symp. on FOCS, 1987, pp. 151- 160.
• 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]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Machine-independent complexity**
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations; Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Projections

General Terms:
Algorithms, Design, Performance, Theory