Object representation by means of nonminimal division quadtrees and octrees

ABSTRACT

Quadtree representation of two-dimensional objects is performed with a tree that describes the recursive subdivision of the more complex parts of a picture until the desired resolution is reached. At the end, all the leaves of the tree are square cells that lie completely inside or outside the object. There are two great disadvantages in the use of quadtrees as a representation scheme for objects in geometric modeling system: The amount of memory required for polygonal objects is too great, and it is difficult to recompute the boundary representation of the object after some Boolean operations have been performed. In the present paper a new class of quadtrees, in which nodes may contain zero or one edge, is introduced. By using these quadtrees, storage requirements are reduced and it is possible to obtain the exact backward conversion to boundary representation. Algorithms for the generation of the quadtree, Boolean operations, and recomputation of the boundary representation are presented, and their complexities in time and space are discussed. Three-dimensional algorithms working on octrees are also presented. Their use in the geometric modeling of three-dimensional polyhedral objects is discussed.

REFERENCES

• 1: BOYSE, J. W., AND GILCHRIST, J.E. GMSolid: Interactive modeling for design and analysis of solids. IEEE Comput. Graph. Appl. 2, 2 (Mar. 1982), 27-40.
• 2: Charles R. Dyer , Azriel Rosenfeld , Hanan Samet, Region representation: boundary codes from quadtrees, Communications of the ACM, v.23 n.3, p.171-179, March 1980 [doi>10.1145/358826.358838]
• 3: GARGANTINI, I. Linear octrees for fast processing of three-dimensional objects. Comput. Graph. Image Process. 20 (1982), 365-374.
• 4: HEGRON, G. Techniques de remplisage de taches sur une surface a pointillage. Rep. IMI-Info- 5. Universit6 de Nantes, France, Sept. 1982.
• 5: HUNTER, G. M., AND STEIGLITZ, K. Operations on images using quad trees. IEEE Trans. Pattern Anal. Mach. Intell. 1, 2 (Apr. 1979), 145-153.
• 6: JACKINS, C. L., AND TANIMOTO, S.L. Oct-trees and their use in representing three-dimensional objects. Comput. Graph. Image Process. 14 (1980), 249-270.
• 7: OLIVER, M. A., AND WISEMAN, N.E. Operations on quadtree encoded images. Comput. J. 26, 1 (Jan. 1983), 83-91.
• 8: REQUICHA, A. A. G., AND VOELCKER, H. B. Solid modelling: A historical summary and contemporary assessment. IEEE Comput. Graph. Appl. 2, 2 (Mar. 1982), 9-24.
• 9: SHNEIER, M. Calculations of geometric properties using quadtrees. Comput. Graph. Image Process. 16 (1981), 296-302.

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations; Geometric algorithms, languages, and systems; Modeling packages

General Terms:
Algorithms