A simple output-sensitive algorithm for hidden surface removal

ABSTRACT

We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map, the method runs in time Onklog n . The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time On^3/2logn+k .

REFERENCES

• 1: Marshall Bern, Hidden surface removal for rectangles, Journal of Computer and System Sciences, v.40 n.1, p.49-69, February 1990 [doi>10.1016/0022-0000(90)90018-G]
• 2: C~^ZELLE, B. A theorem on polygon cutting with applications. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science (Chicago, Ill., Oct. 1982), pp. 339-349.
• 3: CHAZELLE, B., AND EOELSBRUNNER, H. An optimal algorithm for intersecting line segments in the plane. In Proceedings of the 29th 1EEE Symposium on Foundations of Computer Science (White Plains, N.Y., Oct. 1988), pp. 590-600.
• 4: 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]
• 5: C~)OORICH, M. T. A polygonal approach to hidden line elimination. In Proceedings of the 25th Allerton Conference on Communication, Control and Computing (Monticello, Ill., Sept. 1987), pp. 849-858.
• 6: Michael T. Goodrich , Mikhail J. Atallah , Mark H. Overmars, An input-size/output-size trade-off in the time-complexity of rectilinear hidden surface removal, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.689-702, July 1990, Warwick University, England
• 7: 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]
• 8: Ralf Hartmut Güting , Thomas Ottmann, New algorithms for special cases of the hidden line elimination problem, Computer Vision, Graphics, and Image Processing, v.40 n.2, p.188-204, November 1, 1987 [doi>10.1016/S0734-189X(87)80114-7]
• 9: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 10: MnmsoN, H., AND STOLFI, J. Reporting and counting intersections between two sets of line segments. In Theoretical Foundations of Computer Graphics and CAD, R. A. Ear^shaw, Ed, NATO ASI Series, Vol F-40, Springer Verlag, 1988, pp. 307-326.
• 11: Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
• 12: Michael McKenna, Worst-case optimal hidden-surface removal, ACM Transactions on Graphics (TOG), v.6 n.1, p.19-28, Jan. 1987 [doi>10.1145/27625.27627]
• 13: K. Mulmuley, An efficient algorithm for hidden surface removal, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.379-388, July 1989
• 14: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 15: OVERMAI~S, M. H., ^NO S~^gm, M. Output-sensitive hidden surface removal. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Research Triangle Park, N.C., Oct. 1989), pp. 598-603.
• 16: OvsRM^m% M. H., ^ND SHAam, M. An improved technique for output-sensitive hidden surface removal. Tech. Rept. RUU-CS-89-32, Dept. of Computer Science, Utrecht Univ., 1989.
• 17: Michael S. Paterson , F. Frances Yao, Efficient binary space partitions for hidden-surface removal and solid modeling, Discrete & Computational Geometry, v.5 n.5, p.485-503, 1990 [doi>10.1007/BF02187806]
• 18: 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]
• 19: Haijo Schipper , Mark H. Overmars, Dynamic partition trees, BIT, v.31 n.3, p.421-436, Summer 1991 [doi>10.1007/BF01933260]
• 20: Franco P. Preparata , Jeffrey S. Vitter , Mariette Yvinec, Computation of the axial view of a set of isothetic parallelepipeds, ACM Transactions on Graphics (TOG), v.9 n.3, p.278-300, July 1990 [doi>10.1145/78964.78967]
• 21: S(mMn*r, A. Time and space bounds for hidden line and hidden surface algorithms. In Eurographics '81, pp. 43-56.
• 22: 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.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
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Theory

Keywords:
hidden line elimination, hidden surface removal, object-space algorithm