Efficient octree conversion by connectivity labeling
Published 1 January 1984Open access
Markku Tamminen, Hanan Samet
Citations68
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
An algorithm for converting from the boundary representation of a solid to the corresponding octree model is presented, utilizing an efficient new connected components labeling technique and demonstrating that all processing can be performed directly on linear quad and octree encodings.
Abstract
We present an algorithm for converting from the boundary representation of a solid to the corresponding octree model. The algorithm utilizes an efficient new connected components labeling technique. A novelty of the method is the demonstration that all processing can be performed directly on linear quad and octree encodings. We illustrate the use of the algorithm by an application to geometric mine modeling and verify its performance by analysis and practical experiments.
Keywords
Computer ScienceEngineering
ACM Computing SurveysThe Quadtree and Related Hierarchical Data Structures
2,171 Citations1984Hanan Samet
L'accentuation est mise sur la representation de donnees dans les applications de traitement d'images, d'infographie, les systemes d'informations geographiques and the robotique.
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.
Computer Graphics and Image ProcessingGeometric modeling using octree encoding
1,244 Citations1982Donald J. Meagher
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.
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 Computer Graphics and ApplicationsSolid Modeling: Current Status and Research Directions
300 Citations1983Aristides G. Requicha, H. Voelcker
The proliferation of commercial systems over the past two years is noted, changes in system organization are discussed, work aimed at enhancing the geometric coverage, the applications coverage, and the performance of solid modeling systems is surveyed.
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.
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.
IEEE Computer Graphics and ApplicationsGWB: A Solid Modeler with Euler Operators
160 Citations1982Mantyla, Sulonen
In Helsinki, a Small but General Set of Manipulative Operations for Boundary Models of Solid Objects has been used to Construct a Comprehensive Solid Modeling System.
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.
Computer Graphics and Image ProcessingLinear octtrees for fast processing of three-dimensional objects
153 Citations1982Irene Gargantini
The newly proposed data structure is a (dynamically built) array of sorted octal codes which reflects the successive octant subdivisions which represents a dramatic improvement with respect to octtrees when space complexity is considered.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn a Method of Binary-Picture Representation and Its Application to Data Compression
138 Citations1980Eiji Kawaguchi, Tsutomu Endo
It was made clear that the DF-expression is a very effective technique as a data compression for binary pictorial patterns not only because it yields high data compression but also because its coding and decoding algorithms are very feasible.
Communications of the ACMA hierarchical data structure for multidimensional digital images
134 Citations1983Mann-may Yau, Sargur N. Srihari
A tree data structure for representing multidimensional digital binary images and an algorithm for constructing the tree of a d-dimensional binary image from the trees of its (d - 1 )-dimensional cross sections are given.
Elsevier eBooksPATTERNS AND SEARCH STATISTICS**Research sponsored by the Air Force Office of Scientific Research, Office of Aerospace Research, USAF, under Grant No. AFOSR 70-1915 and the National Science Foundation under Grant No. NSF-GK-4827. The United States Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copywright notation herein.
130 Citations1971Allen Klinger
This chapter discusses the pattern and search statistics and describes approaches to that application as to which pair of null and alternative hypotheses to emphasize in further testing.
IEEE Transactions on Pattern Analysis and Machine IntelligenceComputing Geometric Properties of Images Represented by Linear Quadtrees
111 Citations1985Hanan Samet, Markku Tamminen
A general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed and implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.
IEEE Computer Graphics and ApplicationsOctree-Related Data Structures and Algorithms
110 Citations1984Kazunori Yamaguchi, T. L. Kunii +2 more
Here, together with their formal definitions and related algorithms, are two data structures more suitable for graphics operations that are not always a desirable data structure.
Communications of the ACMAlgorithms for computing the volume and other integral properties of solids. II. A family of algorithms based on representation conversion and cellular approximation
102 Citations1982Yong Tsui Lee, Aristides A. G. Requicha
A family of algorithms for computing the volume, moments of inertia, and other integral properties of geometrically complex solids, e.g. typical mechanical parts, are discussed and a new algorithm is presented which uses recursive subdivision to convert CSG representations ofcomplex solids into approximate cellular decompositions based on variably sized blocks.
IEEE Transactions on Pattern Analysis and Machine IntelligenceQuad-Trees, Oct-Trees, and K-Trees: A Generalized Approach to Recursive Decomposition of Euclidean Space
63 Citations1983Chris L. Jackins, Steven L. Tanimoto
The algorithm provides a method for computing the perimeter of a quad-tree encoded image or the surface area of an oct- tree encoded object in worst case time proportional to the number of nodes in the tree, improves upon the expected-case linear-time method of Samet for the perimeter problem.
Computer Vision Graphics and Image ProcessingA new three-dimensional connected components algorithm
56 Citations1983Ronald Lumia
An efficient new algorithm which calculates the connected components of a binary image with a relatively small equivalence table is reported, suitable for both large and small computer systems.
Localized set operations for solid modeling
46 Citations1983Martti Mäntylä, Markku Tamminen
This work presents an algorithm that employs a three-dimensional extendible cell (EXCELL) directory to the set operation problem, and demonstrates by practical experiments the efficiency and the local nature of the algorithm.
ACM SIGGRAPH Computer GraphicsLocalized set operations for solid modeling
42 Citations1983Martti Mäntylä, Markku Tamminen
Journal of the ACMEfficiency of a Good But Not Linear Set Union Algorithm
38 Citations1975Robert E. Tarjan
It is shown that, if t(m, n) is seen as the maximum time reqmred by a sequence of m > n FINDs and n -- 1 intermixed UNIONs, then kima(m), n is shown to be related to a functional inverse of Ackermann's functmn and as very slow-growing.
Computer Vision Graphics and Image ProcessingEncoding pixel trees
37 Citations1984Markku Tamminen
It is shown that asymptotically, as resolution is increased with respect to image detail, a multicolor image can be represented with less than 5 bits per intersected pixel, compared to the 2–3 bits required by chain encoding schemes.
Computer-Aided DesignRay-casting and block model conversion using a spatial index
32 Citations1984Markku Tamminen, Olli Karonen +1 more
The 3D extensible cell (EXCELL) index is presented together with algorithms for spatial search and for converting a complex polyhedron (boundary representation) into an octree-like block model.
Computer Graphics and Image ProcessingA new three dimensional connected components algorithm
7 Citations1982Ronald Lumia