Clasificación y comparación de métodos de detección de colisiones de fase amplia para imágenes sintéticas en 2D+tiempo

Abstract

La detección de colisiones ha sido un tópico de extenso estudio en computación gráfica y geometría computacional. Sus campos de aplicación incluyen la robótica, biología computacional, juegos, y simulaciones en cirugía, física y biología. Un entorno real complejo para la detección de colisiones corresponde a imágenes biomédicas y astronómicas: imágenes en series de tiempo, de gran tamaño, a veces con gran cantidad de objetos, que se mueven y se deforman, y que pueden aparecer o desaparecer de la escena, o experimentar autocolisiones, aspectos que pueden hacer la detección de colisiones un trabajo demasiado lento de calcular sin las estrategias apropiadas. Este trabajo realiza un contraste entre dos enfoques de detección de colisiones de fase amplia en 2D+tiempo: usando los métodos estáticos sweep and prune directo, que funcionan cuadro a cuadro, y el método sweep and prune incremental, que mantiene las estructuras a lo largo de la simulación, contra el enfoque cinético del algoritmo sweep and prune cinético. Ambos enfoques fueron probados en simulaciones de objetos con movimiento rectilíneo en direcciones aleatorias. La comparación se hizo siguiendo los lineamientos de experimentación en algoritmos establecidos por Moret [26] respecto a qué parámetros es pertinente medir, las diez sugerencias de Johnson [22] para realizar un experimento con algoritmos y las sugerencias de Sanders [31] para mostrar los resultados en forma de gráficos. Los resultados muestran que el uso del algoritmo sweep and prune cinético es un orden de magnitud más rápido que los algoritmos sweep and prune estáticos en simulaciones que involucran una distribución aleatoria de objetos en movimiento, sin importar la densidad de objetos en la simulación. También se estudia el efecto de colisiones múltiples dentro de las simulaciones, un suceso que no fue investigado por Coming & Staad [11]. Esto permite hacer sugerencias sobre las instancias en las que un algoritmo es más apropiado que otro.