Sign in to follow this  

Optimized Collision Detection & Physics

This topic is 3038 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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[i].id) continue; float d_x = particles[i].p_x - particle.p_x; float d_y = particles[i].p_y - particle.p_y; float R = sqrt(d_x * d_x + d_y * d_y); float F = G * particle.mass * particles[i].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[i].id) continue; double cNorm = atan2(particles[i].p_y - particle.p_y, particles[i].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[i].v_x, particles[i].v_y, nX, nY); double optimisedP = (2.0 * (a1-a2)) / (particle.mass + particles[i].mass); float d_x = particles[i].p_x - particle.p_x; float d_y = particles[i].p_y - particle.p_y; float R = sqrt(d_x * d_x + d_y * d_y); float totalRadius = particle.radius + particles[i].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[i].p_x += radDiff; particles[i].p_y += radDiff; // Reflect Velocities particle.v_x -= (optimisedP * particles[i].mass * nX) * .5f; particle.v_y -= (optimisedP * particles[i].mass * nY) * .5f; particles[i].v_x += (optimisedP * particle.mass * nX) * .5f; particles[i].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!

Share this post


Link to post
Share on other sites
You shouldn't be getting quadratic time with a spatial index grid, but it's hard to tell that with just the code posted. As for speeding it up, you can rearrange the math to remove some redundant operations.

nX=d_x/R
nY=d_y/R

So you can remove the atan2, sin, and cos. You don't need to calculate optimisedP unless the particles are colliding. You multiply optimisedP by 2.0 and then multiply it by 0.5 when its added to the particle velocities, so you can remove both of those. It's possible to avoid a square root by checking if (R<totalRadius*totalRadius), and then writing R=sqrt(R) if that's true.

EDIT: I can't see why your particles are shooting off at high velocities, might be something in AddTotalForces.

Share this post


Link to post
Share on other sites
Well actually, I don't know how much it would speed it up, but I might avoid the sqrts.

Since it is possible to just use the non-sqrt versions for R for the code below,

float R = d_x * d_x + d_y * d_y;
float F = G * particle.mass * particle[i].mass / R;
...
particle.f_x += d_x * (F*F)/R;
particle.f_y += d_y * (F*F)/R;

Multiplications are definitely cheaper than a sqrt, but, how much would this speed up, I am not too sure, hope this is useful, hahahah... :)

EDIT: I didnt notice this line

float radDiff = (totalRadius - R) * .5f;

so I guess what i said above cant really help, hahahaha, but actually the last time I did something like this, without the collision detection, just purely using the gravitational formular, I remember them shooting away really quick when they get really close, if I don't remember wrongly, finally I find the problem is when the two are really close, the force becomes really big or something, you might want to take a look at that, it might not be because of the collision detection...

[Edited by - FelixWong on August 17, 2009 11:57:31 PM]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
@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.

Share this post


Link to post
Share on other sites
@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[i].id) continue;
float d_x = particles[i].p_x - particle.p_x;
float d_y = particles[i].p_y - particle.p_y;
if(d_x * d_x + d_y * d_y < (particle.radius + particles[i].radius)*(particle.radius + particles[i].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[i]);
if(collisions.empty()) continue;
for(unsigned int j = 0; j < collisions.size(); ++j)
NarrowPhaseCollision(particles[i], 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]

Share this post


Link to post
Share on other sites
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.


for each cell
{
start with i = 0

for each particle i
{
start with j = i + 1

for each particle j
{
if particles i and j collide
...
}

increment j
}

increment i
}







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

" for(int i = 0; i < particles_length; ++i)
{
if(particle.id == particles[i].id) continue;
float d_x = particles[i].p_x - particle.p_x;
float d_y = particles[i].p_y - particle.p_y;
float R = sqrt(d_x * d_x + d_y * d_y);
float F = G * particle.mass * particles[i].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;
}"







this way:

for(int i = 0; i < particles_length; ++i)
{
if( particle.id != particles[i].id )
{
Vector2 difference = particles[i].get_location() - particle.get_location();
float cubed_distance = cubed_length( difference );
if( cubed_distance ) > cubed_minimum_distance )
{
Vector2 force = ( G * particle.get_mass() * particles[i].get_mass() / ( cubed_distance ) )
* difference;
if( squared_length( force ) > squared_minimum_force )
{
particle.set_location( particle.get_location() + force / particle.get_mass() * delta_time );
}
}
}
}







It enhances readability and maintenance.

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
It matters a lot if you sweep through cells or particles, the entire point of having cells is to avoid checking collisions between particles that will never collide. Typically a spatial indexing grid goes like this:

You have a grid of cells.
Each cell has a list of the objects overlapping it
Go through each cell, check for collisions between each object listed in the cell.

You shouldn't need to be building a list at collision time.

Share this post


Link to post
Share on other sites
yeah, understandable, I went ahead and listened to you guys:


void BroadPhaseCollision()
{
grid->Refresh(particles, particles_length);

for(int i = 0; i < grid->Width * grid->Height; ++i)
{
for(unsigned int j = 0; j < grid->m_grid[i].size(); ++j)
{
Particle p1 = particles[grid->m_grid[i][j]];
for(unsigned int k = j + 1; k < grid->m_grid[i].size(); ++k)
{
Particle p2 = particles[grid->m_grid[i][k]];
if(p1.id == p2.id) continue;
float d_x = p2.p_x - p1.p_x;
float d_y = p2.p_y - p1.p_y;
float R = p1.radius + p2.radius;
if(R * R > d_x * d_x + d_y * d_y)
NarrowPhaseCollision(particles[grid->m_grid[i][j]], particles[grid->m_grid[i][k]]);
}
}
}
}



its actually faster(at least its not as slow as it was before with 400 particles), though the collision itself is still acting funny.. I'll continue to try and figure that out :[

The problem is, that after the collisions are dealt with, more collisions are created, though its finished checking for collision, and continues to update the particles, resulting in a rather buggy Simulation.

Share this post


Link to post
Share on other sites
Quote:
Original post by pinknation
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.


Yes, it matters a lot...even more if at each step, you compute the neighbours of every particle. So if you have one thousand particles, for each step( time step ), you, at least, allocate( and deallocate ) one thousand lists of neighbours. This is very costly.
The point was: you don't need computing neighbouring information, since you already have it. Avoiding computing redundant information, is an optimization.
I was not recommending you to add another loop to an existing one, I was simply recommending you to write a faster loop.

You don't need doing things particle-wise, because if A collides with B, then B collides with A: so computing forces, impulses or any other things to maintain your simulation in a coherent state, can be done for each couple of interacting particles, instead of doing it twice, as if the two interacting particles were not affected by the same event.

P.S: I noticed you were computing for every two possible interacting objects, their force of interaction. You should test first if they can possibly interact, and then only compute their force of interaction.

Quote:

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.

I don't know if I perfectly understood your question...Your spatial index grid algorithm is a recommended one, and basically does not depend on the bounding volume you use to detect collisions.
You'll still need it( or any other possible divide and conqueer method ) no matter the bounding volume you use.
As you may know, detecting collisions between two spheres( as your collision test shows ) is faster than detecting collision between two AABBs. The only problem is that spheres give many false positives, in general. AABBs are generally better: it depends of the simulation. But if your particles are particles in the most common acception, then there's no need of using bouding volumes.

[edit]Sorry, I didn't see your post...

Share this post


Link to post
Share on other sites
It's all good, thanks.. I'm just having issues now with particles colliding with one another, after the collision tests have completed. :[ I've been reading up on more collision detection & response, though I'm not understanding how to resolve this problem in an non-costly manner, like all that keeps coming to mind is 'BRUTE-FORCE BRUTE-FORCE BRUTE-FORCE'. ^_^

Share this post


Link to post
Share on other sites
Quote:
Original post by pinknation
yeah, understandable, I went ahead and listened to you guys:

*** Source Snippet Removed ***

its actually faster(at least its not as slow as it was before with 400 particles), though the collision itself is still acting funny.. I'll continue to try and figure that out :[

The problem is, that after the collisions are dealt with, more collisions are created, though its finished checking for collision, and continues to update the particles, resulting in a rather buggy Simulation.


This is to be expected. Actually you should try detecting the time of the first collision after having checked all possible collisions. Let's tfc be the time of first collision. Then advance your simulation to that time, if it is inside your timestep( otherwise don't care )...That is, if the actual simulation time is to and your timestep dt, if tfc < to + dt, then dt = tfc - to. You'll have the assurance that only two objects are colliding at time tfc. Your timestep will not, on the contrary, be fixed.

Share this post


Link to post
Share on other sites
Quote:
Original post by pinknation
It's all good, thanks.. I'm just having issues now with particles colliding with one another, after the collision tests have completed. :[ I've been reading up on more collision detection & response, though I'm not understanding how to resolve this problem in an non-costly manner, like all that keeps coming to mind is 'BRUTE-FORCE BRUTE-FORCE BRUTE-FORCE'. ^_^


One thing is certain, you won't find an easy way of detecting collisions and compute collision responses, if you have a lot of "fast moving" object, in a "small" region of space.

Share this post


Link to post
Share on other sites
Quote:
Original post by pinknation
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


Didn't really read the thread, so maybe this has been said, but you should be able to get that to 200*100 really easily.

If A collides B, then B collides A. Therefore, only test each pair of items once. Psuedo-coded:

for each item:
for each item after other item:
collide 'em


This, of course, is still quadratic time but it's still a strong improvement for no real overhead.

Share this post


Link to post
Share on other sites
If you're doing a distance check in NarrowPhaseCollision, you don't need to do it in BroadPhaseCollision. Your issue with resolving one collision and creating another in the process doesn't have any fast solution that I know of, but you can make it look better by performing your collision phase multiple times.

Share this post


Link to post
Share on other sites
you could also consider not returning by-value and instead receive by reference in this function.
vector<int> FindContacts(Particle &particle)


Specially if you know at hand how many vector<int> you will need.

or you can always receive by reference the destination vector<int> and do a swap with contacts instead of returning saving that way a temporary value and a call to the copy constructor (copying all elements from contacts to thetemp)

Also a good compiler will remove most of the declaration in the scope of the for but we can never be sure :P (well actaually we can always look at asm)
but its better always to on the safe safe side and declare those outside the scope of the for:
cNorm, nX, nY, a1, a2 etc.

Finally if you want to achieve a really high count of particles you should look into aceleration structures (BVH, BSPs etc) and use the principle that if one particle is a node of the BVH then it doesn't need to be tested for colision with any other node.

Cheers

Share this post


Link to post
Share on other sites

This topic is 3038 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this