Hidden surface removal for rectangles

ABSTRACT

A simple but important special case of the hidden surface removal problem is one in which the scene consists of n rectangles with sides parallel to the x and y-axes, with viewpoint at z = ∞ (that is, an orthographic projection). This special case has application to overlapping windows. An algorithm with running time &Ogr;(n log n log log n + k log n) is given for static scenes, where k is the number of line segments in the output. Algorithms are given for a dynamic setting (that is, rectangles may be inserted and deleted) that take time &Ogr;(log2 n log log n + k log2 n) per insert or delete, where k is now the number of visible line segments that change (appear or disappear). Algorithms for point location in the visible scene are also given.

REFERENCES

• CG: B. Chazelle and L. J. Guibas, Fractional Cascading: I. A Data Structuring Technique, Algorithmica 1 (1986), 133-162.
• DSST: J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12142]
• E: H. Edelsbrunner, A Note oil Dynamic Range Searching, Bull. of the EATCS 15 (1981), 34-40.
• EM: H. Edelsbrunner and H. A. Maurer, On the intersection of Orthogonal Objects, Inform. Proc. Lett. 13 (1981), 177-181.
• FMN: O. Fries , K. Mehlhorn , St. Näher, Dynamization of geometric data structures, Proceedings of the first annual symposium on Computational geometry, p.168-176, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323256]
• G: M.T. Goodrich, A Polygonal Approach to Hidden- Line Elimination, Proc. ~5th Allerton Conf. on Comm., Control, and Comp., 1987, 849-858.
• GMPR: Leo J. Guibas , Edward M. McCreight , Michael F. Plass , Janet R. Roberts, A new representation for linear lists, Proceedings of the ninth annual ACM symposium on Theory of computing, p.49-60, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803395]
• GO: R H Güting , Th. Ottman, New algorithms for special cases of the hidden line elimination problem, Proceedings on STACS 85 2nd annual symposium on theoretical aspects of computer science, p.161-172, December 1985, Saarbru:9Aicken, Germany
• McC: E. M. McCreight, Priority Search Trees, Xerox PARC Tech. Report CSL-81-5, 1982.
• McK: 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]
• M: Brad A Myers, A complete and efficient implementation of covered windows, Computer, v.19 n.9, p.57-67, Sept. 1986 [doi>10.1109/MC.1986.1663332]
• PS: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• PVY: F. P. Preparata, J. S. Vitter, and M. Yvinec, Computation of the Axial View of a Set of Isothetic Parallelepipeds, Manuscript, 1987.
• ST: Neil Sarnak , Robert E. Tarjan, Planar point location using persistent search trees, Communications of the ACM, v.29 n.7, p.669-679, July 1986 [doi>10.1145/6138.6151]
• VKZ: P. van Erode Boas, B. Kaas, and E. Zijlstra, Design and Implementation of an Emcient Priority Queue, Math. Syst. Theory 10 (1977), 99-127.
• WL: Dan E. Willard , George S. Lueker, Adding range restriction capability to dynamic data structures, Journal of the ACM (JACM), v.32 n.3, p.597-617, July 1985 [doi>10.1145/3828.3839]

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.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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Representations, data structures, and transforms
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection
      I.4.7 Feature Measurement
          Subjects: Projections

General Terms:
Algorithms, Performance, Theory