On constructing binary space partitioning trees

ABSTRACT

Binary Space Partitioning Trees have several applications in computer graphics. We prove that there exist n-polygon problem instances with an O(n2) lower bound on tree size. We also show that a greedy algorithm may result in constructing a tree with O(n2) nodes, while there exist a tree for the same n-polygon instance with only O(n) nodes. Finally, we formulate six different heuristics and test their performance.

REFERENCES

• 1: Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.65-72, July 1983
• 2: William C. Thibault , Bruce F. Naylor, Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.153-162, July 1987
• 3: William Charles Thibault , Bruce F. Naylor, Application of binary space partitioning trees to geometric modeling and ray-tracing, 1987
• 4: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 5: P. Atkin and J. Parker, "High Performance Graphics with the IMS T800", INMOS Technical Note 37, March 1988.
• 6: 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]
• 7: Peter R Atherton, A scan-line hidden surface removal procedure for constructive solid geometry, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.73-82, July 1983
• 8: Norman Chin , Steven Feiner, Near real-time shadow generation using BSP trees, ACM SIGGRAPH Computer Graphics, v.23 n.3, p.99-106, July 1989

INDEX TERMS

Primary 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

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.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

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

General Terms:
Algorithms, Design