Bintrees, CSG trees, and time

ABSTRACT

A discussion is presented of the relationship between two solid representation schemes: constructive solid geometry (CSG trees) and recursive spatial subdivision exemplified by the bintree, a generalization of the quadtree and octree. Detailed algorithms are developed and analyzed for evaluating CSG trees by bintree conversion, i.e., by determining explicitly which parts of space are solid and which empty. These techniques enable the addition of the time dimension and motion to the approximate analysis of CSG trees in a simple manner to solve problems such as dynamic interference detection. For "well-behaved" CSG trees, the execution time of the conversion algorithm is directly related to the spatial complexity of the object represented by the CSG tree (i.e., asymptotically it is proportional to the number of bintree nodes as the resolution increases). The set of well-behaved CSG trees includes all trees that define multidimensional polyhedra in a manner that does not give rise to tangential intersections at CSG tree nodes.

REFERENCES

• 1: J. Alander, Interval arithmetic methods in the processing of curves and sculptured surfaces, Proceedings of the Sixth Internalional Symposium on CAD~CAM, Zagreb, Yugoslavia (1984).
• 2: 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
• 3: John W. Boyse, Interference detection among solids and surfaces, Communications of the ACM, v.22 n.1, p.3-9, Jan. 1979 [doi>10.1145/359046.359048]
• 4: Gregory Michael Hunter, Efficient computation and data structures for graphics., 1978
• 5: C. Jackins and S.L. Tanimoto, Quad-trees, oct-trees, and k-trees- a generalized approach to recursive decomposition of Euclidean space, IEEE Transactions on Pattern Analysis and Machine Intelligence 5, 5(September 1983), 533-539.
• 6: E. Kawaguchi and T. Endo, On a method of binary picture representation and its application to data compression, IEEE Transactions on Pattern Analysis and Machine Intelligence 2, 1(January 1980), 27-35.
• 7: P. Koistinen, M. Tamminen, and H. Samet, Viewing solid models by bin tree conversion, to appear in Proceedings of the EUROGRAPHICS '85 Conference, Nice, September 1985.
• 8: Yong Tsui Lee , Aristides A. G. Requicha, Algorithms for computing the volume and other integral properties of solids. I. known methods and open issues, Communications of the ACM, v.25 n.9, p.635-641, Sept 1982 [doi>10.1145/358628.358643]
• 9: D. Meagher, Octree encoding: a new technique for the representation, manipulation and display of arbitrary 3-D objects by computer, Report IPL-TR-80-111, Rensselaer Polytechnic Institute, Troy, New York, 1980.
• 10: D. Meagher, The Solids engine: a processor for interactive solid modeling, Proceedings of the NICOGRAPH '84 Conference, Tokyo, November 1984.
• 11: S.P. Mudur and P.A. Koparkar, Interval methods for processing geometric objects, IEEE Computer Graphics and Applications ~, 2(February 1984), 7-17.
• 12: N. Okino, Y. Kakazu, and H. Kubo, TIPS-I: Technical information processing system for computer aided design, drawing and manufacturing, in Computer Languages for Numerical Control,, J. Hatvany, Ed., North Holland, Amsterdam, 1973, 141-150.
• 13: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 14: A.A.G. Requicha and H.B. Voelcker, Solid modeling: current status and research directions, IEEE Computer Graphics and Applications 3, 7(1983), 25-37.
• 15: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• 16: H. Samet and M. Tamminen, Approximating CSG trees of moving objects, Computer Science TR-1472, University of Maryland, College Park, MD, January 1985.
• 17: Markku Tamminen , Hanan Samet, Efficient octree conversion by connectivity labeling, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.43-51, January 1984
• 18: M. Tamminen, P. Koistinen, J. Hamalainen, O. Karonen, P. Korhonen, R. Raunio, and P. Rekola, Biatree: a dimension independent image processing system, Report- HTKK-TKO-C9, Helsinki University of Technology, 198qi.
• 19: Robert B. Tilove, A null-object detection algorithm for constructive solid geometry, Communications of the ACM, v.27 n.7, p.684-694, July 1984 [doi>10.1145/358105.358195]
• 20: A.F. Wallis and J.R. Woodwork, Creating large solid models for NC toolpath verification, Proceedings of CAD 84, 1984.
• 21: J.R. Woodwork and K.M. Quinlan, Reducing the effect of complexity on volume model evaluation, Computer-aided Design IJ, 2(1982), 89-95.
• 22: Mann-May Yau , Sargur N. Srihari, A hierarchical data structure for multidimensional digital images, Communications of the ACM, v.26 n.7, p.504-515, July 1983 [doi>10.1145/358150.358158]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms; Viewing algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Motion

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
bintrees, constructive solid geometry (CSG), conversion, hierarchical data structures, image processing, interference detection, motion, octrees, quadtrees, solid modeling, time