Práctica 3. Modelos Escalables de Colisión de Partículas
Esta práctica se centra en el tratamiento de colisiones que tienen lugar en la simulación de un sistema de partículas siguiendo dos tipos de modelo de colisión partícula-partícula y uno de partícula-plano.
Además, se tratará de mejorar el rendimiento de la simulación ante la escalabilidad de los sistemas, tratando de seguir distintas estrategias para poder simular un gran número de colisiones mediante la gestión de dos tipos de estructuras de datos: Grid y Hash. Estas estructuras son necesarias a partir de cierto número de partículas, ya que la comprobación de detección de colisiones es muy costosa en estos casos lo que hace imposible su correcta simulación.
Seguiremos tres estrategias principales para la unión de los nodos:
La simulación consistirá en un recipiente definido por varios planos (ver Figura 1) que formarán el fondo y las paredes del recipiente, sobre el que dejaremos caer una fuente de partículas.
Aplicaremos tres modelos de colisión:
-
Modelo de colisión partícula-plano
usando un modelo basado en la normal del plano, asumiendo un choque semielástico (se pierde un cierto porcentaje de energía en cada colisión).
-
Modelo de colisión partícula-partícula basado en velocidades
Con sus tres pasos: detección de la colisión, restitución a la posición previa a la colisión y cálculo de la velocidad de salida.
-
Modelo de colisión partícula-partícula basado en fuerzas elásticas
En este modelo se aplica una fuerza elástica repulsiva si las partículas se acercan demasiado, pero no se aplica una fuerza elástica atractiva si se separan (como ocurre en un muelle real).
El modelo más propio para simulación de colisiones es el basado en muelles. Por ello es el que más veremos en el vídeo de demostración.
Estructuras de Datos para Mejorar la Escalabilidad.
La estrategia de comprobación de fuerza bruta (“todas contras todas”) genera un coste de comprobación de colisiones de O(n^2) donde n es el número de partículas. Cuando n es muy grande, esta estrategia no es en nada adecuada.
Para mejorar la escalabilidad del sistema se pueden utilizar estructuras de datos para agrupar las partículas vecinas y estudiar las colisiones sólo en el entorno de cada partícula. Estos métodos, aunque llevan un coste asociado a la actualización de las estructuras de datos en cada frame, son más eficientes que la estrategia de fuerza bruta de “todas contra todas” si el número de partículas n es muy grande.
Estructuras de datos empleadas
-
Grid:
en esta estructura se sigue una estrategia de división del espacio en celdas. De esta manera una partícula se insertará en un o en otra celda dependiendo de su posición en el espacio. Controlando cuando una partícula entra y sale de una celda, resolveríamos el problema de la comprobación de colisión. Ahora únicamente comprobaremos con las partículas en las celdas vecinas y en la actual.
-
Hash:
Sigue la misma estrategia de división del espacio. Sin embargo difiere del método del Grid en la manera en la que se insertan las partículas en la estructura de datos. Para ello emplea números primos muy altos en lugar de números de celda.