Generalized hidden surface removal

ABSTRACT

In this paper we study the following generalization of the classical hidden surface removal problem: given a set S of objects, a view point and a point light source, compute which parts of the objects in S are visible, subdivided into parts that are lit and parts that are not lit. We prove tight bounds on the maximum combinatorial complexity of such views and give efficient output-sensitve algorithms to compute the views for three cases: (i) S consists of non-intersecting triangles, (ii) S consists of horizontal axis-parallel rectangles, (iii) S is the set of faces of a polyhedral terrain.

REFERENCES

• 1: Pankaj K. Agarwal , Jiří Matoušek, Ray shooting and parametric search, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.517-526, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129763]
• 2: 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]
• 3: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991
• 4: B. Chazelle , H. Edelsbrunner , L. Guibas , M. Sharir, Lines in space-combinators, algorithms and applications, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.382-393, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73044]
• 5: B. Chazelle , L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete & Computational Geometry, v.4 n.6, p.551-581, Sep. 1989
• 6: M. de Berg , D. Halperin , M. Overmars , J. Snoeyink , M. van Kreveld, Efficient ray shooting and hidden surface removal, Proceedings of the seventh annual symposium on Computational geometry, p.21-30, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109651]
• 7: Mark de Berg , Mark H. Overmars, Hidden surface removal for c-oriented polyhedra, Computational Geometry: Theory and Applications, v.1 n.5, p.247-268, May 1992 [doi>10.1016/0925-7721(92)90007-F ]
• 8: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 9: 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
• 10: 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]
• 11: L.J. Guibas, J. Hershberger, D. Leven, M. Sharir and R. E. Tarjan, Linear-Time Algorithms for Visibility and Shortest Path Problems Inside Triangulated Simple Polygons, Algorithmica 2 (1987), pp. 209-233.
• 12: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• 13: Matthew J. Katz , Mark H. Overmars , Micha Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, v.2 n.4, p.223-234, Dec. 1992 [doi>10.1016/0925-7721(92)90024-M ]
• 14: H. Mairson and J. Stolfi, Reporting and counting intersections between two sets of line segments, Theoretical Foundations of Computer Science and CAD, R.A. Earnshaw (Ed.), NATO ASI Series, Vol. F-40, Springer Verlag, 1988, pp.307-326.
• 15: 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]
• 16: M.H. Overmars, personal communication.
• 17: Mark H. Overmars , Chee-Keng Yap, New upper bounds in Klee's measure problem, SIAM Journal on Computing, v.20 n.6, p.1034-1045, Dec. 1991 [doi>10.1137/0220065]
• 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]

INDEX TERMS

Primary 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

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Viewing algorithms; Display algorithms
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

General Terms:
Algorithms, Theory, Verification