neighbor search for smooth particle hydrodynamics

Community Forums/Showcase/neighbor search for smooth particle hydrodynamics

Nate the Great(Posted 2010) [#1]
well I worked on this a while. It will hopefully be the base of the physics in my future fluid based games. This has much more realistic fluid physics than before but the most important thing is the neighbor search algorithm. It is optimized very well and can handle 10,000 particles for me on a single core 2.4 ghz at 20-30 fps. I compiled it so it shows the console because that is where the statistics are output on number of particles and efficiency of the search algorithm. It guesses a neighbor correctly 93 to 94 percent of the time which is very good compared to the .024 % guess rate of a brute force algorithm with 3000 particles and the previously 34% guess rate of the grid algorithm. Also it is not multithreaded but I plan to tinker with that so maybe I can make it even faster for you multicore users. As for its use in games, it will run at a decent speed with well over 10,000 particles in a game environment where there are multiple bodies of fluid and not just one because it speeds up the search significantly. It is a big unstable with too much compression and some random particles go flying but I am working on fixing that at the moment.

Download it here:

http://naillproductions.synthasite.com/resources/SPH%20neighbor%20search.zip

a adds particles
space displays statistics
left/right click manipulate the fluid


Danny(Posted 2010) [#2]
Wow, impressive stuff!


Serpent(Posted 2010) [#3]
very nicely done.


Noobody(Posted 2010) [#4]
What exactly do you mean with 'guess a neighbour correctly'? Do you mean neighbours that contribute to the particle forces?

This does sound interesting, since the 34% of the grid method are correct - it's the area of a circle with radius smoothing length divided by the area of a 3*smoothing length square. But on the other hand, the grid method is very efficient considering it's administration cost (filling the grid is very fast, iterating it even faster). How exactly does your method work? I'd like to test it in the SPH code of mine to see how it behaves. 95% sounds promising :)

As for your fluid, it behaves a bit wierd. It tends to build blobs that grow out of the surface and seems to have no damping, considering the tall splashes at the walls. What SPH approach did you use?


ImaginaryHuman(Posted 2010) [#5]
It's pretty sweet, nice and quick, good fluid simulation :-D

Are you using vertex arrays for your rendering yet?


Stevie G(Posted 2010) [#6]
Excellent.


Nate the Great(Posted 2010) [#7]
thanks everybody & noobody haha..

Are you using vertex arrays for your rendering yet?


no, I am using gl points but they are all rendered in the same glbegin and glend so I assume they are one 'texture'? someone on the gl forum said that is the fastest way to render 10,000 or more points...

What exactly do you mean with 'guess a neighbour correctly'? Do you mean neighbours that contribute to the particle forces?


yep, it gives a 'best guess' to the nieghbors that contribute to particle forces

This does sound interesting, since the 34% of the grid method are correct - it's the area of a circle with radius smoothing length divided by the area of a 3*smoothing length square. But on the other hand, the grid method is very efficient considering it's administration cost (filling the grid is very fast, iterating it even faster). How exactly does your method work? I'd like to test it in the SPH code of mine to see how it behaves. 95% sounds promising :)


yeah its kinda confusing, its basicly a modified grid and its not very oo looking at the moment, It is interesting how you can easily trade the accuracy for more speed but if you trade too much it explodes. I am working on making it a simple variable called accuracy that you can change but for now its 3 seperate variables


As for your fluid, it behaves a bit wierd. It tends to build blobs that grow out of the surface and seems to have no damping, considering the tall splashes at the walls. What SPH approach did you use?


it is normal sph, unfortunately the neighbor search misses some particles right now, I can easily change the variables so it is 100% accurate at finding all neighbors and misses 34% of the time but that means its not as fast (its still fast enough to use in a game though). About half way between the accuracy of what I put up for download and the accuracy of a standard grid the difference is almost impossible to tell and the grid is much harder to see.

It is going to be great for games but since it misses some neighbors (depending on how accurate it is) it is not good to create simulations for careful analysis from sph experts ;) I might be able to clean it up and post the code in a week or so but I am on vacation right now so pardon my lazyness. :)

edit oops percents are calculated wrong thats ironic...

x = missed guesses per particle
y = neighbors per particle

it shows (1-x/y)*100

it should be (1-x/(y+x))*100

so that means it misses 94 percent of the time, not 93 haha.. it makes a big difference for lower percentages though.


Nate the Great(Posted 2010) [#8]
ok here is how it works, it was too hard to explain clearly so I drew some pictures in ms paint :)

key-
black lines = grid cell
red dot = particle
blue radius = radius of support
green radius = 2* blue radius
blue dot = cell that is considered neighboring

here is how a normal grid works:
each particle in each grid cell is tested for collisions with particles in its grid cell and particles in neighboring grid cells like this


I decided it would be better to divide the grid up more and save some calculations by only calculating the grids in a rough circle around the center grid cell, this is slightly inaccurate because as you can see there are places where particles can be missed but there are also places where particles can be considered that are not really options...


Then I decided to sacrifice another level of accuracy for fewer 'misses' but more particles not considered, this leads to worse grid artifacts and is what is in the download above. So a few particles are missed for speed but I am not sure if I want to use this method which can easily be scaled to be more or less accurate or the above method which takes a little more cpu time or the normal grid method which is the slowest.


Its nothing ground breaking or special but its fun to see that many particles not to mention I need that many for my game ideas and when your playing a game it is much harder to notice grid artifacts and odd clumping when the fluids are in constant motion so I believe this method is great for games, not so much for other things. in order here are how many particles I can get with each method,

normal grid - 3000
smaller accurate grid - 6000
smaller less accurate grid - 9000


_Skully(Posted 2010) [#9]
Hi Nathan,

This confuses me as to why its faster to use this "approximation".. perhaps its in the algorithm

If you are using the cells to determine proximity influences and therefore have a list of the "particles" in each cell, then I would assume you are using a distance formula to filter out particles over a certain distance when parsing the list.

Does calculating the distance formula save that much time... how complex are the fluid calculations?


Nate the Great(Posted 2010) [#10]
hey skully

it is faster because it doesnt test as many particles that actually arent neighbors at all as apposed to normal grids, I hope that makes sense but I dont exactly understand what you are asking.


ImaginaryHuman(Posted 2010) [#11]
You should try using vertex arrays, it could double the speed. glBegin/End is not usually as fast because there is lots of function call overhead.

Also things all being on one texture has nothing to do with your glBegin/End except that everything within the glBegin/End MUST use the current texture since you can't swap textures while defining geometry. So, yah.


Nate the Great(Posted 2010) [#12]
thanks IH, that shows how little I know about gl ;)


WERDNA(Posted 2010) [#13]
Downloading now, this looks awesome :)


ImaginaryHuman(Posted 2010) [#14]
Especially since you have a large number of particles, I think the vertex array will help a lot and it's supported in standard OpenGL 1.1


Noobody(Posted 2010) [#15]
Oh, then it's a lot simpler than I imagined :)

The particle misses do contribute to the overall instability, so it's not really an option for me at the moment. Dividing the grid cells into further sub cells is also not a good idea, since I'm already having memory problems with a regular grid (3D, that is). Splitting each cell into more sub cells would burst my RAM.

Also, I think a big problem is that particles don't have to be centered in a grid cell like in your drawings. If they're near borders, much more neighbours will be left out, leading to discrepancies between particles in the same grid cell, depending on their location inside that cell. An overall calculation error that is the same everywhere in the grid wouldn't be that bad, but errors sensitive to particle disorder are very bad for the overall behaviour of the fluid. I therefore recommend using this new method with care, because the gain in performance is probably not worth the loss in 'realistic-ness'.


Nate the Great(Posted 2010) [#16]
Oh, then it's a lot simpler than I imagined :)



but the process of getting to it took a week of messing around with my grid haha then I was like hey this is a lot simpler than I was making it out to be.


The particle misses do contribute to the overall instability, so it's not really an option for me at the moment. Dividing the grid cells into further sub cells is also not a good idea, since I'm already having memory problems with a regular grid (3D, that is). Splitting each cell into more sub cells would burst my RAM.



ah, I am leaning toward using smaller cells and checking more of them (the middle picture above) but that is because it is for a game and has a limited 2d playing field. The real advantage of this is that I can adjust the grid size to trade stability for speed which is really what I need for this, if my game doesnt look realistic or starts exploding I crank up the number of cells checked or adjust the grid size.


Also, I think a big problem is that particles don't have to be centered in a grid cell like in your drawings. If they're near borders, much more neighbours will be left out, leading to discrepancies between particles in the same grid cell, depending on their location inside that cell. An overall calculation error that is the same everywhere in the grid wouldn't be that bad, but errors sensitive to particle disorder are very bad for the overall behaviour of the fluid. I therefore recommend using this new method with care, because the gain in performance is probably not worth the loss in 'realistic-ness'.



yeah I realize that, that is why it is a balancing act, trading speed for stability but I actually cant tell a difference in the realisticness with the method described in the picture in the middle so I am leaning toward that where I can get 6000 unthreaded, I hope blitz max's threading capabilities have improved enough to make it threaded without significant loss of time on the gc... I also have a previous neighbor list stored in each particle that works quite well and catches some missed particles, unfortunately I havent experimented with that much so its not as fast as I would like it to be to use in the game, overall I am happy with how it is now, I get 6000 particles very easily at a playable framerate, now I have to get viscosity to work, I hit a bump with those equations and it never really got fixed, just left out...

@ IH

thanks for the suggestion, I really want to learn how vertex arrays work even though with 10000 particles my render time is 1 ms, ill post in the open gl section sometime this week if I make enough progress to worry about rendering.


slenkar(Posted 2010) [#17]
cool demo man


Nate the Great(Posted 2010) [#18]
Ive been messing around with viscosity and how my goo is going to react with the environment. I definitely need to make it more gooey but for now its pretty good. It also takes over anything it touches very quickly which will be an important part of gameplay in flood.

Vid here http://www.youtube.com/watch?v=6cBDLcW1ZJI


ImaginaryHuman(Posted 2010) [#19]
Neat, Nate.


slenkar(Posted 2010) [#20]
it behaves very much like water now,

isntead of viral goo, you could do a game based on mixtures, keeping certain elements at certain concentrations.