Hi, my simulation is slowing down @ 200 particles, this mainly was because of the collision detection at first, where every particle, checked for collision against every other particle, meaning 200 * 199 iterations were processed each frame(along side the F = GMm/R^2 equation, which made it slower), I was able to speed this up, by implementing a spatial index grid.. which allowed me to only check for collision of neighboring particles(within the same grid cell), however the force calculations are still gathering a total(because that's most accurate.. perhaps I dont have to?) and so ending up w/ 200 * 199 iterations, still.. is there any way to speed up the math here, and any suggestions for other optimizations? " for(int i = 0; i < particles_length; ++i) { if(particle.id == particles.id) continue; float d_x = particles.p_x - particle.p_x; float d_y = particles.p_y - particle.p_y; float R = sqrt(d_x * d_x + d_y * d_y); float F = G * particle.mass * particles.mass / (R * R); if(R == 0.f || F == 0.f) continue; particle.f_x += d_x * F / R; particle.f_y += d_y * F / R; }" that adds the gravitation force of F = GMm/R^2. my collision code is: vector<int> idxs = grid->GetNeighbourIndex(particle); for(unsigned int j = 0; j < idxs.size(); ++j) { int i = idxs[j]; if(particle.id == particles.id) continue; double cNorm = atan2(particles.p_y - particle.p_y, particles.p_x - particle.p_x); double nX = cos(cNorm); double nY = sin(cNorm); double a1 = DotProduct(particle.v_x, particle.v_y, nX, nY); double a2 = DotProduct(particles.v_x, particles.v_y, nX, nY); double optimisedP = (2.0 * (a1-a2)) / (particle.mass + particles.mass); float d_x = particles.p_x - particle.p_x; float d_y = particles.p_y - particle.p_y; float R = sqrt(d_x * d_x + d_y * d_y); float totalRadius = particle.radius + particles.radius; if(R < totalRadius) { float radDiff = (totalRadius - R) * .5f; // force both particles out of one anothers radius particle.p_x -= radDiff; particle.p_y -= radDiff; particles.p_x += radDiff; particles.p_y += radDiff; // Reflect Velocities particle.v_x -= (optimisedP * particles.mass * nX) * .5f; particle.v_y -= (optimisedP * particles.mass * nY) * .5f; particles.v_x += (optimisedP * particle.mass * nX) * .5f; particles.v_y += (optimisedP * particle.mass * nY) * .5f; } } which I hope can also be optimized in some way.. (mostly took that code from somewhere on this site I think); Side-Question: I'm having one particular issue w/ collision detection, which is, it 'un-collides' all current collisions, though sometimes creates more 'collisions' before its unable to sweep it again, resulting in physics related issues(where the particles are to close, and blast off at some really high velocity), my order of computations is AddTotalForces, Update Particle, Collision Sweep.. any ideas how to fix this..? >.> unless I like had something recursive to constantly un-collide particles, until there are none colliding, I cannot think of any way to solve that.. so.. any suggestions here would help!

uhm, Felix, your optimizations only made things buggy.. >.>

@flounder: thanks, uhm, about the multiplying by .5f, that was just a quick way for me to add friction, so nevermind that :P;

as for what you said about the sqrt thing.. that only made it buggy.. :S

the 'buggy' that I refered to for both of you, was the particles began to vibrate, and/or not move

@Flounder, thanks! I've resolved that, actually a noticeable speed-boost! Thanks, much!

@Felix, you're right... that is exactly why! That's why I've included the collision detection, to avoid them becoming super close, however, during the Collision Detection Sweep, it pushes two colliding particles away from each other, and sometimes even pushes one of them, directly into another, causing it to 'shoot off'. That's what I was trying to explain in my original post, that I need a better method of Collision Detection, because my current solution doesn't solve each collision, before updating the physics.

@Flounder, thanks! I've resolved that, actually a noticeable speed-boost! Thanks, much!

@Felix, you're right... that is exactly why! That's why I've included the collision detection, to avoid them becoming super close, however, during the Collision Detection Sweep, it pushes two colliding particles away from each other, and sometimes even pushes one of them, directly into another, causing it to 'shoot off'. That's what I was trying to explain in my original post, that I need a better method of Collision Detection, because my current solution doesn't solve each collision, before updating the physics.

Edit: Oops, I've posted this twice.. ^_^' Sorry. I've read up on some collision response, and junk.. I've re-wrote my code(it's somewhat faster now), but there still seems to be some issues where they become to close, and shoot off.. My current code (for collisions detection) is:

vector<int> FindContacts(Particle &particle)
{
vector<int> contacts = vector<int>();
vector<int> idxs = grid->GetNeighbourIndex(particle);
for(unsigned int j = 0; j < idxs.size(); ++j)
{
int i = idxs[j];
if(particle.id == particles.id) continue;
float d_x = particles.p_x - particle.p_x;
float d_y = particles.p_y - particle.p_y;
if(d_x * d_x + d_y * d_y < (particle.radius + particles.radius)*(particle.radius + particles.radius))
contacts.push_back(i);
}
return contacts;
}

void NarrowPhaseCollision(Particle &particle, Particle &particle2)
{
float friction = .5f;

if(particle.id == particle2.id) return;

float d_x = particle2.p_x - particle.p_x;
float d_y = particle2.p_y - particle.p_y;
float R = d_x * d_x + d_y * d_y;

float totalRadius = particle.radius + particle2.radius;

if(R < totalRadius * totalRadius)
{
R = sqrt(R);

float radDiff = (totalRadius - R) * .5f;
double nX = d_x / R;
double nY = d_y / R;

double a1 = DotProduct(particle.v_x, particle.v_y, nX, nY);
double a2 = DotProduct(particle2.v_x, particle2.v_y, nX, nY);
double optimisedP = (2.0 * (a1-a2)) / (particle.mass + particle2.mass);

// force both particles out of one anothers radius
particle.p_x -= radDiff;
particle.p_y -= radDiff;
particle2.p_x += radDiff;
particle2.p_y += radDiff;

// Reflect Velocities
particle.v_x -= (optimisedP * particle2.mass * nX) * (1 - friction);
particle.v_y -= (optimisedP * particle2.mass * nY) * (1 - friction);
particle2.v_x += (optimisedP * particle.mass * nX) * (1 - friction);
particle2.v_y += (optimisedP * particle.mass * nY) * (1 - friction);
}
}

void BroadPhaseCollision()
{
for(int i = 0; i < particles_length; ++i)
{
vector<int> collisions = FindContacts(particles);
if(collisions.empty()) continue;
for(unsigned int j = 0; j < collisions.size(); ++j)
NarrowPhaseCollision(particles, particles[collisions[j]]);
}
}

FindContacts() uses my Spatial Index Grid, to locate neighboring particles, which are checked for collisions, and then passes those which are colliding to the NarrowPhaseCollision(), which simply pushes the particles apart based on their radius, and uses a reflection velocity(with a friction constant), to push them farther apart.. This did manage to speed things up slightly, though its still not the best solution.

My current order of action is:
Add all forces to each particle individually(still time consuming)
Update Particle Physics
Start BroadPhaseCollision()
Draw each particle

Edit2: Unknown reason, though if instead of returning contacts as their IDs, but the actual Particle object itself, the particles never get 'too close', because they seem to constantly push one another, until they're no longer touching, however this seems to happen often, and so you notice what used to just be circular rotating clusters, is now becoming longer thinner lines. :P

[Edited by - pinknation on August 18, 2009 3:46:11 AM]

Well, after reading the function vector<int> findContacts( Particle& particle ):

you're allocating memory for each particle, to find neighbour ids. If you're only searching for collisions involving particles located in the same cell, there's no need to do it for each particle. Since you know how many particles are located in a cell, you know exactly how many neighbours each one has: the number of particles in the cell, minus one...Moreover as you certainly store particle ids in the cell( the cell data structure must have a container of ids( or pointers to particles ) ), there's definitively no need to allocate memory for each particle, since you know that his neighbours are all the ids( pointers ) in the cell data structure, except its own. Allocating memory costs, and doing it for each particle, at every update, is even more costly.
You can remove that cost by doing all the collision detection "cell-wise", not "particle-wise".

P.S: You can further remove the allocation factor, knowing that each grid cell has a maximum number of particle.

So:

for each cell
...

Instead of:

for each particle
...

You don't need defining an id data member, since the adress of a particle is enough to identify it. You should test if two particle adresses match, instead of testing if their ids do. The id data member is redundant( unless you use it for something else ).

So if you had to do it "cell-wise":
you should traverse your particle list of pointers( or ids ) and compute all interactions without the need of neighbouring information for each particle.


i and j are particle indexes in the cell's array of particle pointers.

This is at first, what I can say about your algorithm.

You should, for example, implement the following function


this way:


It enhances readability and maintenance.

[Edited by - johnstanp on August 18, 2009 9:12:38 AM]

it shouldn't matter if I swept through cells, or particles.. because either way I'd loop through each particle, adding the cell loop, would simply add an extra loop.

Edit: Would AABB method of collision detection be better? Currently I am using a Spatial Index Grid.. which I've seen used in SPH systems.