Partición espacial
Dividir el espacio en regiones para que una consulta examine solo los objetos cercanos en lugar de todos.
Probar cada objeto contra todos los demás es O(n²) — pasable con diez objetos, ruinoso con diez mil. La partición espacial indexa los objetos según dónde están, de modo que una consulta de colisión o visibilidad toca solo las celdas cercanas al punto por el que se pregunta.
Las estructuras difieren en cómo cortan el espacio: una rejilla uniforme lo divide en celdas iguales, un quadtree u octree subdivide de forma recursiva donde se agrupan los objetos, un árbol BSP corta a lo largo de planos arbitrarios. Todas cambian memoria y coste de actualización por consultas mucho más baratas, y todas sostienen la fase amplia de la detección de colisiones y el frustum culling.