CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Ayala, D., P. Brunet and Juan (et al)
year 1985
title Object Representation by Means of Nominimal Division Quadtrees and Octrees
source ACM Transactions on Graphics. January, 1985. vol. 4: pp. 41-59 : ill. includes bibliography
summary 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 operation, 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
keywords geometric modeling, algorithms, octree, quadtree, curves, curved surfaces, boolean operations
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
HOMELOGIN (you are user _anon_319501 from group guest) Works Powered by SciX Open Publishing Services 1.002