Editing Octree

{{Short description|Tree data structure in which each internal node has exactly eight children, to partition a 3D space}}
{{Infobox data structure
| name               = Octree
| image              = 
| alt                = 
| caption            = 
| type               = Tree
| invented_by        = Donald Meagher
| invented_year      = 1980
| space_avg          = O(N)
| space_worst        = O(N)
| search_avg         = O(logN+K)
| search_worst       = O(logN+K)
| insert_avg         = O(logN)
| insert_worst       = O(logN)
| delete_avg         = O(logN)
| delete_worst       = O(logN)
| peek_avg           = O(logN)
| peek_worst         = O(logN)
| find_min_avg       = 
| find_min_worst     = 
| delete_min_avg     = 
| delete_min_worst   = 
| decrease_key_avg   = 
| decrease_key_worst = 
| merge_avg          = 
| merge_worst        = 
}}
[[File:Octree2.svg|thumb|Left: Recursive subdivision of a cube into [[octant (solid geometry)|octant]]s. Right: The corresponding octree.]]

An '''octree''' is a [[tree data structure]] in which each [[internal node]] has exactly eight [[child node|children]]. Octrees are most often used to partition a [[three-dimensional space]] by [[recursive subdivision|recursively subdividing]] it into eight [[Octant (geometry)|octants]]. Octrees are the three-dimensional analog of [[quadtree]]s. The word is derived from ''oct'' (Greek root meaning "eight") + ''tree''. Octrees are often used in [[3D graphics]] and 3D [[game engine]]s.

==For spatial representation==
Each node in an octree subdivides the space it represents into eight [[octant (solid geometry)|octant]]s. In a point region (PR) octree (analogous to a point quadtree), the node stores an explicit [[Point (geometry)|three-dimensional point]], which is the "center" of the subdivision for that node; the point defines one of the corners for each of the eight children. In a matrix-based (MX) octree (analogous to a region quadtree), the subdivision point is implicitly the center of the space the node represents. The root node of a PR octree can represent infinite space; the root node of an MX octree must represent a finite bounded space so that the implicit centers are well-defined. Note that octrees are not the same as [[k-d tree|''k''-d trees]]: ''k''-d trees split along a dimension and octrees split around a point. Also ''k''-d trees are always binary, which is not the case for octrees.
By using a [[depth-first search]] the nodes are to be traversed and only required surfaces are to be viewed.

==History==
The use of octrees for [[3D computer graphics]] was pioneered by Donald Meagher at [[Rensselaer Polytechnic Institute]], described in a 1980 report "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer",<ref>{{cite journal|last=Meagher|first=Donald|title=Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer|journal=Rensselaer Polytechnic Institute|date=October 1980|issue=Technical Report IPL-TR-80-111}}</ref>  for which he holds a 1995 patent (with a 1984 [[priority right|priority date]]) "High-speed image generation of complex solid objects using octree encoding" <ref>{{cite web|last=Meagher|first=Donald|title=High-speed image generation of complex solid objects using octree encoding|url=https://patents.google.com/patent/EP0152741B1/en|publisher=USPO|access-date=20 September 2012}}</ref>

==Common uses==
* [[Level of detail (computer graphics)|Level of detail]] rendering in [[3D computer graphics]]<ref name="Luebke2003">{{cite book|author=David P. Luebke|title=Level of Detail for 3D Graphics|url=https://books.google.com/books?id=M-gl4aoxQfIC|year=2003|publisher=Morgan Kaufmann|isbn=978-1-55860-838-2}}</ref>
* [[Spatial index]]ing
* [[Nearest neighbor search]]<ref>Elseberg, Jan, et al. "[https://www.researchgate.net/profile/Andreas_Nuchter/publication/233792571_Comparison_on_nearest-neigbour-search_strategies_and_implementations_for_efficient_shape_registration/links/0912f50b8bb8590953000000/Comparison-on-nearest-neigbour-search-strategies-and-implementations-for-efficient-shape-registration.pdf Comparison of nearest-neighbor-search strategies and implementations for efficient shape registration]." Journal of Software Engineering for Robotics 3.1 (2012): 2-12.</ref>
* Efficient [[collision detection]] in three dimensions
* [[View frustum culling]]
* [[Fast multipole method]]
* [[Unstructured grid]]
* [[Finite element analysis]]
* [[Sparse voxel octree]]<ref>{{Cite book|last1=Akenine-Mo ̈ller|first1=Tomas|url=https://books.google.com/books?id=0g1mDwAAQBAJ&dq=%22sparse+voxel+octree%22&pg=PA579|title=Real-Time Rendering, Fourth Edition|last2=Haines|first2=Eric|last3=Hoffman|first3=Naty|date=2018-08-06|publisher=CRC Press|isbn=978-1-351-81615-1|language=en}}</ref>
* [[State estimation]]<ref>[http://isas.uka.de/Publikationen/Fusion10_EberhardtKlumpp.pdf Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, ''Density Trees for Efficient Nonlinear State Estimation'', Proceedings of the 13th International Conference on Information Fusion, Edinburgh, United Kingdom, July, 2010.]</ref>
* [[Set estimation]]<ref>
[http://www.ensta-bretagne.fr/jaulin/paper_drevelle_nolcos_2013.pdf V. Drevelle, L. Jaulin and B. Zerr, ''Guaranteed Characterization of the Explored Space of a Mobile Robot by using Subpavings'', NOLCOS 2013.]</ref>

==Application to color quantization==

The octree [[color quantization]] algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because <math>2^3 = 8</math> and there are three color components in the [[RGB]] system. The node index to branch out from at the top level is determined by a formula that uses the most significant bits of the red, green, and blue color components, e.g. 4r + 2g + b. The next lower level uses the next bit significance, and so on. Less significant bits are sometimes ignored to reduce the tree size.

The algorithm is highly memory efficient because the tree's size can be limited. The bottom level of the octree consists of leaf nodes that accrue color data not represented in the tree; these nodes initially contain single bits. If much more than the desired number of palette colors are entered into the octree, its size can be continually reduced by seeking out a bottom-level node and averaging its bit data up into a leaf node, pruning part of the tree. Once sampling is complete, exploring all routes in the tree down to the leaf nodes, taking note of the bits along the way, will yield approximately the required number of colors.

==Implementation for point decomposition==
The example recursive algorithm outline below ([[MATLAB]] syntax) decomposes an array of 3-dimensional points into octree style bins. The implementation begins with a single bin surrounding all given points, which then recursively subdivides into its 8 octree regions. Recursion is stopped when a given exit condition is met. Examples of such exit conditions (shown in code below) are:
* When a bin contains fewer than a given number of points
* When a bin reaches a minimum size or volume based on the length of its edges
* When recursion has reached a maximum number of subdivisions
<syntaxhighlight lang="matlab">
function [binDepths, binParents, binCorners, pointBins] = OcTree(points)

binDepths = [0]     % Initialize an array of bin depths with this single base-level bin
binParents = [0]    % This base level bin is not a child of other bins
binCorners = [min(points) max(points)] % It surrounds all points in XYZ space
pointBins(:) = 1    % Initially, all points are assigned to this first bin
divide(1)           % Begin dividing this first bin

function divide(binNo)

% If this bin meets any exit conditions, do not divide it any further.
binPointCount = nnz(pointBins == binNo)
binEdgeLengths = binCorners(binNo, 1:3) - binCorners(binNo, 4:6)
binDepth = binDepths(binNo)
exitConditionsMet = binPointCount<value || min(binEdgeLengths) < value || binDepth > value
if exitConditionsMet
    return; % Exit recursive function
end

% Otherwise, split this bin into 8 new sub-bins with a new division point
newDiv = (binCorners(binNo, 1:3) + binCorners(binNo, 4:6)) / 2
for i = 1:8
    newBinNo = length(binDepths) + 1
    binDepths(newBinNo) = binDepths(binNo) + 1
    binParents(newBinNo) = binNo
    binCorners(newBinNo) = [one of the 8 pairs of the newDiv with minCorner or maxCorner]
    oldBinMask = pointBins == binNo
    % Calculate which points in pointBins == binNo now belong in newBinNo
    pointBins(newBinMask) = newBinNo
    % Recursively divide this newly created bin
    divide(newBinNo)
end
</syntaxhighlight>

==Example color quantization==
Taking the full list of colors of a 24-bit RGB image as point input to the Octree point decomposition implementation outlined above, the following example show the results of octree color quantization. The first image is the original (532818 distinct colors), while the second is the quantized image (184 distinct colors) using octree decomposition, with each pixel assigned the color at the center of the octree bin in which it falls. Alternatively, final colors could be chosen at the centroid of all colors in each octree bin, however this added computation has very little effect on the visual result.<ref>Bloomberg, Dan S. [http://leptonica.org/papers/colorquant.pdf "Color quantization using octrees."], 4 September 2008. Retrieved on 12 December 2014.</ref>
<syntaxhighlight lang="matlab">
% Read the original RGB image
Img = imread('IMG_9980.CR2');
% Extract pixels as RGB point triplets
pts = reshape(Img, [], 3);
% Create OcTree decomposition object using a target bin capacity
OT = OcTree(pts, 'BinCapacity', ceil((size(pts, 1) / 256) * 7));
% Find which bins are "leaf nodes" on the octree object
leafs = find(~ismember(1:OT.BinCount, OT.BinParents) & ...
    ismember(1:OT.BinCount, OT.PointBins));
% Find the central RGB location of each leaf bin
binCents = mean(reshape(OT.BinBoundaries(leafs,:), [], 3, 2), 3);
 
% Make a new "indexed" image with a color map
ImgIdx = zeros(size(Img, 1), size(Img, 2));
for i = 1:length(leafs)
    pxNos = find(OT.PointBins==leafs(i));
    ImgIdx(pxNos) = i;
end
ImgMap = binCents / 255; % Convert 8-bit color to MATLAB rgb values
 
% Display the original 532818-color image and resulting 184-color image 
figure
subplot(1, 2, 1), imshow(Img)
title(sprintf('Original %d color image', size(unique(pts,'rows'), 1)))
subplot(1, 2, 2), imshow(ImgIdx, ImgMap)
title(sprintf('Octree-quantized %d color image', size(ImgMap, 1)))
</syntaxhighlight>

==See also==
* [[Binary space partitioning]]
* [[Bounding interval hierarchy]]
* ''[[Cube 2: Sauerbraten]]'', a 3D game engine in which geometry is almost entirely based on octrees
* [[id Tech 6]] is a 3D game engine that utilizes voxels stored in octrees
* [[Irrlicht Engine]], supports octree scene nodes
* [[Klee's measure problem]]
* [[Linear octree]]
* [[OGRE]], has an octree scene manager implementation
* [[Subpaving]]
* [[Voxel]]
* [[Quadtree]]

==References==
{{reflist}}

==External links==
{{commons category|Octrees}}
*[https://web.archive.org/web/20140605161956/http://www.microsoft.com/msj/archive/S3F1.aspx Octree Quantization in Microsoft Systems Journal]
*[http://www.ddj.com/184409805 Color Quantization using Octrees in Dr. Dobb's]
*[http://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant/CQoctree.html Octree Color Quantization Overview]
*{{cite book|chapter-url=https://ieeexplore.ieee.org/document/727419 | doi=10.1109/ICIP.1998.727419 | chapter=Parallel implementation of octtree generation algorithm | title=Proceedings 1998 International Conference on Image Processing. ICIP98 (Cat. No.98CB36269) | year=1998 | last1=Sojan Lal | first1=P. | last2=Unnikrishnan | first2=A. | last3=Poulose Jacob | first3=K. | volume=3 | pages=1005–1009 | isbn=0-8186-8821-1 | s2cid=195863788 }}
*[http://dblp.uni-trier.de/db/conf/viip/viip2001.html#LalUJ01 Generation of Octrees from Raster Scan with Reduced Information Loss, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, IASTED International conference VIIP 2001]  [http://www.actapress.com/catalogue2009/proc_series13.html#viip2001]{{dead link|date=February 2018 |bot=InternetArchiveBot |fix-attempted=yes }}
*[http://sc07.supercomputing.org/schedule/pdf/pap117.pdf Parallel Octrees for Finite Element Applications]
*[https://www.youtube.com/watch?v=Jw4VAgcWruY Video: Use of an octree in state estimation]
{{CS-Trees}}

[[Category:Trees (data structures)]]
[[Category:Computer graphics data structures]]
[[Category:Database index techniques]]