Binary partitions with applications to hidden surface removal and solid modelling

ABSTRACT

We consider schemes for recursively dividing a set of geometric objects by hyperplanes until all objects are separated. Such a binary partition is naturally considered as a binary tree where each internal node corresponds to a division and the leaves correspond to the resulting fragments of objects. The goal is to choose the hyperplanes properly so that the size of the binary partition, i.e., the number of resulting fragments of the objects, is minimized. We construct binary partitions of size &Ogr;(n log n) for n edges in the plane, and of size &Ogr;(n) if the edges are orthogonal. In three dimensions, we obtain binary partitions of size &Ogr;(n2) for n planar facets, and prove a lower bound of &OHgr;(n3/2). Two applications of efficient binary partitions are given. The first is an &Ogr;(n2)-sized data structure for implementing a hidden-surface removal scheme of Fuchs, Kedem and Naylor [5]. The second application is in solid modelling: given a polyhedron described by its n faces, we show how to generate an &Ogr;(n2)-sized CSG (constructive-solid-geometry) formula whose literals correspond to half-spaces supporting the faces of the polyhedron (see Peterson [9] and Dobkin et al. [3]). The best previous results for both of these problems were &Ogr;(n3).

REFERENCES

• 1: Bernard Chazelle, New techniques for computing order statistics in Euclidean space (extended abstract), Proceedings of the first annual symposium on Computational geometry, p.125-134, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323251]
• 2: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 3: David Dobkin , Leonidas Guibas , John Hershberger , Jack Snoeyink, An efficient algorithm for finding the CSG representation of a simple polygon, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.31-40, Aug. 1988
• 4: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 5: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 6: E. Gilbert and E. hloore, Variable-length binary encoding, Bell System Tech. J.,38, 1959, 933-968.
• 7: L. Guibas and F. Yao, On translating a set of rectangles, Advances in Computing Research, Vol.1, JAI Press, 1983, Gl-77.
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: D. Peterson, Halfspace representations of extrusions, solids of revolution, and pyramids, SANDIA Report SAND84-0572, Sandia National Laboratories, 1984.
• 10: W. Thurston, private communication.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Theory