Spatial Partitioning
A ray-tracing intersection [see page 25, optimisation-technique] which divides the world into a grid and associates each object with the cells of the grid the object contains. We then find which cells a ray passes through and then only test objects whose cells overlap with the rays cells.
The efficiency and reliability of this approach depends of the resolution of the grid we create.
Space partitioning isn't limited to regular grids (with [see page 26, voxels]), it can also use:
- [see page 27, octree]s which divides the grid into 4s and remembers each object in each division. It then divides each sub-grid into 4s once again recursively until every grid cell is associated with at most 1 object. We then trace the ray through the grid and check for collisions against each leaf cells object which the ray had intersected.
- [see page 28, Binary space partitioning] incrementally divides the grid into partitions again and again (storing as a binary tree) until each object is in it's own partition. We then repeat the same process as octrees. The main concern here is keeping the binary tree balanced.