Partizionamento spaziale
Dividere lo spazio in regioni in modo che una query esamini solo gli oggetti vicini anziché tutti.
Confrontare ogni oggetto con tutti gli altri costa O(n²): va bene per dieci oggetti, è rovinoso per diecimila. Il partizionamento spaziale indicizza gli oggetti in base alla posizione, così che una query di collisione o di visibilità tocchi solo le celle vicine al punto interrogato.
Le strutture differiscono nel modo di tagliare lo spazio: una griglia uniforme lo divide in celle uguali, un quadtree o un octree lo suddivide ricorsivamente dove gli oggetti si addensano, un albero BSP lo taglia lungo piani arbitrari. Tutte scambiano memoria e costo di aggiornamento con query molto più economiche, e tutte stanno dietro la fase larga del rilevamento delle collisioni e del culling del frustum di vista.