An octree is a
tree data structure
In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be c ...
in which each
internal node has exactly eight
children
A child ( : children) is a human being between the stages of birth and puberty, or between the developmental period of infancy and puberty. The legal definition of ''child'' generally refers to a minor, otherwise known as a person younger ...
. Octrees are most often used to partition a
three-dimensional space
Three-dimensional space (also: 3D space, 3-space or, rarely, tri-dimensional space) is a geometric setting in which three values (called ''parameters'') are required to determine the position of an element (i.e., point). This is the informa ...
by
recursively subdividing it into eight octants. Octrees are the three-dimensional analog of
quadtrees. The word is derived from ''oct'' (Greek root meaning "eight") + ''tree''. Octrees are often used in
3D graphics and 3D
game engine
A game engine is a software framework primarily designed for the development of video games and generally includes relevant libraries and support programs. The "engine" terminology is similar to the term "software engine" used in the software ...
s.
For spatial representation
Each node in an octree subdivides the space it represents into eight
octants. In a point region (PR) octree, the node stores an explicit
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, 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 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
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible a ...
the nodes are to be traversed and only required surfaces are to be viewed.
History
The use of octrees for
3D computer graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
was pioneered by Donald Meagher at
Rensselaer Polytechnic Institute
Rensselaer Polytechnic Institute () (RPI) is a private research university in Troy, New York, with an additional campus in Hartford, Connecticut. A third campus in Groton, Connecticut closed in 2018. RPI was established in 1824 by Stephen Van ...
, described in a 1980 report "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer", for which he holds a 1995 patent (with a 1984
priority date) "High-speed image generation of complex solid objects using octree encoding"
Common uses
*
Level of detail rendering in
3D computer graphics
3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
*
Spatial index
A spatial database is a general-purpose database (usually a relational database) that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data. Most s ...
ing
*
Nearest neighbor search
* Efficient
collision detection
Collision detection is the computational problem of detecting the intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing fields, primarily in computer grap ...
in three dimensions
*
View frustum culling
*
Fast multipole method
*
Unstructured grid
*
Finite element analysis
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
*
Sparse voxel octree
*
State estimation
*
Set estimation
Application to color quantization
The octree
color quantization
In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as v ...
algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because
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
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementat ...
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
function inDepths,binParents,binCorners,pointBins= OcTree(points)
binDepths = % Initialize an array of bin depths with this single base-level bin
binParents = % This base level bin is not a child of other bins
binCorners = in(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(pointBinsbinNo)
binEdgeLengths = binCorners(binNo,1:3) - binCorners(binNo,4:6)
binDepth = binDepths(binNo)
exitConditionsMet = binPointCountvalue
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) = ne of the 8 pairs of the newDiv with minCorner or maxCorner oldBinMask = pointBinsbinNo
% Calculate which points in pointBinsbinNo now belong in newBinNo
pointBins(newBinMask) = newBinNo
% Recursively divide this newly created bin
divide(newBinNo)
end
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.
[Bloomberg, Dan S]
"Color quantization using octrees."
4 September 2008. Retrieved on 12 December 2014.
% 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.PointBinsleafs(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)))
See also
*
Binary space partitioning
*
Bounding interval hierarchy A bounding interval hierarchy (BIH) is a partitioning data structure similar to that of bounding volume hierarchies or kd-trees. Bounding interval hierarchies can be used in high performance (or real-time) ray tracing and may be especially useful ...
* ''
Cube 2: Sauerbraten'', a 3D game engine in which geometry is almost entirely based on octrees
*
id Tech 6
id Tech 6 is a multiplatform game engine developed by id Software. It is the successor to id Tech 5 and was first used to create the 2016 video game '' Doom''. Internally, the development team also used the codename ''id Tech 666'' to refer to t ...
is a 3D game engine that utilizes voxels stored in octrees
*
Irrlicht Engine, supports octree scene nodes
*
Klee's measure problem
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of ( multidimensional) rectangular ranges can be computed. Here, a ''d''-dimensional rectangular range is defined to be a Cartes ...
*
Linear octree
*
OGRE, has an octree scene manager implementation
*
Subpaving
In mathematics, a subpaving is a set of nonoverlapping boxes of R⁺. A subset ''X'' of Rⁿ can be approximated by two subpavings ''X⁻'' and ''X⁺'' such that ''X⁻'' ⊂ ''X'' ⊂ ''X⁺''.
In R¹ the bo ...
*
Voxel
In 3D computer graphics, a voxel represents a value on a regular grid in three-dimensional space. As with pixels in a 2D bitmap, voxels themselves do not typically have their position (i.e. coordinates) explicitly encoded with their values. I ...
*
Quadtree
References
External links
Octree Quantization in Microsoft Systems JournalColor Quantization using Octrees in Dr. Dobb's*
tp://ftp.drdobbs.com/sourcecode/ddj/1996/9601.zip Color Quantization using Octrees in Dr. Dobb's Source Codebr>
Octree Color Quantization OverviewParallel implementation of octtree generation algorithm, P. Sojan Lal, A Unnikrishnan, K Poulose Jacob, ICIP 1997, IEEE Digital Library ttp://www.actapress.com/catalogue2009/proc_series13.html#viip2001*
ttp://sc07.supercomputing.org/schedule/pdf/pap117.pdf Parallel Octrees for Finite Element Applicationsbr>
Video: Use of an octree in state estimation{{CS-Trees
Trees (data structures)
Computer graphics data structures
Database index techniques