Octree Algorithm

An octree is a tree data structure in which every internal node has exactly eight children, serving as the three-dimensional counterpart to the quadtree by recursively partitioning space into eight octants. Donald Meagher developed its application to three-dimensional computer graphics at Rensselaer Polytechnic Institute, describing the technique in a 1980 report titled Octree Encoding, A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer, and later receiving a patent on the method. Depending on the variant, an octree either stores an explicit three-dimensional point at each node marking the center of its subdivision or, in a matrix-based form, implicitly subdivides around the center of the region itself, and the structure is widely used for level-of-detail rendering, spatial indexing, nearest-neighbor search, collision detection and view-frustum culling in three-dimensional graphics and game engines.