Tesis para optar al grado de Magíster en Ciencias, Mención Computación / 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.
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/170930 |
| Date | January 2019 |
| Creators | Moraga Aros, Héctor Marcelo |
| Contributors | Hitschfeld Kahler, Nancy, Bustos Cárdenas, Benjamín, Inostroza Fajardin, Patricio, Rannou Fuentes, Fernando |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.007 seconds