Octree
|
|
An octree is a tree data structure mainly used for organising 3-dimensional space. Each node of the octree represents a cuboid volume. Each node has 8 children, hence oct+tree = octree. The 8 child nodes can partition the same volume of space as the parent node. This heirarchical organizing of 3D space can be useful for a number of problems relating to queries about regions in space. In particular, visibility algorithms used in computer graphics will use octrees to exclude large regions of a rendered scene from consideration simply by determining that a higher octree node lies completely outside the viewing volume, therefore, there is no need to render anything that lies in that cube, and, consequently, any of its constituant smaller cubes.