En las simulaciones físicas , el barrido y la poda son algoritmos de fase amplia que se utilizan durante la detección de colisiones para limitar la cantidad de pares de sólidos que se deben verificar para detectar colisiones , es decir, intersecciones. Esto se logra clasificando los inicios (límite inferior) y los finales (límite superior) del volumen delimitador de cada sólido a lo largo de una serie de ejes arbitrarios. A medida que los sólidos se mueven, sus inicios y finales pueden superponerse. Cuando los volúmenes delimitadores de dos sólidos se superponen en todos los ejes, se marcan para que se prueben con algoritmos más precisos y que requieren más tiempo.
El barrido y la poda aprovechan la coherencia temporal , ya que es probable que los sólidos no se muevan significativamente entre dos pasos de simulación. Por eso, en cada paso, las listas ordenadas de inicios y finales de volúmenes delimitadores se pueden actualizar con relativamente pocas operaciones computacionales. Los algoritmos de ordenamiento que son rápidos para ordenar listas casi ordenadas, como el ordenamiento por inserción , son particularmente buenos para este propósito.
Según el tipo de volumen delimitador utilizado, es necesario actualizar las dimensiones del volumen delimitador cada vez que se reorienta un sólido. Para evitar esto, se puede utilizar la coherencia temporal para calcular los cambios en la geometría del volumen delimitador con menos operaciones. Otro enfoque es utilizar esferas delimitadoras u otros volúmenes delimitadores independientes de la orientación.
El barrido y poda también se conoce como ordenación y barrido , [1] mencionado de esta manera en la tesis doctoral de David Baraff en 1992. [2] Trabajos posteriores como el artículo de 1995 sobre I-COLLIDE de Jonathan D. Cohen et al. [3] se refieren al algoritmo como barrido y poda .