Line drawings of octree-represented objects

ABSTRACT

The octree structure represents the space occupied by an object as a juxtaposition of cubes, where the sizes and position coordinates of the cubes are integer powers of 2 and are defined by a recursive decomposition of three-dimensional space. This makes the octree structure highly sensitive to object location and orientation, and the three-dimensional shape of the represented object obscure. It is helpful to be able to see the actual object represented by an octree, especially for visual performance evaluation of octree algorithms. Presented in this paper is a display algorithm that helps visualize the three-dimensional space represented by the octree. Given an octree, the algorithm produces a line drawing of the objects represented by the octree, using parallel projection, from any specified viewpoint with hidden lines removed. The order in which the algorithm traverses the octree has the property that if node x occludes node y, then node x is visited before node y. The algorithm produces a set of long, straight visible edge segments corresponding to the visible surface of the polyhedral object represented by the octree. Examples of some line drawing produced by the algorithm are given. The complexity of the algorithm is also discussed.

REFERENCES

• 1: AHUJA, N., AND NASH, C. Octree representations of moving objects. Comput. Vision Graph. Image Process. 26 (1984), 207-216.
• 2: AHUJA, N., AND VEENSTRA, J. Octree generation and display. Tech. Rep. UILU-ENG-86-2215. Coordinated Science Laboratory, Univ. of Illinois, Urbana, May 1986.
• 3: BROOKS, R. Symbolic reasoning among models and 2-D images. Artif. Intell. 17 (1981), 285-348.
• 4: C H Chien , J K Aggarwal, Volume/surface octrees for the representation of three-dimensional objects, Computer Vision, Graphics, and Image Processing, v.36 n.1, p.100-113, Oct. 1986 [doi>10.1016/S0734-189X(86)80031-7]
• 5: DOCTOR, L. J., AND TORBORG, J. G. Display techniques for octree-encoded objects. IEEE Comput. Graph. Appl. 1, 3 (1981), 29-38.
• 6: James D. Foley , Andries Van Dam, Fundamentals of interactive computer graphics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 7: GARGANTINI, I. Linear octrees for fast processing of three-dimensional objects. Comput. Graph. Image Process. 20, 4 (Dec. 1982), 365.
• 8: SONG, W. H., AND SHNEIEF., M. Describing a robot's workspace using a sequence of views from a moving camera. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-7 (Nov. 1985), 721-726.
• 9: JACKINS, C. L., AND TANIMOTO, S.L. Oct-trees and their use in representing three-dimensional objects. Comput. Graph. Image Process. 14, 3 (Nov. 1980), 249-270.
• 10: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 11: MEAGHER, D. Efficient synthetic image generation of arbitrary 3-D objects. In Proceedings of the IEEE Conference on Pattern Recognition and Image Processing (Las Vegas, Nev., June 14-17, 1982), p. 473.
• 12: MEAGHER, D. Geometric modeling using octree encoding. Comput. Graph. Image Process. 19, 2 (1982), 129.
• 13: William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
• 14: OSSE, W., AND AHUJA, N. Efficient octree representation of moving objects. In Proceedings of the IAPR 7th International Conference on Pattern Recognition (Montreal, Quebec, July 30- Aug. 2, 1984), pp. 821-823.
• 15: SHNEIER, M., KENT, E., AND MANSBACH, P. Representing workspace and model knowledge for a robot with mobile sensors. In Proceedings of the IAPR 7th International Conference on Pattern Recognition (Montreal, Quebec, July 30-Aug. 2, 1984), pp. 199-202.
• 16: VEENSTRA, J., AND AHUJA, N. Octree generation of an object from silhouette views. In Proceedings of the 1985 IEEE International Conference on Robotics and Automation (St. Louis, Mo., Mar. 25-28, 1985), pp. 843-848.

INDEX TERMS

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

General Terms:
Algorithms