Jump to content
  • Advertisement
Sign in to follow this  
pinknation

Optimized Collision Detection & Physics

This topic is 3326 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.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!

Share this post


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

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.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;
}"







this way:

for(int i = 0; i < particles_length; ++i)
{
if( particle.id != particles.id )
{
Vector2 difference = particles.get_location() - particle.get_location();
float cubed_distance = cubed_length( difference );
if( cubed_distance ) > cubed_minimum_distance )
{
Vector2 force = ( G * particle.get_mass() * particles.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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!