Hierarchical data structures and algorithms for computer graphics. I. Fundamentals
- 1 May 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Computer Graphics and Applications
- Vol. 8 (3), 48-68
- https://doi.org/10.1109/38.513
Abstract
The fundamentals of hierarchical data structures are reviewed and it is shown how they are used in the implementation of some basic operations in computer graphics. The properties of hierarchical structures are discussed, focusing on quadtrees and octrees. The latter are defined, some of the more common ways in which they are implemented are examined, and an explanation of the quadtree/octree complexity theorem is provided. Vector quadtrees and vector octrees are discussed. The performance of basic operations using quadtrees is considered.Keywords
This publication has 69 references indexed in Scilit:
- Storing a collection of polygons using quadtreesACM Transactions on Graphics, 1985
- Operations on Quadtree Leaves and Related Image AreasThe Computer Journal, 1983
- Depth-First Picture Expression Viewed from Digital Picture ProcessingIeee Transactions On Pattern Analysis and Machine Intelligence, 1983
- Operations on Quadtree Encoded ImagesThe Computer Journal, 1983
- An effective way to represent quadtreesCommunications of the ACM, 1982
- Vectorization of raster images using hierarchical methodsComputer Graphics and Image Processing, 1982
- Geometric modeling using octree encodingComputer Graphics and Image Processing, 1982
- Oct-trees and their use in representing three-dimensional objectsComputer Graphics and Image Processing, 1980
- On a Method of Binary-Picture Representation and Its Application to Data CompressionIeee Transactions On Pattern Analysis and Machine Intelligence, 1980
- Operations on Images Using Quad TreesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1979