|
An octtree is a three-dimensional data structure that partitions space into axis-aligned boxes called voxels. Octtrees are adopted in various divide and conquer rendering strategies. Starting with a root voxel enclosing the region to be partitioned, voxels are partitioned by bisection in each dimension, generating a tree with eight branches at each node. Solutions to various problems are generally simpler within each branch, since that branch addresses contains only a sub-region of the origin voxel. The partitioning continues until some termination criteria are met, typically when the solution to a problem becomes trivial.
|