Algoritmo de detección de colisiones de objetos volumétricos basado en el modelo de visualización y manipulación de volúmenes EVM

Abstract

El modelo de los vértices extremos es un modelo orientado a la visualización y manipulación de datos volumétricos que proporciona un conjunto aceptable de operaciones de edición, de análisis y morfológicas, sin embargo, no contaba con una operación para la detección de colisiones, la cual es fundamental para las aplicaciones que necesitan realizar un análisis de contacto entre objetos estáticos o en movimiento. En vista de la importancia de la detección de colisiones en cualquier modelo que permita la visualización y manipulación de datos volumétricos, se desarrolló un algoritmo de detección de colisiones el cual complementa el conjunto de operaciones del modelo de los vértices extremos. El diseño se hizo en base al algoritmo para las operaciones booleanas regularizadas, particularmente orientado a la operación de intersección, la cual permite verificar si dos objetos colisionan, pero requiere gran cantidad de tiempo de cómputo, lo cual la hace ineficiente. La implementación del algoritmo fue realizada tomando en cuenta dos estructuras de datos distintas (ABCSorted y Trie-Trie), sobre las cuales fueron realizadas las pruebas. Las pruebas realizadas revelaron que el algoritmo desarrollado es mejor que la operación de intersección para la detección de colisiones, desde un 74% para objetos pequeños, hasta un 82% para objetos grandes. Asimismo, las pruebas revelaron que el algoritmo presenta un mejor comportamiento sobre la estructura ABC-Sorted. Por otro lado también se demuestra que el algoritmo de detección de colisiones permite utilizar el EVM como volumen envolvente multiresolución y así disminuir los falsos positivos.

Palabras clave: Algoritmo de detección de colisiones, modelo de los vértices extremos, EVM.