Geometric modeling using octree encoding
Computer Graphics and Image ProcessingPublished 1 June 1982
Donald J. Meagher
Citations1,244
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Efficient (linear time) algorithms have been developed for the Boolean operations, geometric operations,translation, scaling and rotation, N-dimensional interference detection, and display from any point in space with hidden surfaces removed.
Abstract
A geometric modeling technique called Octree Encoding is presented. Arbitrary 3-D objects can be represented to any specified resolution in a hierarchical 8-ary tree structure or "octree" Objects may be concave or convex, have holes (including interior holes), consist of disjoint parts, and possess sculptured (i.e., "free-form") surfaces. The memory required for representation and manipulation is on the order of the surface area of the object. A complexity metric is proposed based on the number of nodes in an object's tree representation. Efficient (linear time) algorithms have been developed for the Boolean operations (union, intersection and difference), geometric operations (translation, scaling and rotation), N-dimensional interference detection, and display from any point in space with hidden surfaces removed. The algorithms require neither floating-point operations, integer multiplications, nor integer divisions. In addition, many independent sets of very simple calculations are typically generated, allowing implementation over many inexpensive high-bandwidth processors operating in parallel. Real time analysis and manipulation of highly complex situations thus becomes possible.
Keywords
Computer ScienceEngineering
LeonardoPrinciples of Interactive Computer Graphics
1,572 Citations1975Dick Land, William M. Newman +1 more
The principles of interactive computer graphics are applied to computer graphics practice and show the importance of user interaction in the development of computer graphics algorithms.
ACM Computing SurveysRepresentations for Rigid Solids: Theory, Methods, and Systems
1,430 Citations1980Aristides G. Requicha
A coherent view, based on sound theoretical principles, of what is presently known about the representation of solids is provided by providing a simple mathematical framework for characterizing certain important aspects of representations, for example, their semantic (geometric) integrity.
Communications of the ACMHierarchical geometric models for visible surface algorithms
774 Citations1976James H. Clark
Communications of the ACMMultidimensional divide-and-conquer
676 Citations1980Jon Bentley
Multidimensional divide-and-conquer is discussed, an algorithmic paradigm that can be instantiated in many different ways to yield a number of algorithms and data structures for multidimensional problems.
Computer Graphics and Image ProcessingOct-trees and their use in representing three-dimensional objects
577 Citations1980Chris L. Jackins, Steven L. Tanimoto
Oct-Trees are developed as a three-dimensional analog of quad-trees to be used in geometric modeling and space planning and a fast algorithm is given for 90° rotation of oct-tree representations of objects.
IEEE Transactions on Software EngineeringMultidimensional Binary Search Trees in Database Applications
410 Citations1979Jon Bentley
The purposes of this paper are to cast k-D trees in a database framework, to collect the results on k-d trees that have appeared since the structure was introduced, and to show how the basic data structure can be modified to facilitate implementation in large (and very large) databases.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOperations on Images Using Quad Trees
405 Citations1979Gregory M. Hunter, Kenneth Steiglitz
Warnock-type algorithms are presented for building the quad tree for the picture of the boundary of apolygon, and for coloring the interior of such a polygon.
A 3-dimensional representation for fast rendering of complex scenes
308 Citations1980Steven M. Rubin, Turner Whitted
This paper describes a method whereby the object space is represented entirely by a hierarchical data structure consisting of bounding volumes, with no other form of representation, which allows the visible surface rendering to be performed simply and efficiently.
ACM SIGGRAPH Computer GraphicsA 3-dimensional representation for fast rendering of complex scenes
201 Citations1980Steven M. Rubin, Turner Whitted
Journal of the ACMConnected Component Labeling Using Quadtrees
195 Citations1981Hanan Samet
Analysis of the algorithm reveals that its worst case average execution time is bounded by a quantity proportional to the product of the log of the region's diameter and the number of blocks comprising the area connected by the components.
Computer-Aided DesignGeometric modelling: a survey
193 Citations1979Adrian E. Baer, Charles M. Eastman +1 more
Issues and alternatives in geometric modelling are discussed and illustrated with comparisons of 11 existing modelling systems, in particular coherently-structured models of polyhedral solids where the faces may be either planar or curved.
Communications of the ACMRegion representation
174 Citations1980Hanan Samet
An algorithm is presented for constructing a quadtree for a region given its boundary in the form of a chain code that reveals that its execution time is proportional to the product of the perimeter and the log of the diameter of the region.
ComputerGeometric Modeling of Mechanical Parts and Processes
161 Citations1977H. Voelcker, Aristides A. G. Requicha
Dramatic changes are likely to occur in the next decade, however, because the deficiencies of current methods are retarding the progress of automation and are stimulating the development of new, computationally oriented schemes for handling mechanical geometry.
ACM Computing SurveysRepresentation of Three-Dimensional Digital Images
159 Citations1981Sargur N. Srihari
This paper attempts to unify data structures for representing interior, surface, and structural information of objects in such images by companng their relative efficium by survey of three-dimensmnal spatial-data representation methods emphasizing techniques that apply to cellular images.
Communications of the ACMRegion representation
144 Citations1980Charles R. Dyer, Azriel Rosenfeld +1 more
This paper presents an algorithm for converting from quadtrees to a simple class of boundary codes and is shown to have an execution time proportional to the perimeter of the region.
IEEE Transactions on Pattern Analysis and Machine IntelligenceAn Algorithm for Converting Rasters to Quadtrees
120 Citations1981Hanan Samet
An algorithm is presented for constructing a quadtree for a binary image given its row-by-row description that processes the image one row at a time and merges identically colored sons as soon as possible, so that a minimal size quadtree exists after processing each pixel.
Computer Graphics and Image ProcessingRegion representation: Quadtrees from binary arrays
103 Citations1980Hanan Samet
An algorithm is presented for constructing a quadtree from the array representation of a binary image that examines each pixel in the image once and only once, and never requires temporary nodes.
IEEE Transactions on Pattern Analysis and Machine IntelligenceDistance Transform for Images Represented by Quadtrees
81 Citations1982Hanan Samet
The chessboard distance metric is shown to be particularly suitable for the quadtree and an algorithm is presented which computes this transform by only examining the BLACK node's adjacent and abutting neighbors and their progeny.
Computer Graphics and Image ProcessingLinear transformation of pictures represented by quad trees
70 Citations1979Gregory M. Hunter, K. Steiglitz
The transformation algorithm is shown to take time O(n + sp + mg) , where n is the number of nodes in the input tree, s is a scale factor, p is the total perimeter of all the regions of the original picture, m is theNumber of regions, and q is a resolution parameter.
Computing Perimeters of Images Represented by Quadtrees
44 Citations1979Hanan Samet
An algorithm is presented for computing the total perimeter of a binary image represented by a quadtree and it is shown that its worst- case average execution time is proportional to the product of the log of the image diameter and the number of nodes in the tree.
A linear time exact hidden surface algorithm
44 Citations1980Wm. Randolph Franklin
This paper presents a new hidden surface algorithm that overlays a grid on the screen whose fineness depends on the number and size of the faces, and is as accurate as the arithmetic precision of the computer.
ACM SIGGRAPH Computer GraphicsA linear time exact hidden surface algorithm
41 Citations1980Wm. Randolph Franklin
IEEE Transactions on ComputersProperty Encoding: Application in Binary Picture Encoding and Boundary Following
27 Citations1972Gursharan S. Sidhu, Raymond Boute
The containment code is defined, a special case of the more general property code presented in [1], which permits a compression of data into a linear array that can be stored for later processing or for picture reconstruction.
Elsevier eBooksTREE STRUCTURES FOR REGION REPRESENTATION The support of the Defense Advanced Research Projects Agency and the U.S. Army Night Vision Laboratory under Contract DAAG-53-76C-0138 (DARPA Order 3206) is gratefully acknowledged, as is the help of Kathryn Riley in preparing this paper. The material in this paper is based on a series of reports by H. Samet, as well as two reports by C. R. Dyer and M. Shneier.
13 Citations1980Azriel Rosenfeld
A method of representing arrays by trees of degree 4, which are constructed by recursively subdividing the array into blocks of constant value, can be applied to binary arrays representing regions.
Region Representation: Quadtree-to-Raster Conversion
9 Citations1979Hanan Samet
An algorithm is presented for obtaining a raster representation for an image given its quadtree and its execution time is proportional to the sum of the heights of the blocks comprising the image.