Tree data structure in which each internal node has exactly eight children, to partition a 3D space
Octree
Type
Tree
Invented
1980
Invented by
Donald Meagher
Time complexity in big O notation
Operation
Average
Worst case
Search
O(logN+K)
O(logN+K)
Insert
O(logN)
O(logN)
Delete
O(logN)
O(logN)
Peek
O(logN)
O(logN)
Space complexity
Space
O(N)
O(N)
Left: Recursive subdivision of a cube into octants. Right: The corresponding octree.
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space 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 engines.
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional...
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...
linear octree is an octree that is represented by a linear array instead of a tree data structure. To simplify implementation, a linear octree is usually...
tree Min/max k-d tree Relaxed k-d tree Adaptive k-d tree Quadtree Octree Linear octree Z-order UB-tree R-tree R+ tree R* tree Hilbert R-tree X-tree Metric...
preassembled Cuboid forms of different sizes (from 1 unit up to 1024) according to octree model. The inspiration for 3D Slash came from kids playing Minecraft and...
neighbors (using FLANN) of a specific point or location. The pcl_octree library implements the octree hierarchical tree data structure for point cloud data. The...
pixel and so may be neglected. The use of hierarchical structures such as octree and BSP-tree could be very helpful for both compression of volume data and...
similarity queries on complex objects as compared using an arbitrary metric. Octree PH-tree Quadtree R-tree: Typically the preferred method for indexing spatial...
(hence the 'oct' in octree) until individual heightfield elements are reached is efficient and natural. A quadtree is simply a 2D octree. PHIGS was the first...
Computer, which led to the incorporation of Octree Software was released in 1986. From 1988 to 1992, Octree released several software packages including...
the geometry represented by voxels (instead of triangles) stored in an octree. Carmack claimed that this format would also be a more efficient way to...
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...
(PDF) on 2015-09-23. Cyril Crassin. "Voxel Cone Tracing and Sparse Voxel Octree for Real-time Global Illumination" (PDF). On-demand.gputechconf.com. Archived...
triangles, before the application of any structuring operation, such as e.g. octree grouping. The term must not to be confused with the "PolySoup" operation...
beveled. Dual contouring often uses surface generation that leverages octrees as an optimization to adapt the number of triangles in output to the complexity...
guide better object or primitive splitting. Binary space partitioning, octree, k-d tree R-tree, R+-tree, R*-tree and X-tree M-tree Sweep and prune Hierarchical...
containing the most points. A more modern popular method is clustering using octrees, first conceived by Gervautz and Purgathofer and improved by Xerox PARC...
meshes Parallel linear quadtree/octree with load balancing and 2:1 balancing (PABLO - PArallel Balanced Linear Octree) Basic container object for different...
acceleration techniques using spatial subdivision schemes such as Quadtrees or Octrees. These are also used to reduce the amount of main memory required at a...
Global Information