D. Ayala
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.
- 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.Google Scholar
- 2 DYER, C. R. ROSENFELD, A., AND SAMET, H. Region representation: Boundary codes from quadtrees. Commun. ACM 23, 3 (Mar. 1980), 171-179. Google Scholar
- 3 GARGANTINI, I. Linear octrees for fast processing of three-dimensional objects. Comput. Graph. Image Process. 20 (1982), 365-374.Google Scholar
- 4 HEGRON, G. Techniques de remplisage de taches sur une surface a pointillage. Rep. IMI-Info- 5. Universit6 de Nantes, France, Sept. 1982.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 7 OLIVER, M. A., AND WISEMAN, N.E. Operations on quadtree encoded images. Comput. J. 26, 1 (Jan. 1983), 83-91.Google Scholar
- 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.Google Scholar
- 9 SHNEIER, M. Calculations of geometric properties using quadtrees. Comput. Graph. Image Process. 16 (1981), 296-302.Google Scholar
Index Terms
- Object representation by means of nonminimal division quadtrees and octrees
Recommendations
Solid representation and operation using extended octrees
Solid modelers must be based on reliable and fast algorithms for Boolean operations. The octree model, as well as several generalizations (polytrees, integrated polytrees, extended octrees), is specially well suited for these algorithms and can be used ...
Navigating through triangle meshes implemented as linear quadtrees
Techniques are presented for navigating between adjacent triangles of greater or equal size in a hierarchical triangle mesh where the triangles are obtained by a recursive quadtree-like subdivision of the underlying space into four equilateral ...
Triangular Mesh Generation of Octrees of Non-Convex 3D Objects
ICPR '06: Proceedings of the 18th International Conference on Pattern Recognition - Volume 03A general surface-generating algorithm, the Marching Cube, produces triangular meshes from octants where the vertices of octants are clearly classified into either inside or outside the object. However, the algorithm is ambiguous for octrees ...
Reviews
W. Teunissen
This paper presents a technique to store polygons and polyhedra using quadtrees and octrees, respectively. The essential difference with the standard quadtrees is that the squares corresponding to the end nodes in the tree need not necessarily be completely located within the object. It is permitted that an edge of the polygon intersects such a square and cuts off a piece. In the “new” quadtrees, the corresponding node is still considered an end node, and it is stored in the quadtree with a reference to a data structure in which that crossing edge is kept. An analogous description for polyhedra is given. The program algorithms presented in the text, as well as the explanations following them, are of poor quality and should not have been published in this loose format. Another, more or less connected, problem is the question of which kind of polygons are permitted as input to the conversion routine. For instance, the fact that crossing edges cannot be handled was not mentioned in the text. Whether polygons that have more than two edges with a common vertex, or more than two edges at the minimum resolution level are permitted is also not clear from the text. There are numerous mistakes in the text; for example: :9Bputout(pointer, pointer) on p. 45 where putout appears to be a generic function with variable parameter list. Fig. 3 is superfluous (quadrant ordering was explained at the occasion of Fig. 1). The meaning of the pictures in Fig. 6 is not clear. On p. 50 polyline should be substituted for fillarea, not the reverse. In Fig. 8(b) the vertical axis should be labeled gn instead of ng. The printing of quantities such as gn, par, nc, etc. (in themselves meaningless names for variables) occurs in Roman font in one place and in italic someplace else. On p. 45, minscale and maxscale are undefined. The conclusion should be that the proposed method has some clear advantages over the use of the old quadtrees: :9BThere is no loss in information when translating back and forth between polygon representation and the “new” quadtrees because the polygon data remain part of the data used for the quadtrees. Set operations such as intersection, difference, and complement are very easy to perform. When one has to intersect polygons very often, one might even consider to translate to these “new” quadtrees before performing the operation, even when the quadtree is only used for that particular purpose. It is only unfortunate that these good ideas were presented in such a sloppy paper.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments