Sistemas de particulas + octree

[pipu]

hola
estoy tratando de simular fluidos y tengo un sistemas de particula mi problemas es que por el metodo que esoty haciendo esto nececito savesr en todo momento quienes son las particuals vecinas a la particual que esoty analizando y para eso me sugerieron utilizar un octree pero nececito hacer un metodo que me diga la vecindad de las particulas que esten a una distancia h dela misma

alguna sugerencia????? :shock:

[Prompt]

http://en.wikipedia.org/wiki/Octree

Particionamiento binario. Siempre tienes el vecino y el padre.

Ya lo del radio h, pues te lo curras tu y haces una busqueda binaria para ver si está dentro de un radio r...

[pipu]

el problema no es hacer el octree por que ya lo tengo iplementado, el problema es hacer un metodo que me busque la becindad de las particulas, que recorra el arbol y me diga quien o quienes son veciones de la particula que estoy mirando en ese momento, este es el problema en si

gracias

[senior wapo]

Los vecinos están dentro de una esfera de centro tu partícula y radio la distancia que te interesa.

Mira que nodos/subespacios del octree intersectan dicha esfera y los que lo hagan contendrán posibles vecinos. Para cada uno de estos vecinos compara la distancia entre las partículas y la que te interesa.

Alternativamente, tal vez te convenga más usar un arbol tradicional y ordenar por códigos morton (googlea).

[pipu]

La idea que tengo es la siguiente:
El octree como todos sabemos se utiliza para la partición del espacio 3d ahora por ejemplo si tengo unos 100 000 polígonos en nuestro mundo, no podemos mandar a nuestra tarjeta grafica que nos pinte todos los polígonos en cada frame pues esto seria muy costoso y arruinaría nuestro programa y mas en mi caso que necesito que sea en tiempo real, ahora si subdividimos el espacio con un octree esto seria genial    
Pues la idea básica de este árbol seria primero se crea el octree, el cual va a envolver el mundo y se irá adaptando a él, lo que te dejará el espacio dividido en zonas de forma cúbica. Cada uno de estos cubos contiene a un máximo de otros 8 cubos de menor tamaño. Ahora que tenemos la herramienta creada, a la hora de pintar todo, vamos a mirar si un cubo está en el área de visión (un test simple y rápido); si no lo está, no necesitamos probar a sus hijos, ya que no estarán dentro; si está dentro probaremos si sus hijos están dentro del área, y así recursivamente
Lo que en esta caso en ves de polígonos tenemos un sistema de partícula en el cual la idea básicamente es la misma, subdividir el espacios hasta que me queden una X  cantidad de partículas vecinas en los cubos (los cubos serán de 2h que es la distancia que necesito para la vecindad de las partículas) y así solo tenia que ver los cubos vecinos para ver que no se me quede ninguna partícula vecina.
Ahora como esto es un fluido (sangre por ejemplo) que va estar en un espacio dado (un cubo, un baso, etc.) las partículas van a estar en constante movimiento y tengo que actualizar en todo momento el octree pues las partículas van a cambiar de vecino  y esto se me hace muy costoso.
De todas formas pienso probar esto pero si alguien tiene otra idea por favor seria bienvenida.
Gracias por sus ideas son siempre de gran ayuda    
:roll:

[Prompt]

Si es que te lo estamos diciendo pipu! :)

Recorre el arbol, si quieres previamente ordenalo o haz una busqueda con poda, y haces mira si en un radio R (una esfera de centro la particula que quieras) quien está dentro.

Gugléa! :D

[nostromo]

Utiliza un grid para las partículas, si están confinadas en un espacio pequeño.... en fin, esto depende de lo que quieras hacer
El grid es muy fácil de actualizar y también es fácil listar las partículas vecinas; te quitará el problema de actualizar el octree....
Luego integra el grid con el mundo, mete el grid en un objeto contenedor(que no sea visible) y este contenedor en el octree del mundo.... esto hará que puedas eliminar el grid del proceso si no esta visible.

Lo malo es que el grid ocupa espacio... en fin, como he dicho antes depende de lo que quieras hacer

Un saludo

[pipu]

Hola esta idea me parece genial lo ke no tengo mucha experiencia con esto del grid
¿Me puedes explicar más sobre este tema??    
Ah lo ke quiero hacer es simular fluido en tiempo real y que la simulación visual sea lo mas real posible, esto es un poco complicado, para la simulación física estoy usando un método matemático que se llama Hidrodinámica de las Partículas Suavizadas (SPH), este método es muy eficiente (libre de mayas) y fácil de implementar el mayor problemas es este, el de la búsqueda de vecinos de las partículas.
Bueno en fin si puedes explícame un poquito mas sobe este tema del grid que de veras no estoy muy empapado en el
Gracias por sus ideas son de gran ayuda.
:roll:

[nostromo]

Claro, te explico...

Un grid se basa en lo mismo que el octree, dividir el espacio en cubos. Pero sin usar un arbol, sino que se usa una matriz tridimensional donde cada elemento es un cubo y todos los cubos tienen el mismo tamaño. Cada cubo del grid es una lista de objetos(particulas en este caso) De ahi que ocupe más espacio que un octree.

Supongo que las particulas estan uniformemente distribuidas en el espacio porque sino no te solucionaría el problema,
Te explico como iria el tema.... aunque creo que entendiendo que es el grid ya sabrás por donde voy.

Supongamos que las particulas tienen coordenadas (x,y,z) donde tanto x,y,z están en el rango 0 a 127. El grid tiene longitud total de 128 y longitud de una arista del cubo(elemento del grid) de 16.
Con estos datos tenemos 8 x 8 x 8 = 512 cubos en el grid, donde 8= 128/16  

Digamos que el indice de cada cubo es (i,j,k). Lo sencillo es calcular a que cubo pertenece cada particula.
Seria i = x / 16 , j = y /16 y k= z / 16

Para actualizar una particula:
Calculamos a que cubo pertenecía según la antigua posicion de la particula y lo borramos de la lista de ese cubo, calculamos el nuevo cubo donde ira la particula y lo añadimos a su lista.

Ver las particulas vecinas es muy sencillo... digamos que la particula esta en el cubo (i,j,k)... pues vamos mirando las particulas de ese cubo y de los vecinos que necesitemos(i-1,j,k),(i+1,j,k) etc... incluso puede que la vecindad que necesites este en el mismo cubo de la particulas.

La lista de cubos puede ser un vector de 512 elementos y su indice (i+j*16+k*16*16) y si las dimensiones son multiplos de 2 los calculos se pueden simplificar mucho y ser mucho más rapidos.

Desventajas:
- Puede ocupar mucho espacio
- No es adaptativo. Si las particulas se acumulan en pocos cubos del grid tenemos un problema O(n^2) que es lo que quieres evitar.

[pipu]

Hola nostromo:
Gracias por contestar a este tema, me ha servido de mucha ayuda ahora solo tengo que estudiar un poquito más sobre el grid e implementar, cuando termine te diré como quedo todo.

Bueno espero alguna otra propiciación sobre este tema que esta un poco interesante  anímense!!!!!!!!!
graciasss
:roll:

[pipu]

Hola:
Como había dicho antes estoy implementando una aplicación que simula fluido y para la simulación física estoy haciéndolo con un método que se llama hidrodinámica de las partículas suavizadas (SPH por su nombre en ingles) pero tengo algunos problemas a la hora de implementar algunas de sus ecuaciones matemáticas, si alguien ha trabajado con este método por favor que me responda es muy importante  

 :roll:  :(


Gracias por su ayuda

[pipu]

Hola:
Como había dicho antes estoy implementando una aplicación que simula fluido y para la simulación física estoy haciéndolo con un método que se llama hidrodinámica de las partículas suavizadas (SPH por su nombre en ingles) pero tengo algunos problemas a la hora de implementar algunas de sus ecuaciones matemáticas, si alguien ha trabajado con este método por favor que me responda es muy importante  

 :roll:  :(



Gracias por su ayuda