En las simulaciones físicas , el barrido y la poda es un algoritmo de fase amplio que se utiliza durante la detección de colisiones para limitar el número de pares de sólidos que deben comprobarse en busca de colisión , es decir, intersección. Esto se logra ordenando los inicios (límite inferior) y los extremos (límite superior) del volumen delimitador de cada sólido a lo largo de varios 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 ser probados por algoritmos más precisos y que requieren más tiempo.
Barrer y podar explota 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 los inicios y finales del volumen delimitador se pueden actualizar con relativamente pocas operaciones computacionales. Los algoritmos de clasificación que son rápidos para clasificar listas casi ordenadas, como el ordenamiento por inserción , son particularmente buenos para este propósito.
De acuerdo con 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, la coherencia temporal se puede utilizar para calcular los cambios en la geometría del volumen delimitador con menos operaciones. Otro enfoque consiste en utilizar esferas delimitadoras u otros volúmenes delimitadores independientes de la orientación.
Barrer y podar también se conoce como ordenar y barrer , [1] referido 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 barrer y podar .
Ver también
Referencias
- ^ Ericson, Christer (2005), Detección de colisiones en tiempo real , serie Morgan Kaufmann en tecnología interactiva 3D, Amsterdam: Elsevier, págs. 329–338, ISBN 978-1-55860-732-3
- ^ Baraff, D. (1992), Simulación dinámica de cuerpos rígidos no penetrantes, (tesis doctoral) , Departamento de Ciencias de la Computación, Universidad de Cornell, págs. 52–56
- ^ Cohen, Jonathan D .; Lin, Ming C .; Manocha; Ponamgi, Madhav K. (9 al 12 de abril de 1995), I – COLLIDE: an Interactive and Exact Collision Detection System for Large Scale Environments) (PDF) , Actas del Simposio de 1995 sobre gráficos interactivos en 3D (Monterey, CA), págs. 189-196