🔒 Locked

2-D Physics Engine

Started by L. Spiro Jul 5, 2006 at 12:13 AM 4 replies 1.8k views

Original Post

L. Spiro

1,026

L. Spiro

Jul 5, 2006 at 12:13 AM

This is a common problem, but the search terms for it are far too general, so I can’t find anything. Anyone who has made a generic circle/line physics engine should know of this problem. For now, I am using only circles. Things are 100% perfect if I do not use gravity, and allow things to just bounce off each other. When I apply gravity, things fall down and eventually come to rest on the ground, which I created using a series of more circles that don’t move. The common problem is that, thanks to floating-point errors at such low velocities, the circles are able to slowly melt through the ground and eventually fall through. I would like to know the common methods for defeating this problem. The problem is that when the objects rest on each other (but not embedded), their distances are 0, which in collision detection means they infinitely collide with each other. But I have to allow this because the distance at the time of collision between moving objects is also 0. My first approach: When objects collide, I move forward in time to JUST BEFORE the collision (then resolve their vectors to bounce away), so they don’t cause another collision in the recursive call afterwards. This solved nothing. My second approach: When objects are detected as being embedded, they are pushed out of each other directly away from their center points. So when the circles start to melt into the ground, they are pushed back up, and things are almost flawless because they can only melt when at low speeds, so it does not create a jitter in the object’s path. But the problem is when more circles are introduced. Now Circle A gets pushed upwards, out of Circle B (the ground circle), but Circle C is resting on Circle A, and now THEY are embedded. The routine continues, and then pushes Circle A back down, to unembed it from Circle C. Now it is embedded into Circle B again, which allows it to melt into the ground again. I can remove this by starting the routine over after each unembedding, but this causes tremendous slowdown. Because of the speed issues, the second approach won’t work. So what are other common ways of handling this? Speed is very important because this is going to be running in several PlayStation Portable games, which is not a fast machine. Thank you. YogurtEmperor

Icefox

Jul 5, 2006 at 11:29 AM

I dunno about a common way of dealing with this, but I have a couple ideas that may (or may not) help.

First is that when an object's velocity gets close enough to zero, to just set it to zero. The downside of this is that it makes very very small accelerations meaningless, but if you don't have very very small accelerations, it probably doesn't matter. This may or may not solve the floating-point creep.

Another idea is to sort your list of objects by their Y value, and then do the collision detection from the bottom up. Each object can only collide with the ones to the bottom or sides of it. If you have three objects:

C
B
A

If B falls down so it overlaps A, it'll get pushed back up until it doesn't. This may make it overlap with C, but it doesn't care. Then when C has the collision detection done to it, it'll realize it's overlapping B, and push itself up until it doesn't.

O'course, this is all just me thinking aloud, so there's no guarantee it'll work. Good luck!

L. Spiro

Author

1,026

L. Spiro

Jul 5, 2006 at 10:12 PM

I’m not sure if sorting will work.
Collisions aren’t necessarily done in any specific order—it depends on what collides with what first.
The engine scans for the first collision, steps forward to that point in time (moving all objects by that time step), handles that collision, then goes recursive, starting over, looking for more collisions during the remainder of the time frame.

So sorting won’t make one collision happen before another, unless they both occur at the exact same time, which is next to impossible given floating-point errors.

I’m actually considering changing things to fixed-point math.
Has anyone done this for this type of engine?
One benefit I know is that it will be faster, especially for the PlayStation Portable.
But the main reason I would do it is to eliminate these floating-point errors with small numbers, as they would all be rounded to 0 automatically.

But whether this will solve my problem or not I do not know.
Before I try this, I would like feedback, because this is not a simple modification.
Does this sound reasonable? I’ve rounded small numbers to 0 in a few places already but solved nothing. Maybe I need to do it in more places, or maybe this doesn’t help either way.

Input?

Thank you.
YogurtEmperor

David Bonnet

Jul 6, 2006 at 4:22 PM

I know the problem you have, because i have exactly the same in my 2d physics engine. I don't think going to fixed point math will solve anything. The problem is that the collision impulse depends on the relative velocities of the colliding objects, and when this velocity is null, then the impulse is also null, and the object don't get separated.
Without going too much into the details, in my engine, the amplitude of the colliding impulse was :

f = (1+e)*v / m

where e is the elasticity of the collision, v the relative velocity and m depends on the masses and moment of inertia of the 2 objects.

I changed it to :

f = ( (1+e)*v + k*p ) / m

where p is the penetration distance of the collision and k a factor (0.25 in my case).

This way, when v is zero, the "p" argument make the impulse not null are the object are still separated.

But this quick and easy solution is still not staisfactory to me, because sometimes it make the objects slide on each other when the friction should have stopped them.

Another, more complicated, solution is explained in this document :

http://www.cs.ubc.ca/~rbridson/docs/rigid_bodies.pdf

I have not implmented it yet, but it looks interesting.

david

L. Spiro

Author

1,026

L. Spiro

Jul 6, 2006 at 10:21 PM

I think it will be fine to use your method in my case, but I have only one problem.

I’ve used the book “Mathematics and Physics for Programmers” and it seems to take a different approach to resolving collisions, for the sake of speed.

I have separated the collision resolvers into 4 functions, two of which handle elastic and two of which handle non-elastic.
The two elastic functions just invert the velocity vectors and don’t need to be changed for this problem.

The inelastic ones are set up a different way, and I don’t see where exactly to use your modification.

// =============================================
// Resolve an inelastic collision. Function changes the velocities of the two objects
// based on their masses, the rebound coefficient (fE, from 0 to 1), and the supplied normal.
VOID CPhysics::ResolveFreeElasticCollision( CPhysicsObject * ppoObj1, CPhysicsObject * ppoObj2, FLOAT fE, SS_VECTOR * pvNormal ) {
// If the objects have no mass, error.
if ( ppoObj2->GetMass() == 0.0f || ppoObj1->GetMass() == 0.0f ) { return; }
FLOAT fReb = ppoObj1->GetMass() / ppoObj2->GetMass();
SS_VECTOR vBase = (*ppoObj2->GetVelocityVec());

// vU is the relative velocity.
SS_VECTOR vU;
SS_VECSUB( &vU, ppoObj1->GetVelocityVec(), &vBase );

FLOAT fSq = sqrtf( fE - (fE - 1) * fReb );

SS_VECTOR vUn;
SS_VECCOMPONENT( &vUn, &vU, pvNormal );

SS_VECTOR vUt;
SS_VECSUB( &vUt, &vU, &vUn );

SS_VECTOR vVn = vUn * (fReb - fSq) / (fReb + 1.0f);
SS_VECTOR vWn = vUn * fReb * (fSq + 1.0f) / (fReb + 1.0f);

(*ppoObj1->GetVelocityVec()) = vUt + vVn + vBase;
(*ppoObj2->GetVelocityVec()) = vWn + vBase;

// Both objects are now rebounding.
// Their time-frame vectors need to be recalculated.
}
// =============================================

I imagine
SS_VECTOR vVn = vUn * (fReb - fSq) / (fReb + 1.0f);
SS_VECTOR vWn = vUn * fReb * (fSq + 1.0f) / (fReb + 1.0f);
are the two lines of interest as they calculate the lengths of the resulting vectors, but this is far different from your equations.

How would I fit this in?

Thank you,
YogurtEmperor

David Bonnet

Jul 7, 2006 at 1:00 PM

I think it could be something like :

(*ppoObj1->GetVelocityVec()) = vUt + vVn + vBase + (pvNormal * penetration * k / (fReb + 1.0 ));
(*ppoObj2->GetVelocityVec()) = vWn + vBase - (pvNormal * penetration * k * fReb / ( fReb + 1.0 ));

But the signs may be inverted ( - for Obj1 and + for Obj2 ) depending on the orientation of pvNormal. Here i assume that pvNormal is pointing from Obj2 to Obj1. I assume also that the length of pvNormal is 1.0

david

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.