Octree
Un albero che suddivide ripetutamente lo spazio 3D in otto cubi, così da verificare solo gli oggetti che si trovano davvero vicini.
Ogni nodo è un cubo con otto figli, uno per ottante. Gli oggetti finiscono nel cubo più piccolo che li contiene e una query su una regione deve visitare soltanto i cubi che la intersecano. La profondità si adatta alla densità: le zone vuote del mondo restano poco profonde.
La struttura è alla base della broad-phase delle collisioni, del frustum culling e della memorizzazione di voxel (come nei mondi in stile Minecraft) e nuvole di punti. La controparte bidimensionale è il quadtree; scegliere tra i due dipende solo da quanti assi occorre dividere.