Sign in to follow this  
too_many_stars

inifinite mass and a jitter problem

Recommended Posts

Hi guys,

 

I have a small issue with impulse based physics. After loading a 2d array of inifinite mass "bricks" (32x32) into a game level and dropping a character with finite mass on top of the bricks everything works fine until the character spans two bricks. That's when the jitter starts.

 

Code is pairwise AABB vs AABB testing like so

for(unsigned int i=0;i<entities.size();i++){
		for(unsigned int j=i+1;j<entities.size();j++){
			if(entities[i]->rigid->i_mass==0.0f && entities[j]->rigid->i_mass==0.0f)
				continue;
			//check collisions here
					
		}
	}

I don't quite understand what's going on here. All the collision and physics works fine until a third finite mass entity is in contact with two infinate mass entities, whether the two inifinate mass entities are in contact or not. 

 

I did not test this on other shapes, just AABBs.

 

Could this have something to do with floating point errors perhaps?

 

Thanks,

 

Mike

Share this post


Link to post
Share on other sites

Could it simply be that while the corrective impulse from interacting with brick #1 is exactly enough to counter the finite mass objects perp velocity vector due to movement and gravity, the the impulse caused by interaction with brick #2 does not take this into account and applies the same impulse, resulting in overshoot? I've experienced similar behaviour in some of my innumerable physics experiments.

 

Cheers,

Mike

Edited by h4tt3n

Share this post


Link to post
Share on other sites

In my opinion the most robust solution is always to only apply some fraction of the total needed impulse, and then iterate through the velocity-part of the constraint until it reaches an equilibrium. 

Share this post


Link to post
Share on other sites

If you would post your collision response code I or someone else might be able to tell you specifically how to improve it. Basically what you do is for each loop (1) pre-compute all object distances, normalized vectors, overlaps, and the exact impulse needed to move colliding objects apart. (2) Apply a fraction of that impulse + a velocity dependant damping impulse, resulting in new object velocities, but do *not* update object position. Repeat (2), recycling all data computed in (1) but with re-computed damping impulses until an acceptable global equilibrium is reached. Depending on the setup and your expectations this could be done in perhaps 4 - 16 iterations. (3) Update position and go back to (1). 

 

Cheers,

Mike

Share this post


Link to post
Share on other sites

Inside the main update loop

		for(ui i=0;i<bodies.size();i++)
			bodies[i]->integrate(1.0f/(float)FPS);
		
	
		for(ui i=0;i<bodies.size();i++){
			for(ui j=i+1;j<bodies.size();j++){
				if(bodies[i]->i_mass==0.0f && bodies[j]->i_mass==0.0f)
					continue;
				ContactInfo ci;
				
				collisionTest collide=coll_matrix[bodies[i]->type][bodies[j]->type];
				if(collide(bodies[i],bodies[j],ci)){
					Contact contact(bodies[i],bodies[j],ci);
					contacts.push_back(contact);

					
				}
				
			}		
		}
		
		for(ui i=0;i<contacts.size();i++)
			contacts[i].solvePenetration();

		for(ui iter=0;iter<iterations;iter++)
			for(ui i=0;i<contacts.size();i++)
				contacts[i].solveImpulse();

Penetration method

void Contact::solvePenetration(){
	float tot_i_mass=b1->i_mass+b2->i_mass;

	b1->center-=ci.normal*b1->i_mass/(tot_i_mass)*ci.pen;
	b2->center+=ci.normal*b2->i_mass/(tot_i_mass)*ci.pen;
	
}

and the impulse solve method

void Contact::solveImpulse(){
	Vec2 rel_vel=b2->vel-b1->vel;
	float sep_vel=rel_vel.dot(ci.normal);;
	if(sep_vel>0.0f)
		return;
	float tot_i_mass=b1->i_mass+b2->i_mass;

	b1->vel+=ci.normal*sep_vel*((b1->i_mass/(tot_i_mass))*(1+ci.e));
	b2->vel-=ci.normal*sep_vel*((b2->i_mass/(tot_i_mass))*(1+ci.e));

}

Share this post


Link to post
Share on other sites

Okay, I'll give it a try. Just please don't expect me to deliver a ready-made code snippet that can be pasted directly into your program. First, I'd like to know a little more about the iterations going on here:

for(ui iter=0;iter<iterations;iter++)
			for(ui i=0;i<contacts.size();i++)
				contacts[i].solveImpulse();

This seems to be doing exactly the kind of velocity-level iteration that I recommended earlier. What change in behaviour do you experience when changing the number of iterations? Especially, what happens when you have a lot of interacting bodies either stacked or pulling each other via constraints?

 

Cheers,

Mike

Edited by h4tt3n

Share this post


Link to post
Share on other sites

Hi Mike,

 

 

What change in behaviour do you experience when changing the number of iterations?

Visibly none

 

what happens when you have a lot of interacting bodies either stacked or pulling each other via constraints?

That depends.

 

When I have an AABB with finite mass, resting (more specifically after falling, ie due to gravity) onto 2 or more infinetly massed AABBs, the finite mass AABB starts to jitter.

 

Now, if I have an AABB with finite mass resting on one infinitelly massed AABB, there's no jitter and the object is settled.

 

If I have many objects resting on top of each other, especially ones with bigger masses resting on smaller masses I get jitters, but that's usually if there's more than 3 or 4. For my game purposes this is not a concern as I am not attempting to do a physical simulation.

 

I strongly suspect that the issue is what you told me about earlier,

 

 

Could it simply be that while the corrective impulse from interacting with brick #1 is exactly enough to counter the finite mass objects perp velocity vector due to movement and gravity, the the impulse caused by interaction with brick #2 does not take this into account and applies the same impulse, resulting in overshoot?

 

However, I am not exactly sure how to solve this problem. I tried two different SAT algos, and one works better than the other, but the issue persists.

 

Thanks,

 

Mike

Share this post


Link to post
Share on other sites

Hi again,

 

It looks like your program is first lifting the finite mass object free of contact with the infinite mass object (SolvePenetration), and then applies a separation impulse of some magnitude (SolveImpulse). So in short, your code lifts the movable object free of the ground and then applies a velocity away from it. This will always create jitter. 

 

I would drop SolvePenetration completely and only apply an iterative impulse that separates the objects and dampens them, in principle like a damped spring but formulated as an impulse. Something like this, where k and d are stiffnes and damping coefficients between 0 and 1 (start with 0.3 or something like that). Number of iterations could be anything from 1 to 20, you should see a noticeable difference. You may need to swap signs somewhere to make it work properly, remember I can't test this, only compare to my own code. 

 

Cheers,

Mike

void Contact::solveImpulse(){
    
    Vec2 rel_vel=b2->vel-b1->vel;

    float sep_vel=rel_vel.dot(ci.normal);

    float tot_i_mass=b1->i_mass+b2->i_mass;

    b1->vel+=ci.normal*(-ci.pen*(1.0f/(float)FPS)*k+sep_vel*d)*((b1->i_mass/(tot_i_mass));
    b2->vel-=ci.normal*(-ci.pen*(1.0f/(float)FPS)*k+sep_vel*d)*((b2->i_mass/(tot_i_mass));

}
Edited by h4tt3n

Share this post


Link to post
Share on other sites

@h4tt3n

 

I have implemented your algorithm and here's what I found by playing around with the numbers. Note, that this is after commenting out the solvePenetration() method, thereby, transferring all contact resolution to a velocity based system.

 

1.) The jittering stopped when standing on two inverse mass=0.0f tiles. This was the exact result I was looking for, and by playing with three parameters, the iterations, the "d" and the "k" I was able to come up with a global solution that was stable (of course it's only a 2d game where block stacking is not necessary, therefore, I did not do a full body physics test). But all things considered, it works very well.

 

2.) A new problem now cropped up. When an AABB with finite mass is "walking" along infinate mass tiles which are placed adjacent to each other (horizontaly), the algo you supplied allows for a little sinking into the existing tile, which means that if I am "walking" right, the bottom right corner of finite mass AABB snags the top left corner of the tile being walked on providing for a rough jerking motion which should be smooth acceleration.

 

If you have any ideas how to solve this, please let me know. I tried a few hacks, for example turning off gravity when the entity is standing on a mass=0.0f ground, but non of these have proved to adequate for realistic non snagging movement.

 

Thanks,

 

Mike

Share this post


Link to post
Share on other sites

Could you pass me the values of k, d, and iterations? If k and d are both 1.0 you should reach the exact solution within just one iteration, ie. the moving box is exactly touching but not overlapping the non-moving box and has a tangent velocity of exactly 0.0. Could you check if it really does that, just to make sure everything is okay? You may improve the result by applying gravity as an impulse before the solver, so it can take it into account and get rid of sinking.

 

Cheers,

Mike

Edited by h4tt3n

Share this post


Link to post
Share on other sites

Hi Mike,

 

Just heard another response from Paul. It appears I now may have to take into account something called "internal edges." He was kind enough to provide a link

 

http://www.wildbunny.co.uk/blog/2012/10/31/2d-polygonal-collision-detection-and-internal-edges/

 

I will have another look tonight at what you recommened and these internal edges.

 

 

Thanks for the help!

 

Mike

Share this post


Link to post
Share on other sites

I don't get it. The moving body rests when sitting on two adjacent infinite masses, but doesn't when sitting on two infinite masses joined by an internal edge. It's the same thing.

 

The collision detection is different, so this is 95% chance a collision detection bug.

Share this post


Link to post
Share on other sites

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