Culling? Duplicate Impulses during Collision Resolution.

Started by
8 comments, last by Irlan Robson 8 years, 4 months ago
I have a physics engine that I am making that is using Newtons Law of Restitution to calculate impulses (article here: http://chrishecker.com/images/e/e7/Gdmphys3.pdf for those curious). As of now, I am only calculating a response using restitution along the normal of the collision.
My problem happens when the following situation occurs:
AABB C, with a velocity that moves it (up) in the diagram, receives two collisions that have different actors (A and B) but identical responses.

    +-----+  +-----+
    |  A  |  |  B  |
    +-----+  +-----+
    
       +--------+
       |   C    |
       +--------+
AABB C's velocity after collision resolution is twice what it should be.
How should I approach this problem? One option that I have come up with would be to average all collisions with AABB's that are on the same axis. Another could be to simply ignore all but 1 collision on an axis. But which collisions do I ignore/keep?
What do you guys/other engines do?
If it helps, here is my current, very rough, physics loop:

SpaceUtil.stepVelocities(_bodies, gravity, dt);
SpaceUtil.stepPositions(_bodies, dt);
Collision.updateBounds(_bodies);
var collisions = new Array<CollisionInfo>();  // I know, I know.  You should see the rest of the code :D
Collision.collideBodiesMany(_bodies, collisions);
Arbitrator.prestepCollisions(collisions);
Arbitrator.applyImpulses(collisions);
Collision.separateMany(collisions);
SpaceUtil.applyImpulses(_bodies);

Also, I would be very surprised to find this is the first this question has been asked but I can't find a previous post. If you know of one, please link me!

Advertisement

Once the first collision is processed, the box is now moving away from both A/B so the second collision would automatically be ignored.

Not sure how rotation would affect it...

'Proper' physics engines probably collect all contact points and only then solve for it.

edit:

No idea really I probably shouldnt have even posted ph34r.png

o3o


AABB C's velocity after collision resolution is twice what it should be.

Just to be sure, you mean it is 4x the velocity it would be with only a single collision?

Tristam MacDonald. Ex-BigTech Software Engineer. Future farmer. [https://trist.am]

Well, it won't be twice what it should be if you update the velocity of C after you do Solve( A, C ), and then do Solve( B, C ). The solutions you solve for will invalidate one another to varying degrees since you haven't implemented a scheme that can converge to a global solution.

Some solutions would be to use the "shock propogation" idea that uses a contact graph to solve layers one at a time. You can find information about this in that one "Non-convex stacking" paper. The current state of the art is to implement a seidel solver, which Catto has written a lot about in terms of his "Sequential Impulses". Resources by Catto et. al are over at Box2D.org, but be warned the rabbit hole can go quite deep.

It ends up with 2x the velocity it should have. If there were 3 simultaneous collisions, it would have 3x the velocity.

Solution: scale each collision response by a factor of 1/n when you have n simultaneous collisions.

This requires that you find all the collisions first, then do the resolutions as a separate step afterwards, so you know what n is for each object before you start adding any forces.


AABB C's velocity after collision resolution is twice what it should be.

Just to be sure, you mean it is 4x the velocity it would be with only a single collision?

No it is actually 2x because the identical impulse is applied twice.

Well, it won't be twice what it should be if you update the velocity of C after you do Solve( A, C ), and then do Solve( B, C ).

Yes that is correct. I implemented the loop the way I did because that is how I think I am reading some of the major engines loops. I can't really think of a reason that I shouldn't just do it the easy way though.

Also, thanks for the Impulse Engine articles. Extremely helpful.

Once the first collision is processed, the box is now moving away from both A/B so the second collision would automatically be ignored.

Not sure how rotation would affect it...

'Proper' physics engines probably collect all contact points and only then solve for it.

edit:

No idea really I probably shouldnt have even posted ph34r.png

Hah, you are actually spot on with your first statement. I'm not processing the collisions immediately but I'm going to give that a go here in a minute.

It ends up with 2x the velocity it should have. If there were 3 simultaneous collisions, it would have 3x the velocity.

Solution: scale each collision response by a factor of 1/n when you have n simultaneous collisions.

This requires that you find all the collisions first, then do the resolutions as a separate step afterwards, so you know what n is for each object before you start adding any forces.

This is actually how my engine's step function works now, collide all then resolve all. I looked into scaling the collisions as you say but it seems to be a very specific solution to a very specific problem and I'd hope to avoid that situation. Even looking at the major engines, as well as I can understand the code, I am not seeing a resolution to this specific issue.

It ends up with 2x the velocity it should have. If there were 3 simultaneous collisions, it would have 3x the velocity.

Solution: scale each collision response by a factor of 1/n when you have n simultaneous collisions.

This requires that you find all the collisions first, then do the resolutions as a separate step afterwards, so you know what n is for each object before you start adding any forces.

Assuming the OP is using some math he got from Chris Hecker, impulses are solved from the relative velocity between each body, and configuration. This means your statements about 2x and 3x velocity are 100% incorrect. These equations are not just blindly applying forces. This means that scaling solved impulses by 1/n doesn't really make sense at all in the context of the Hecker equations in that article, and is not physically based.

PeterStock, you're mathematically and practically incorrect. Your approach doesn't have any relationship with constraint-based/impulse-based/position-based dynamics. And repulsive impulses don't depend of the velocities as a whole. Read page 227 of this paper if you want to get an approximate idea of what an happens during iterations:

http://www.cs.cmu.edu/~baraff/papers/sig89.pdf

It is an old paper but it is the foundations. And if you want to solve for friction then you can definetly forget about applying (infinite) forces. Always use velocity based approach for games. Of course you an apply forces individually to bodies before the velocity update (out of the solver).

I believe Chris Hecker has mentioned in his papers only a single contact point and body. For a single contact point then he is correct. Otherwise what Randy said is correct.

You just can't expect a good and fast rigid body simulation by neither applying impulses individually nor applying repulsive forces. You should implement an iterative velocity-based constraint solver instead in order for you to solve your problem. Of course this doesn't means that you will be creating large matrix equations. I mean, you can do that if you want, but this is quite impractical and difficult to debug for games in my experience.

If you are really very interested in this I recommend:

Read Erin Catto's resources.

Implement your engine based on Box2D Lite.

Parse Box2D to match your current engine's needs.

Not taking the "impulse" word in consideration, Chris Hecker's math on this post is very different from what Catto's uses, and as was said you probably will have to increase your math (specially calculus) knowledge if you think is not sufficiently when reading these resources.

There are well-known solutions for rigid-body dynamics for games currently. I don't know if we can come up with an algorithm that can cause a big impact that won't be affecting the game performance crucially since the best way of doing something at run-time is by definetly not doing. Maybe in engineering an approach like that might get some attention IMHO.

I have a physics engine that I am making that is using Newtons Law of Restitution to calculate impulses...
...
C, with a velocity that moves it (up) in the diagram, receives two collisions that have different actors (A and B) but identical responses.

Whatever you do, remember this: Newton's Law of Restitution is only correct (and even then it's only a law) for collisions between two particles (no rotation).

In practice, you can apply it to a single contact between two objects that can rotate. I'm not sure if this gives you physically correct behaviour, but it will look fine.

In practice you can apply it to multiple contacts between a pair of colliding objects. Again, I suspect this doesn't give you physically correct behaviour, but it will look fine.

In practice you can apply it to multiple contacts between more than two objects (i.e. simultaneous collisions) so long as the coefficient of restitution is zero. You can use this to solve for resting contact.

However, if you apply it to multiple contacts between more than two objects with non-zero coefficients of restitution, then if you enforce that law for all contacts simultaneously, you'll get implausible results. Just work through the example of a Newton's Cradle, which is similar to your example. If you apply the restitution law to pairs of contacts sequentially then you'll get plausible results, though (a) the exact result will depend on the order in which you process the pairs and (b) you may not get complete convergence in a sensible/finite number of iterations.


In practice, you can apply it to a single contact between two objects that can rotate. I'm not sure if this gives you physically correct behaviour, but it will look fine.

That is physically plausible for a single contact point (e.g. sphere and plane).

(For beginners) Found this very basic slide that should help to understand (page 35):

http://gdcvault.com/play/1018160/Physics-for-Game

For a box and plane, for instance, things get tricky since other points may affect the others.

This topic is closed to new replies.

Advertisement