# 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.

## Recommended Posts

##### 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 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

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 on other sites

@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 on other sites
I probably didn't explain it correctly, can you post the modified code?

##### 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 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;
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;

{
R = sqrt(R);

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

// 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);
}
}

{
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
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 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
...

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.

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 );			}		}	}}

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

##### 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 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.

1. 1
2. 2
3. 3
4. 4
Rutin
12
5. 5

• 12
• 17
• 10
• 14
• 10
• ### Forum Statistics

• Total Topics
632660
• Total Posts
3007698
• ### Who's Online (See full list)

There are no registered users currently online

×

## Important Information

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!