“Bintrees, CSG trees, and time” by Tamminen and Samet

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.

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. P.R. At, herton, A scan-line hidden surface removal procedure for constructive solid geometry, Computer Graph- {cs 17, 3(1983), 73-82.
3. J.W. Boyse, Interference detection among solids and surfaces, Communications of the ACM 22, l(January 1979), 3-9.
4. G.M. Hunter, Efficient computation and data structures for graphics, Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University, Princeton, N J, 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. Y.T. Lee and A.A.G. Requicha, Algorithms for computing the volume and other integral properties of solids. I and iI, Communications of the ACM 25, 9(September 1982), 635-650.
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. A.A.G. Requicha, Representations of rigid solids: theory, methods, and systems, A CM Computing Surveys 12, 4(December 1980), ,t37-464.
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. H. Samet, The quadtree and related hierarchical data structures, ACM Computing Surveys 16, 2(june 1984), 187-260.
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. M. Tamminen and H. Samet, Efficient octree conversion by connectivity labeling, Computer Graphics 18, 3(July 1984), pp. 43-51 (also Proceedings of the SIGGRPAH ’84 Conference, Minneapolis, July 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. R.B. Tilove, A null-object detection algorithm for constructive solid geometry, Communications of the A CM 27, 7(July lg84), 684-694.
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. M. Yau and S.N. Srihari, A hierarchical data structure for multidimensional digital images, Communications of the ACM P6, 7(July 19s3), 504-5T5.