Sweep and prune
Een broad-phase-algoritme dat de bounding boxes van objecten langs elke as sorteert en alleen paren test waarvan de intervallen op alle assen overlappen.
Elk object met elk ander object testen is O(n²) en kansloos bij duizenden lichamen. Sweep and prune (ook "sort and sweep") projecteert het begin- en eindpunt van elke bounding box op de x-, y- en z-as, sorteert de lijsten en loopt ze door. Twee boxen kunnen alleen botsen als hun intervallen op alle assen overlappen. Al het andere wordt in één keer weggesnoeid.
De truc is temporele coherentie: objecten bewegen tussen frames maar weinig, dus de gesorteerde lijsten zijn al bijna gesorteerd en een insertion sort draait vrijwel lineair. De methode komt uit de bibliotheek I-COLLIDE van Ming Lin en Dinesh Manocha, begin jaren negentig, en zit in vrijwel elke physics-engine als goedkope eerste ronde vóór de dure exacte fase.