Podział przestrzeni
Dzielenie przestrzeni na regiony, tak by zapytanie sprawdzało tylko pobliskie obiekty zamiast wszystkich.
Testowanie każdego obiektu z każdym innym ma złożoność O(n²) — dla dziesięciu obiektów w porządku, dla dziesięciu tysięcy zabójcze. Podział przestrzeni indeksuje obiekty według położenia, więc zapytanie o kolizję lub widoczność dotyka tylko komórek w pobliżu punktu, o który pytasz.
Struktury różnią się sposobem cięcia: jednorodna siatka dzieli przestrzeń na równe komórki, quadtree lub octree dzielą rekurencyjnie tam, gdzie obiekty się skupiają, a drzewo BSP tnie dowolnymi płaszczyznami. Wszystkie wymieniają pamięć i koszt aktualizacji na znacznie tańsze zapytania i wszystkie stoją za fazą wstępną wykrywania kolizji oraz za odrzucaniem niewidocznych obiektów względem frustum.