Worst-case optimal hidden-surface removal

ABSTRACT

An O(n2) hidden-surface removal algorithm is shown. This is an improvement over the previous best worst-case performance of O(n2 log n). It has been established that the hidden-line and hidden-surface problems have an &OHgr;(n2) worst-case lower bound, so the algorithm is optimal. However, the algorithm is not output-size sensitive. Two corollaries to the result are (1) hidden-lines can be removed in optimal O(n2) time, and (2) the portion of a 3-D polyhedron visible from a given interior point is constructible in optimal O(n2) time.

REFERENCES

• 1: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 2: DEVAI, F. Complexity of visibility computations. Dissertation for the Candidate of Sciences degree, Hungarian Academy of Sciences, Budapest, Hungary, 1981. (In Hungarian.)
• 3: F Devai, Quadratic bounds for hidden line elimination, Proceedings of the second annual symposium on Computational geometry, p.269-275, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10544]
• 4: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• 5: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 6: L Guibas , R Seidel, Computing convolutions by reciprocal search, Proceedings of the second annual symposium on Computational geometry, p.90-99, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10525]
• 7: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 8: MULLER, S. E., AND PREPARATA, F. P. Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7, 2 (1978), 217-236.
• 9: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 10: OTTMANN, T., WIDMAYER, P., AND WOOD, D. A worst-case efficient algorithm for hidden-line elimination. Int. J. Comput. Math. 18, 2 (1985), 93-119.
• 11: SCHMITT, A. Time and space bounds for hidden line and hidden surface algorithms. In Eurographics '81, J. L. Encama~~o, Ed. North-Holland, Amsterdam, 1981, pp. 43-56.
• 12: SCHMITT, A. On the time and space complexity of certain exact hidden line algorithms. Rep. 24/81, Fakult/it fdr Informatik, Univ. Karlsruhe, 1981.
• 13: 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

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Design, Performance, Theory, Verification