Please use this identifier to cite or link to this item:
Title: Efficient linear octree generation from voxels
Authors: Shu, R. 
Kankanhalli, M.S. 
Keywords: linear quadtrees/octrees
quadtree/octree construction
Issue Date: Jun-1994
Citation: Shu, R.,Kankanhalli, M.S. (1994-06). Efficient linear octree generation from voxels. Image and Vision Computing 12 (5) : 297-303. ScholarBank@NUS Repository.
Abstract: The linear octree is an efficient data structure for compact representation of voxel data. There are several algorithms to generate a linear octree from voxel data with time complexity O(n3) for an input of size n3 voxels. We present a new algorithm which first extracts the surface of the object. Based on this surface data, the object is partitioned into a set of parallelepipeds where each parallelepiped is a contiguous run of voxels along one axis. Starting from the lowest level of the octree, the algorithm proceeds iteratively to the highest level, computing maximal overlaps of the parallelepipeds at each level. For any level, the voxels which are not in the overlap are octree nodes and are output at that level. The maximal overlapped parallelepipeds form the input to the next higher level in the algorithm. For a connected object having n3 voxels, the algorithm has a time complexity of O(S) where S is the size of the surface of the object. The algorithm has been implemented and tested for a variety of medical data. © 1994.
Source Title: Image and Vision Computing
ISSN: 02628856
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Oct 12, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.