Sweep And Prune ( rus. find and trim ) es el nombre de un algoritmo en simulaciones de física que se usa en problemas de detección de colisiones para reducir la cantidad de pares de cuerpos sólidos ( ing. solid ) que deben verificarse para una colisión, que es, para una intersección. Por lo tanto, Sweep And Prune es un algoritmo de optimización . El algoritmo Sweep And Prune ordena los inicios (límite superior) y los extremos (límite inferior) del volumen Bounding para cada cuerpo a lo largo de muchos ejes arbitrarios. Cuando dos cuerpos se mueven, sus comienzos y finales pueden superponerse. Si los volúmenes delimitadores de dos cuerpos se superponen a lo largo de todos los ejes, estos cuerpos se marcan para comprobar la intersección mediante algoritmos más precisos y que consumen más tiempo.
El algoritmo Sweep And Prune explota la coherencia temporal , ya que existe una alta probabilidad de que los cuerpos no se muevan una distancia significativa durante un paso de simulación. Debido a esto, en cada paso de la simulación, la lista ordenada de volúmenes límite iniciales y finales se puede actualizar con relativamente pocas operaciones computacionales.
Según el tipo de volumen delimitador utilizado, es necesario actualizar las dimensiones del volumen delimitador cada vez que se reorienta el cuerpo. Para eludir esto, se puede utilizar la coherencia temporal para calcular los cambios en la geometría del volumen computacional, lo que requiere menos operaciones. Otro enfoque consiste en utilizar esferas delimitadoras como volúmenes delimitadores .
El algoritmo Sweep And Prune también se conoce como ordenar y barrer, [1] y fue proporcionado por David Baraff Ph . D en su artículo de 1992 [2] . Trabajos posteriores como "I-COLLIDE" de Cowan y otros se refieren al algoritmo como "Sweep And Prune". [3]