Sweep and prune
Un algoritmo di fase larga che ordina i bounding box degli oggetti lungo ogni asse e verifica solo le coppie i cui intervalli si sovrappongono su tutti gli assi.
Confrontare ogni oggetto con tutti gli altri costa O(n²) ed è impensabile con migliaia di corpi. Lo sweep and prune (detto anche «sort and sweep») proietta l'inizio e la fine di ogni bounding box sugli assi x, y e z, ordina le liste e le scorre: due box possono collidere solo se i loro intervalli si sovrappongono su tutti gli assi. Tutto il resto viene scartato subito.
Il trucco è la coerenza temporale: tra un frame e l'altro gli oggetti si spostano di poco, quindi le liste ordinate sono già quasi in ordine e un insertion sort gira in tempo quasi lineare. Il metodo nasce dalla libreria I-COLLIDE di Ming Lin e Dinesh Manocha, dei primi anni Novanta, e compare in praticamente ogni motore fisico come economico primo passaggio prima della costosa fase esatta.