collisions in physic engine

Quote:

..so there is not penetration between the two balls anymore.. the result is different depending on whether the collision between A and B is treated before the collision between A and C.

You do realize you're making up your own "rules of nature?" Objects do deform on collision (that's where the forces come from), so you may run into problems trying to create a new physics system. Certainly, collisions should not be treated serially ( A+B+C not equal to A+C+B ), but simultaneously.

Suggestion: forget about "gaps" and imitate nature by adding a vector force to each object when it collides with another, without regard to any other collisions. After all collisions have been considered, simply apply F=MA, or, in this case, A = F/M, to all objects, where F is the resultant vector force from all collisions, and A is the vector acceleration. If they interpenetrate momentarily, so be it. I suspect you'll find interpenetration is not a problem.

Quote:

Original post by Buckeye Quote: ..so there is not penetration between the two balls anymore.. the result is different depending on whether the collision between A and B is treated before the collision between A and C. You do realize you're making up your own "rules of nature?" Objects do deform on collision (that's where the forces come from)... Certainly, collisions should not be treated serially ( A+B+C not equal to A+C+B ), but simultaneously.

Actually, most game physics engines simulate rigid bodies - i.e. objects that do not deform on collision, and where the collision is instantaneous. This is a reasonable approximation for objects that deform on timescales smaller than a normal game physics tick. Since there's not really any sense in the idea of multiple simultaneous collisions in a simulation of real world rigid bodies (forget for a moment that they don't exist!), collisions be treated serially. In fact, if you use Newton's law of restitution on more than two objects at once you get the wrong answer (e.g. simulating a Newton's Cradle). If collisions are treated serially then even if they happen within the same timestep then often the order of processing won't make any difference (so long as you iterate enough). When it does make a difference, then whatever order is chosen will still be plausible.

Regarding the original post - you should definitely check out the info in the thread at the top of this forum (list of physics engines and reference material or something like that).

Quote:

there's not really any sense in the idea of multiple simultaneous collisions in a simulation of real world rigid bodies..

I have to disagree with you, MrRowl. If, for example, you consider a sphere colliding with two perpendicular walls at their junction (a concave corner), exactly along the "45," the correct response considers equal (simultaneous) forces from the walls on the sphere. It should return in exactly the opposite direction. If done serially, the sphere will deflect to the right or left as a result of the "first" collision, off-centerline, and the rebound will be incorrect.

Further, if torque due to friction is also being considered (which most physics engines allow), a simultaneous evaluation (equal and opposite torques from each of the two walls) results in no rotation (which is correct). If done serially, the sphere will be given a spin (either CW or CCW) by both collisions and will rebound with an (incorrect) CW or CCW spin.

Because nature is continuous and digital simulation is time-sliced, summing the simultaneous forces, each single force resulting from the depth of penetration for a single collision, at the time of evaluation, yields more realistic results.

If I was the OP, I would listen to the guy who's actually written a simulator :)

Quote:

Original post by Buckeye Quote: there's not really any sense in the idea of multiple simultaneous collisions in a simulation of real world rigid bodies.. I have to disagree with you, MrRowl. If, for example, you consider a sphere colliding with two perpendicular walls at their junction (a concave corner), exactly along the "45," the correct response considers equal (simultaneous) forces from the walls on the sphere. It should return in exactly the opposite direction. If done serially, the sphere will deflect to the right or left as a result of the "first" collision, off-centerline, and the rebound will be incorrect.

If done serially, then both contacts will be considered and iterated over, and in the frictionless case, the ball will bounce straight back, just like if the contacts were simultaneous.

Quote:

Further, if torque due to friction is also being considered (which most physics engines allow), a simultaneous evaluation (equal and opposite torques from each of the two walls) results in no rotation (which is correct).

Yes and no! You're right, of course, that a rigid sphere (hitting rigid walls) when put on that exact trajectory would come back along the same path. However, surely the point of physics engines is to approximate what happens in reality. In reality, the ball will _always_ hit one wall first, because real balls can never be aimed exactly, so will always spin, and never come back along exactly the incoming trajectory. So, an engine that does make it come back along the same trajectory whenever the two contacts happen in the same timestep is actually noticeably implausible. It might do the "maths" better, but it represents the world of non-rigid balls going along not perfectly aligned paths worse.

This is assuming the simulator deals with rigid bodies using impulses (i.e. instantaneous collisions), which is what pretty much all game physics engines do. However, since you mention forces resulting from penetration, that suggests you're thinking of spring/damper models, so we may be talking a little at cross purposes.

I would also make a similar argument about dropping boxes flat onto a floor plane. It always looks unnatural to see the box bouncing up perfectly without rotation - no real box would ever do that.

Edit: Also... in the friction case, what would a rigid body solver do if it solved the collisions simultaneously? For simplicity, assume the restitution is 1 (i.e. the velocity of approach after contact = minus the velocity of approach before contact at each contact point), and it's possible to use Newton's law of restitution on both contact points simultaneously. Also assume the coefficient of friction is infinite. Infinite friction means that the ball surface will be stationary in the tangent plane at each of the two contact points after the collision. However, the only solution that fits the two friction constraints is the ball coming to a dead halt and (a) this is in conflict with the two restitution constraints and (b) it isn't what would actually happen (or is it? Rigid bodies don't really exist of course!).

Edit 2: Sorry for hijacking your thread, OP!

Thanks for your answers!!!

After having read them, I have 2 questions to debate:
1) when there is a collision between 2 balls, do I need to moves them further appart, besides the force they receive???
2) do I need to treat the collisions not serially, if they are severals ones???

I have not tested it, but I think that the answer is "No" for the two questions if the balls are "hard", extremly rigid, so the collision force is great enough to change the direction of the ball instantaneously.

However, I thought of two cases where it could be odd: In my engine, the balls do not have the same rigidity. The more rigid they are, the greater the collision forces are. With my previous exemple, the balls are rigid, so their direction changes instantaneously. With "soft" balls, the collision force are lower, so their acceleration are lower and the direction of their speed does not change instantaneously.

First case, an exemple with weird result if there is no changing of ball positions (the gaps in my topic):
Imagine Ball1 in the middle of the screen and Ball2, coming from the left to collide it. Both are "soft". At the beginning of the collision, the speed of Ball2 decrease, but it still goes to the right, because the collision force is small. The penetration between the 2 balls is greater and greater and then, (OMG!!!) Ball2 is on the right of Ball1 and the collision gives it force to the right. In the real world, Ball2 should stay on the left of Ball1. Here, Ball2 go through Ball1, finishes on the right of Ball1 and the collision gives it speed to go faster on the right!!!
So not adding gap can give weird result???

Second case, an exemple with weird result if the collisions are treated serially:
There is Ball1 in the middle of the screen, Ball2 coming from the left and Ball3 coming from the right. Both are "soft". Ball2 and Ball3 collide Ball1 at the same time. Balls are soft, so the collision should take 1 second. If done serially, the collision between Ball1 and Ball2 puts Ball1 on the right, then the collision between Ball1 and Ball3 puts Ball1 on the left. So at the end, Ball1 is on the left, whereas it should stay on the middle.
So treating collision serially can give weird result???

What do you think about changing balls positions???
What do yout think about treating collisions serially???
Do you think that "soft" balls is a bad idea???

To resume (tell me if I am wrong!!!):
- Buckeye thinks there is no need to change balls positions. The engine should compute all the forces and then update the position and speed with the acceleration due to the forces. With this algorithm, the order of the treated collision do not change the result, so it is not serially.
- MrRowl thinks there is no need to bother with the order of the collisions because the result will be good anyway (but what opinion about changing ball positions???)

I am looking forward to your answers! Thanks!!!

You describe two situations: one with "ideal" rigid balls, the other with "soft" or deformable balls.

In the rigid body case, if, following a collision, you want to move the spheres to a non-intersecting position and then give each one an appropriate velocity, you can certainly do that. You'll have to make up your own rules about how to do that.

With regard to deformable bodies, the scenario you describe, as you realize, is obviously unrealistic. When that happens, you've made some sort of bad assumption. In the case you describe, one sphere passing through another, you assume the force isn't enough to change the sphere's direction which is probably where your problem lies.

As the spheres interpenetrate, what model are you using to generate the force? If you're using only the penetration depth (similar to a spring constant), you can, indeed, run into the situation you describe. But consider that as the penetration depth approaches the diameter of the sphere, either the sphere must shatter or the force must approach inifinity to prevent the spheres from passing through one another.

So, you might want to simulate that type of situation using the concept of strain, perhaps using a force proportional to the (diameter/(diameter-depth))-1. With no interpenetration, the force is zero. As the depth approaches the diameter, the force will approach infinity - sufficient force to change direction! [smile]

Whatever you choose to model, be sure to apply the forces to both (or all) the spheres - for every force there's an equal and opposite force.

EDIT: with regard to serial or simultaneous evaluation of the collisions, that's up to you. Physics engines that I've used (ODE among them) sum the collision forces on each object and apply a single force/torque for that evaluation period to determine the object's new direction/velocity.

EDIT2: By the way, the situation of one object "passing through" another can be acceptable if, for example, you drop a sphere onto a sheet of rubber. The sphere may well drop well below the original plane of the rubber sheet before sufficient force is accumulated to change its direction.

I agree with Buckeye (and I have actually written a simulator [grin]). The deforming+forces+momentum model is the best approach in the long run.

In the tank simulator I made, I use the "moving out of collision" stuff (I hope that's what all the argument is about...). That actually halted the whole thing (I quit the project), because of the corner effect, Buckeye describes. The workaround would be to use iterative collision, or some horrific hacks. The deforming+forces+momentum is more straightforward. (maybe with non-linear (progressive) spring model, so the colliding objects wont act like balloons).
All with fixed time-step of course.

EDIT: I posted again before reading. Pretty much everything is mentioned already.

Quote:

Original post by Buckeye But consider that as the penetration depth approaches the diameter of the sphere, either the sphere must shatter or the force must approach inifinity to prevent the spheres from passing through one another.

OK, I did not think about this. My forces were only linked to the penetration, not penetration/radius. I am going to try it!!!

Besides, if two deformable objects are in collision, it can be a good thing to draw them with penetration.

I did not inform you that I use discrete collision detection (I check if my object is colliding, I do not check if it is going to collide). It is then easier for the fast objects to pass through others than with continuous detection. For example, if I drop a sphere onto a sheet of rubber, it can go on the other side of the sheet!!!

@ Buckeye: do you know if ODE uses the "moving out of collision" stuff???

Thanks!!!