Archived

This topic is now archived and is closed to further replies.

HasHPIT

performance problems with fluid simulator

Recommended Posts

If you just wanna give a quick answer you can skip the explanation and skip right to the question at the bottom (but it might make more sence if you read it all) I am making a fluid simulator. The general idea is to have a lot of particles interacting. All the particles try to maitain a certain distance to each other. This means that all the particles need to figure out how long they are from each other. All particles checking all other particles take up a lot of cpu cycles, way to many in fact. I would like a 1000 particles, so that would make 1000 * 1000 = a million distance calculations (minus the once that get checked twice). I check the distance with the formula sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2) and I think that it is when I run this a million times that the frame rates drop pretty nasty. So my question is : Is there another way to calculate the distance between 1000 3d points than the one mentioned above? (and by "another way" I mean a faster way)

Share this post


Link to post
Share on other sites
ABSOLUTELY!!! The best & quickest way to speed that bad boy up is NOT to take the sqrt of the distance^2, so if you can design your code to just deal with the square of the distance... more power to you, that will help a lot. if you can't.... sorry man.

I'm sure you can visualize, but it looks something like this:

distance = (x1-x2)^2+(y1-y2)^2+(z1-z2)^2

ANOTHER WAY.............
I haven't tested it, but if you want an even worse hack (& thus a worse approximation) you can just add together the two largest axis values & use that as the distance. I know its CRAP, but its a TON faster I'm sure & won't give toooooooo bad of an approximation as long as you are just useing the distances for simple comparisons & checks. You might as well try it & see if it works good with a simulation. Sometimes the weirdest things end up being the best looking. Maybe like this...

float bad_dist;
X = x1-x2; Y = y1-y1; Z = z1-z2;

if(X > Z){
bad_dist += X;
if(Y>Z){
bad_dist += Y;
}else{
bad_dist += Z;
}
}else{
bad_dist += Z;
if(X>Y){
bad_dist += X;
}else{
bad_dist += Y;
}
}

So this way, the bad distance is achieved for each particle with a MAXIMUM of:
2 additions and
3 subtractions and
2 comparisons (look closely)

This is MUCH MUCH MUCH BETTER than the previous method of:
2 additions and
3 subtractions and
3 multiplications
1 square root

The 1st method I mentioned at the top is the same as the latter EXCEPT without the square-root, which will actually help considerably, I'd suggest giving both a try.


[edited by - Luke Miklos on November 17, 2003 6:30:24 PM]

Share this post


Link to post
Share on other sites
Thats pretty brave to try and give real time graphics to a fairly complex simulations. Somthing you may want to consiter is having the simulator draw and then write the image drawn to a file. That way even if you had a frame rate of 1 fame per 5 days you could make a video out of the caputures.

This is of coruse if you end up wanting to make this more complex.

Share this post


Link to post
Share on other sites
there are 2 other things you can/should do, first of all use some sort of space partitioning if each particle has a max known posible distance to travel , and of course unroll your loops.

Share this post


Link to post
Share on other sites
Depending on the hardware this needs to run on you could look at floating-point textures, pBuffers and fragment programs.

I don't currently have access to hardware that is capable of any of this so this is all theoretical but I suspect you should be able to do something like:

1. write the positions of your particles into a 1D floating point texture. I.e. the red component of the first pixel would be particles[0].x, the green would be particles[0].y, e.t.c.

2. write a fragment program that takes the x,y position or the texcoords of each fragment and obtains the pixel positions of the relevant particle by sampling the 1D texture. So for the pixel with position (3,179) you would sample pixels 3 and 179 of the 1D texture. Next dot product the resulting vectors. If you require absolute distance then square root the result and write it to the pBuffer (must be floating-point) as the colour. Alternatively if you just need to know when pixels are too close just set the colour to white if the resulting dot product is less than distance squared, or black otherwise.

3. render a 1000 by 1000 (number of particles * number of particles) quad in ortho mode so that it covers exactly 1000 * 1000 pixels and uses the fragment program from 2.

4. read back your pBuffer to find the distances/which pixels are too close.



Engima

EDIT: typo


[edited by - Enigma on November 18, 2003 8:46:17 AM]

Share this post


Link to post
Share on other sites
A trick from physics, where it is important to take into account every particle and you have millions of them, is to make a grid and calculate each particles effect at each grid point, and then interpolate between them, so 1,000,000 particles on a 100x100 grid is 10^6 * 10^4 calculations at grid points, + 10^6 interpolations, instead of 10^6 * 10^6 particle-particle interactions.

For you, however, it sounds like taking into account every particle will be overkill - a partitioning system would be better (same grid, stick each particle in the nearest cell, and only account for particles in the same cell or a neighbouring cell).

Also, as the first reponse said, try to maintain a particular inverse-squared distance to other particles. Most real physics things behave this way anyway (things in the distance are practically irrelevant)

Share this post


Link to post
Share on other sites
thanks for all the replies. I will definately see how much of a difference it will make, using the simpler distance calculations. Right now I can run it at 50 fps with 100 particles. Now I will change the distance formula and re-calibrate for realism

Share this post


Link to post
Share on other sites
quote:
Original post by Enigma
Depending on the hardware this needs to run on you could look at floating-point textures, pBuffers and fragment programs.

I don''t currently have access to hardware that is capable of any of this so this is all theoretical but I suspect you should be able to do something like:

1. write the positions of your particles into a 1D floating point texture. I.e. the red component of the first pixel would be particles[0].x, the green would be particles[0].y, e.t.c.

2. write a fragment program that takes the x,y position or the texcoords of each fragment and obtains the pixel positions of the relevant particle by sampling the 1D texture. So for the pixel with position (3,179) you would sample pixels 3 and 179 of the 1D texture. Next dot product the resulting vectors. If you require absolute distance then square root the result and write it to the pBuffer (must be floating-point) as the colour. Alternatively if you just need to know when pixels are too close just set the colour to white if the resulting dot product is less than distance squared, or black otherwise.

3. render a 1000 by 1000 (number of particles * number of particles) quad in ortho mode so that it covers exactly 1000 * 1000 pixels and uses the fragment program from 2.

4. read back your pBuffer to find the distances/which pixels are too close.



Engima

EDIT: typo


[edited by - Enigma on November 18, 2003 8:46:17 AM]



BTW you only have to render a 1000x1000 triangle not a quad because the distance from 3 to 179 is the same as from 179 to 3! :-)

So you only have the half "pixels" to calculate!

--------------------------------------------------------

"If it looks good, it is good computer graphics"
"If it looks like computer graphics, it is bad computer graphics"

Corrail
corrail@gmx.at
ICQ#59184081

Share this post


Link to post
Share on other sites