Evaluación de Partículas Vecinas

Descripción del Problema: Se desea un algoritmo/estructura que permita la búsqueda de vecinos en “tiempo real”

Consideraciones: La solución planteada supone un escenario donde las partículas se encuentran en un espacio cartesiano XYZ,

Primera Evaluación (Evaluación Interna)

Evaluación Todos contra Todos, realizando la búsqueda de los vecinos dentro del mismo sector, evaluando para cada partícula si otra partícula se encuentra a una distancia L definida.

El almacenamiento de las partículas se realizan en una lista, sin ningún criterio en específico, por lo que para cada partícula en esta lista se evalúan las partículas que se encuentran después de la posición en la lista de la partícula evaluada, aprovechando que la distancia de una partícula a otra es la misma.

[Imagen de la búsqueda de las partículas en una lista]

Por lo que para evaluar las n partículas del sector se realizarán O(n^2) evaluaciones, esto solo involucra la evaluación de las partículas dentro del mismo sector.

En esta fase también se activan las banderas de cada partícula para evaluar los sectores definiendo su posición relativa para la partícula en un sector en particular.

[Poner imagen de los sectores de las partículas]

Para cada cubo dependiendo del octante en el se encuentra se revisan los cubos adyacentes y sólo aceptamos los que se encuentran a L/2 de distancia, con esto aseguramos que la mayoría de las conexiones se encuentran dentro del sector y solo es necesario realizar la búsqueda en la mitad de los sectores adyacentes, y no en todos los sectores vecinos, esto plantea un “problema” a las partículas vecinas no son lo la porción del planteamiento del problema conveniente los sectores y hacer solo búsqueda en subdivisiones de los sectores adyacentes.

• Propuesta de solución 1:

De la lista de las partículas para cada sector, se definen las subdivisiones de los sectores.sin embargo el problema de esta propuesta es que se requieren 8 espacios de memoria adicional para indicar donde inician las subdivisiones, lo cual si se desea implementar la búsqueda de vecinos con ayuda de tarjetas gráficas es un recurso que no se debe desperdiciar.

• Propuesta de Solución 2:

Se agrupa en un orden específico y se evalúa para cada partícula el sector al que pertenece, el problema sin embargo surge al evaluar las partículas ya que ocurren condiciones de carrera dentro de la GPU, si se desea revisar todas las partículas para cada thread ejecutado.

De la propuesta dos, podemos reducir el número colisiones si se revisa la mitad de las partículas considerando la forma en que se evalúan y agrupan las partículas en los sectores.

[Visualización de la reducción de evaluaciones para el caso 1D, 2D, y 3D]

Para el caso 3D se reducen la evaluación de sectores

#Algortimo #Estructura #Busqueda