Sweep and prune
Un algoritmo de fase amplia que ordena las cajas envolventes de los objetos a lo largo de cada eje y solo prueba los pares cuyos intervalos se solapan en todos los ejes.
Probar cada objeto contra todos los demás es O(n²) y resulta inviable con miles de cuerpos. Sweep and prune (también "sort and sweep") proyecta el punto inicial y final de cada caja envolvente sobre los ejes x, y y z, ordena las listas y las recorre; dos cajas solo pueden chocar si sus intervalos se solapan en todos los ejes. El resto se descarta de inmediato.
El truco es la coherencia temporal — los objetos se mueven poco entre fotogramas, así que las listas ordenadas ya están casi ordenadas y una ordenación por inserción corre casi lineal. El método salió de la biblioteca I-COLLIDE de Ming Lin y Dinesh Manocha a principios de los años noventa y está en prácticamente todo motor de física como un primer filtro barato antes de la fase exacta y costosa.