Modeloa de colisión entre partículas y estructuras de datos

El objetivo de la práctica es simular, visualizar y analizar los diferentes modelos de colisión de entre partículas y las estructuras de datos.
Vamos a trabajar en 2D, y con las partículas dentro de un "cubo" por lo que también vamos a tener implementado un modelo de colisión partícula - plano, muy similar al modelo de colisión de las velocidades de salida explicado en el ejercicio 4 del tema 2, solo que en lugar de tener la posición del centro de una segunda partícula tenemos un punto del plano y la normal de éste como dirección.

Analizando los modelos implementados en el ejercicio 4 del tema, podemos ver que visualmente el modelo de las velocidades de salida nos da unos resultados visuales mejores que el modelo del muelle, por lo que para la realización de la práctica usaremos el modelo de colisión entre partículas de las velocidades de salida. A esto también hay que sumarle, que los resultado de la comparativa fps vs número de partículas es mejor en este modelo también pues acepta más partículas para 30 fps que son los que nos interesará mantener en la simulación de algún videojuego.

Las estructuras de datos que vamos a usar van a ser tabla GRID y tabla HASH. El uso de esto modelos nos va a permitir reducir el número de partículas con las que se va a calcular una posible colisión cada vez, pues sin una estructura de datos, se calcula una hipotética colisión con todas las partículas que haya en la escena, mientras que con las estructura de datos comprobaremos sólo algunas de las celdas vecinas, dejando todas las partículas fuera de la propia celda de la partícula que estamos comprabando o sus vecinas, ahorrando un gran número de compraciones siempre que seleccionemos de forma correcta el tamaño de las celdas de la estructura.
No ha de ser muy grande pues perderíamos los beneficios de la estructura de datos ya que con pocas celdas cubriríamos toda la escena y habr&iacuta;a que comprobar todas las celdas. Si son muy pequeñas puede que no quepa ni una partícula y tampoco nos beneficia nada.

GRID.
Es la estructura más básica. El tamaño viene definido por el número de celdas que hay, es decir, si definimos un tamaño de celda de 50x50 y nuestra área de trabajo es de 200x250, el tamaño de la estructura interna que representará al grid, (ArrayList) será 200/50 * 250/50.

TABLA HASH
Esta estructura es dinámica, ya que su tamaño depende del número de elementos que se vayan a almacenar, concretamente el doble de estos. En este caso el tamaño de la celda no nos servirá para la representación visual del la regilla por detrás de la zona de trabajo, pero sí que no sirve a la hora de calcular el índice de la celda en la que se encuentra la partícula con la función de dispersión.
La función de dispersión del Hash nos devolverá el índice de la "celda" en la que se encuentra la partícula con la que vayamos a trabajar. La función de dispersión que usamos en la prán que usamos es:

xd = (int)floor(posicion.x/cs)
yd = (int)floor(posicion.y/cs)
zd = (int)floor(posicion.z/cs)
celda = (73856093 * xd + 19349663 * yd + 83492791 * zd) % numero_elementos

Los resultados que obtenemos tanto con una estructura como con la otra son mejores que los que obtenemos sin usar estas estructuras de datos. Retomando lo hablado antes, del tamaño de celda adecuado, hemos realizado pruebas con diferentes tamaños de celda y diferentes radios en las partículas. Los mejores resultados se obtienen contra más ajustado es el tamaño de la celda. La diferencia entre radio 10, tama&ntile;o de celda 50 y radio 5, tamaño de celda 25 es de 700 partículas más.