![Octree2](https://upload.wikimedia.org/wikipedia/commons/2/20/Octree2.svg)
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 conn ...
in which each
internal node
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 con ...
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 (geometry), position of an element (i.e., Point (m ...
by
recursively subdividing it into eight octants. Octrees are the three-dimensional analog of
quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four q ...
s. The word is derived from ''oct'' (Greek root meaning "eight") + ''tree''. Octrees are often used in
3D 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 the ...
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 i ...
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 alon ...
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
Priority date is a United States immigration concept – it is the date when a principal applicant first reveals his or her intent of immigration to the US government. For family-sponsored applicants, the priority date is the date an immigration ...
) "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 sp ...
ing
*
Nearest neighbor search
Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function ...
* Efficient
collision detection
Collision detection is the computational problem of detecting the intersection (Euclidean geometry), intersection of two or more objects. Collision detection is a classic issue of computational geometry and has applications in various computing ...
in three dimensions
*
View frustum culling
In 3D computer graphics, hidden-surface determination (also known as shown-surface determination, hidden-surface removal (HSR), occlusion culling (OC) or visible-surface determination (VSD)) is the process of identifying what surfaces and parts o ...
*
Fast multipole method __NOTOC__
The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the ''n''-body problem. It does this by expanding the system Green's function using a multipole expansion, ...
*
Unstructured grid
An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis w ...
*
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
A sparse voxel octree (SVO) is a 3D computer graphics rendering technique using a raycasting or sometimes a ray tracing approach into an octree data representation.
The technique generally relies on generating and processing the hull of points ( ...
*
State estimation In control theory, a state observer or state estimator is a system that provides an estimate of the internal state of a given real system, from measurements of the input and output of the real system. It is typically computer-implemented, and pro ...
*
Set estimation
In statistics, a random vector ''x'' is classically represented by a probability density function.
In a set-membership approach or set estimation, ''x'' is represented by a set ''X'' to which ''x'' is assumed to belong. This means that the suppor ...
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
The RGB color model is an additive color model in which the red, green and blue primary colors of light are added together in various ways to reproduce a broad array of colors. The name of the model comes from the initials of the three addi ...
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, implementation ...
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)
IN, In or in may refer to:
Places
* India (country code IN)
* Indiana, United States (postal code IN)
* Ingolstadt, Germany (license plate code IN)
* In, Russia, a town in the Jewish Autonomous Oblast
Businesses and organizations
* Independ ...
% 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
NE, Ne or ne may refer to:
Arts and entertainment
* Neutral Evil, an alignment in the American role-playing game ''Dungeons & Dragons''
* New Edition, an American vocal group
* Nicomachean Ethics, a collection of ten books by Greek philosopher A ...
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
In computer science, binary space partitioning (BSP) is a method for space partitioning which recursively subdivides a Euclidean space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to a represent ...
*
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 ...
is a 3D game engine that utilizes voxels stored in octrees
*
Irrlicht Engine
Irrlicht (pronounced in German) is an open-source game engine written in C++. It is cross-platform, officially running on Windows, macOS, Linux and Windows CE and due to its open nature ports to other systems are available, including FreeBSD, X ...
, 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 Cart ...
*
Linear octree
*
OGRE
An ogre ( feminine: ogress) is a legendary monster depicted as a large, hideous, man-like being that eats ordinary human beings, especially infants and children. Ogres frequently feature in mythology, folklore, and fiction throughout the wor ...
, 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 box ...
*
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. Ins ...
*
Quadtree
A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four q ...
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