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)

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]

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.

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.

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

Uhmm...

Try NeHe''s physics tutorials for masses connected by springs??

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.


Can anyone who''s experimented with this kind of thing tell me if this is actually possible?


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