Ruimtelijke partitionering
De ruimte in gebieden opdelen, zodat een query alleen objecten in de buurt bekijkt in plaats van alle.
Elk object tegen elk ander object testen kost O(n²) — prima voor tien objecten, desastreus voor tienduizend. Ruimtelijke partitionering indexeert objecten op hun positie, zodat een botsings- of zichtbaarheidsquery alleen de cellen raakt die dicht bij het gevraagde punt liggen.
De structuren verschillen in hoe ze de ruimte snijden: een uniform raster verdeelt haar in gelijke cellen, een quadtree of octree onderverdeelt recursief waar objecten zich concentreren, een BSP-boom snijdt langs willekeurige vlakken. Allemaal ruilen ze geheugen en updatekosten in voor veel goedkopere queries, en allemaal vormen ze de basis van de broad phase van botsingsdetectie en view-frustum culling.