Rumsindelning
Att dela in rummet i regioner så att en fråga bara undersöker närliggande objekt i stället för alla.
Att testa varje objekt mot varje annat är O(n²) — dugligt för tio objekt, förödande för tiotusen. Rumsindelning indexerar objekt efter var de befinner sig, så att en kollisions- eller synlighetsfråga bara rör cellerna nära den punkt man frågar om.
Strukturerna skiljer sig i hur de skär rummet: ett likformigt rutnät delar det i lika celler, en quadtree eller octree delar rekursivt där objekten klumpar ihop sig, ett BSP-träd skär längs godtyckliga plan. Alla byter minne och uppdateringskostnad mot vida billigare frågor, och alla ligger bakom kollisionens broad-phase och frustum culling.