Merging visibility maps

ABSTRACT

Let V be a set of objects in space for which we want to determine the portions visible from a particular point of view &ugr;. Assume V is subdivided in subsets V1,…, Vz and the visibility maps &Mgr;1, … &Mgr;z of these subsets from point ugr; are known. We show that the visibility map &Mgr; for V can be computed by merging &Mgr;1, … &Mgr;z in time &Ogr;((n + &kgr;)z log2 n) where n is the total size (number of edges, vertices and faces) of the visibility maps &Mgr;1,…, &Mgr;z and &kgr; is the size of &Mgr;. This result has important applications e.g. in animation where objects move with respect to a fixed environment. It also leads to efficient algorithms for special cases of the hidden-surface removal problem. For example, we obtain a method for hidden surface removal in a set of unit spheres, viewed from infinity, that runs in time &Ogr;((n + &kgr;) log2 n).

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: B. Chazelle and H. Edelsbrunner, An optimal algorithm for intersecting line segments in the plane, Proc. 29th IEEE Syrup. on Foundations of Computer Science, 1988, pp. 590-6(0.
• 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: Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
• 5: M.T. Goodrich, A polygonal approach to hidden fine elimination, Proc. 25th AUerton Conf. on Communication, Control and Computing, 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: 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]
• 8: H. Mairson and J. Stolti, Reporting and counting intersections between two sets of line segments, Theoretical Foundations of Computer Graphics and CAD, R.A. Earnshaw, Ed., NATO ASI Series, Vol F-40, Springer Verlag, 1988, pp. 307-326.
• 9: 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]
• 10: K. Mulmuley, An efficient algorithm for hidden surface removal, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.379-388, July 1989
• 11: Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
• 12: M.H. Overmars and M. Sharir, Output-sensitive hidden surface removal, Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, pp. 598-603.
• 13: M. S. Paterson , F. F. Yao, Binary partitions with applications to hidden surface removal and solid modelling, Proceedings of the fifth annual symposium on Computational geometry, p.23-32, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73836]
• 14: 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]
• 15: Micha Sharir , Mark H. Overmars, A simple output-sensitive algorithm for hidden surface removal, ACM Transactions on Graphics (TOG), v.11 n.1, p.1-11, Jan. 1992 [doi>10.1145/102377.112141]
• 16: F.P. Preparata, J.S. Vitter and M. Yvinec, Computation of the axial view of a set of isothetic parallelepipeds, Techn. Rep. LIENS-88-1, Lab. d'Informatique de L'Ecole Normal Sup~eure, 1988.
• 17: A. Schmitt, Time and space bounds for hidden line and hidden surface algorithms, Eurographics "81, pp. 43-56.
• 18: 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:
  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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

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

General Terms:
Algorithms