“Efficient octree conversion by connectivity labeling” by Tamminen and Samet

We present an algorithm for converting from the boundary representation of a solid to the corresponding octree model. The algorithm utilizes an efficient new connected components labeling technique. A novelty of the method is the demonstration that all processing can be performed directly on linear quad and octree encodings. We illustrate the use of the algorithm by an application to geometric mine modeling and verify its performance by analysis and practical experiments.

1. Gargantini, I., Linear octtrees for fast processing of three dimensional objects. CVGIP 20 (1982) 4, pp. 363-374.
2. Jackins, C.L. and Tanimoto, S.L., Oct-trees and their use in representing three-dimensional objects. CGIP 14(1980), pp. 249-270.
3. Jackins, C.L. and Tanimoto, S.L., Quad-trees, oct-trees and K-trees: a generalized approach to recursive decomposition of Euclidean space. IEEE PAMI-5(1983)5, pp. 533-539.
4. Journel, A.G. and Huijbregts, Ch, J., Mining Geostatistics. Academic Press, 1978.
5. Karonen, O., Tamminen, M., Kerola, P., Mitjonen, M., and Orivuori, E., A geometric mine modeling system. Proc. Autocarto Six Conference, Ottawa, 1983 pp. 374-383.
6. Kawaguchi, E. and Endo, T., On a method of binary picture representation and its application to data compression. IEEE PAMI 5(1980) 1, pp. 27-35.
7. Klinger, A., Patterns and search statistics. In Optimizing Methods in Statistics, Rustagi, J.S. (Ed.), Academic Press New York, 1971, pp. 303-337.
8. Lee, Y.T. and Requicha, A.A.G., Algorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation. CACM 25(1982)9, pp. 642-650.
9. Lumia, R., A new three-dimensional connected components algorithm. CVGIP 23(1983), pp. 207-217.
10. Meagher, D., Geometric modeling using octree encoding. CGIP 19(1982a), pp. 129-147.
11. Meagher, D., Octree generation, analysis and manipulation Report IPL-TR-027, Rensselaer Polytechnic Institute, Troy, New York, 1982b.
12. Meagher, D., Personal communication. 1983.
13. Mantyla, M. and Sulonen, R., GWB- A Solid Modeler With Euler Operators. IEEE Computer Graphics & Applications 2(1982)7, pp. 17-31
14. Mantyla, M and Tamminen, M., Localized set operations for solid modeling. Computer Graphics 17(1983)3, pp. 279-288.
15. Requicha, A.A.G. and Voelcker, H.B., Solid modeling: current status and research directions. IEEE Computer Graphics and Applications 3(1983) 7, pp. 25 – 37.
16. Requicha, A.A.G., Representations of rigid solids: theory, methods and systems. ACM Comp. Surv. 12(1980), pp. 437-464.
17. Samet, H., Region representation: quadtrees from boundary codes. CACM 23(1980)3, pp. 163-170.
18. Samet, H., Connected component labeling using quadtrees. JACM 28(1981)3, pp. 487-501.
19. Samet, H., The quadtree and related hierarchical data structures. To appear in ACM Comp. Surv. Also TR-1329, Computer Science Department, University of Maryland, College Park, MD, 1983.
20. Samet, H. and Tamminen, M., Computing geometric properties of images represented by linear quadtrees. Report TR-1359, Computer Science Department, University of Maryland, College Park, MD, 1983.
21. Samet, H. and Tamminen, M., Efficient image component labeling. Report TR-1420, Computer Science Department, University of Maryland, College Park, MD, 1984.
22. Sedgewick, R., Algorithms. Addison-Wesley, Reading, 1983.
23. Srihari, S.N., Representation of three dimensional digital images. ACM Comp. Surv. 13(1981)4, pp. 399-423.
24. Tamminen, M., Encoding pixel trees. To be published in CVGIP, 1984.
25. Tamminen, M., Karenen, O., and Mantyla, M., Block model conversion using an efficient spatial index. To be published in CAD Journal, 1984.
26. Tarjan, R.E., On the efficiency of a good but not linear set union algorithm. JACM 22(1975), pp. 215-225.
27. Yamaguchi, K., and Kunii, T.L., A layered string data structure for an octree model. Techn. Rep. 83-15, Dept. of Information Science, Univ. of Tokyo, 1983.
28. Yamaguchi, K., Kunii, T.L., Fujimura, K. and Toriya, H., Octree-related data structures and algorithms. IEEE Computer Graphics and Applications 4(1984)1, pp. 53-59.
29. Yau, M-M and Srihari, S.N., A hierarchical data structure for multidimensional images. CACM 26(1983)7, pp. 504-515.