Question about collision resolution

There are many ways to approximate physics. None of them are 'right', they are all approximations of what we observe in reality. The first looks more traditional, like what you might learn from Physics for Game Developers. It looks to be primarily based on applying impulses to correct collisions. The second also does this, but it's more based on inserting constraints. Think of an imaginary spring attached to the two bodies, at their furthest intersection point.
None of this happens in "real life". In real life, each individual particle of matter is colliding and responding to forces. It's important to understand that even the physics taught in books/school is a _model_ of reality. It's not what _actually_ happens, it's a model to make predictions that are close enough for us. Infact, there are many such models (trig based newtonian, calculus based newtonian, grid based (ig: naiver-stokes) fluid dynamics, lagrangian (ig: SPH) particle based, and we use whichever fits our particular need at the moment. There are usually tradeoffs. I started with a lagrangian-type method from this white paper: Advanced character phsyics. There are even different ways to compute the results. Vector math, matrices, trigonometry.

I would recommend reading and trying several different methods.There are also really good, and easy to use engines out there. Such as Box2d, chipmunk, bullet, etc... I wrote mine based on that white paper, then incorporated a model for bounce and friction (adapted from N), then used concepts I learned from box2d to improve my broad-phase collision detection, etc...

Hope that helps, and isn't too overwhelming. I know it's troublesome, but once again, I would recommend trying/learning a few. Each one becomes easier than the last. Good luck, Happy Coding!

Both approaches uses the Sequential Impulses techique developed by Erin Catto. More one this topic:

http://box2d.org/downloads/

The difference between them is that in the first approach the resolver corrects position errors by changing the position of the objects directly. This is called solving a position constraint.

The second approach doesn't solve a position constraint. Instead it stabilizes it by transforming position errors into velocity errors. This is called constraint stabilization.

Both are correct ways of handling collision resolution. But the first one doesn't introduce artificial energy into the system. Therefore it is better than the second approach and commonly used in rigid body simulation for games. The first approach is used in Box2D. Anyone would recommend it to check Box2D.

4 hours ago, Irlan Robson said:

Both approaches uses the Sequential Impulses techique developed by Erin Catto. More one this topic:

This is not using sequential impulses. It is using the naive impulse method.

The second looks like a derivative of Catto's resources.

5 hours ago, phenom120 said:

I'm currently implementing a 2D physics engine, then i stuck in collision resolution. So i did a search in google, and i found this passage, It explains how to use impulse to separate two objects.

But after that, i found another another passage, this article is very complicated, but they seem talking the same thing ——— how to implementing the collision resolution. So now, what i confuse is why are there two completely different approaches of collision resolution? What's the difference between them? Which approaches is right?

I am not a native english speakers, so i hope you can understand what i wrote.

Thanks.

Here is the eventual result of the first link you posted https://github.com/RandyGaul/ImpulseEngine

The second article is nearly the same thing, except a little more is added. They are using a more abstract mathematical strategy to derive the same exact equation. However, the more abstract strategy makes it clear how to extend the first approach with more features.

The main feature is to include impulse accumulation, caching, and clamping. This feature transforms the first article into a full-blown Gauss-Seidel solver, which can converge. This means you will get nice stacking behavior.

Also the abstract mathematical strategy can be used to derive more equations for different behaviors, and this is called "constraints", to simulate specific things like prismatic or revolute joints.

So how can you go from the first article's strategy (naive impulse method) to the second (constraint method)? You need a few things.

1. Impulse accumulation
2. Impulse clamping
3. Impulse caching

You can do 1 and 2 simultaneously, but 3 will require additional work.

Here is some sample code for the naive impulse method in your first article. And here is some sample code for the sequential impulse method. After comparing them side by side it is easy to see a few key differences. Here is step 1 and step 2. The accumulation for step 1 is stored here. For every collision there is one arbiter. The arbiter persists between simulation ticks in order to implement step 1, and to do this step 3 is required. Step 3 is implemented by keeping the arbiter around from one simulation tick to the next. Here is where Arbiter lifetime is implemented.

This piece of the naive method is completely replaced by step 1 and 2. The naive method throws away negative impulses. However in practice negative impulses are extremely important for convergence and correct overshoot when solving multiple contacts simultaneously. Only the accumulated impulse needs to be clamped above 0 in order to ensure the constraint does no work (d'Alembert's princple), or in other words, projection onto the constraint plane.

This hack completely disappears from the naive solution.

The friction model changes, though is still based on Coloumb's law. In your second link friction is modeled with a constraint almost entirely the same as the contact (collision) constraint.

And finally, this piece here is replaced by Baumgarte stabilization. Baumgarte is just an additive term, that was pre-calculated up here. There isn't much to Baumgarte since it's so simple. You calculate the position error of the constraint, and then take a small factor of it (like 0.2) and feed that directly into the velocity constraint (be careful to scale it by dt properly).

I found all these differences by comparing the impulse engine github repo with Catto's Box2D Lite github repo. I suggest anyone else curious about evolving from the impulse method to the sequential impulses method to compare these two repositories.

To figure out how to derive the differences between the repositories, then go to box2d.org/downloads. Erin Catto has documented his derivation very well in his earlier GDC lectures. Erin had a background where he understood classical mechanics, and then noted that his strategy of clamping and caching the accumulated impulse was equivalent to a Gauss-Seidel matrix solver, thus mathematically proving his strategy to be a good one.

The naive impulse strategy was used for many years before Erin's materials were published, and at the time other people were using similar strategies to Erin, but it was all more or less difficult information to find and learn about (or just plain kept secret). For example, we can see back in 1995 the same equations popping up in Chris Hecker's nice magazine article. These equations will be found in Erin's resources, but expanded upon after arriving at them from a different strategy with more abstract math.

I mentioned the SI technique since both works seem to be based on Catto resources.

In general if you implement this for multiple bodies you will end up with a technique that applies impulses to the bodies sequentially solving constraints.

1 minute ago, Irlan Robson said:

I mentioned the SI technique since both works seem to be based on Catto resources.

In general if you implement this for multiple bodies you will end up with a technique that applies impulses to the bodies sequentially solving constraints.

Yes I know, and that was a good assumption, but the first is just the naive impulse method, and there's quite a leap to be made to get to Erin's method if you want to understand the derivation. But just modifying the code is actually pretty trivial.

My last post is showing how easy it is to go from one method to another in code, despite the very different derivations.

Kenny's PhD thesis is a good introduction to this topic if you have the required level of mathematics. It contains a summary of some of the different rigid body simulation paradigms.

http://image.diku.dk/kenny/download/erleben.05.thesis.pdf

5 hours ago, Randy Gaul said:

This is not using sequential impulses. It is using the naive impulse method.

The second looks like a derivative of Catto's resources.

Here is the eventual result of the first link you posted https://github.com/RandyGaul/ImpulseEngine

The second article is nearly the same thing, except a little more is added. They are using a more abstract mathematical strategy to derive the same exact equation. However, the more abstract strategy makes it clear how to extend the first approach with more features.

The main feature is to include impulse accumulation, caching, and clamping. This feature transforms the first article into a full-blown Gauss-Seidel solver, which can converge. This means you will get nice stacking behavior.

Also the abstract mathematical strategy can be used to derive more equations for different behaviors, and this is called "constraints", to simulate specific things like prismatic or revolute joints.

So how can you go from the first article's strategy (naive impulse method) to the second (constraint method)? You need a few things.

1. Impulse accumulation
2. Impulse clamping
3. Impulse caching

You can do 1 and 2 simultaneously, but 3 will require additional work.

Here is some sample code for the naive impulse method in your first article. And here is some sample code for the sequential impulse method. After comparing them side by side it is easy to see a few key differences. Here is step 1 and step 2. The accumulation for step 1 is stored here. For every collision there is one arbiter. The arbiter persists between simulation ticks in order to implement step 1, and to do this step 3 is required. Step 3 is implemented by keeping the arbiter around from one simulation tick to the next. Here is where Arbiter lifetime is implemented.

This piece of the naive method is completely replaced by step 1 and 2. The naive method throws away negative impulses. However in practice negative impulses are extremely important for convergence and correct overshoot when solving multiple contacts simultaneously. Only the accumulated impulse needs to be clamped above 0 in order to ensure the constraint does no work (d'Alembert's princple), or in other words, projection onto the constraint plane.

This hack completely disappears from the naive solution.

The friction model changes, though is still based on Coloumb's law. In your second link friction is modeled with a constraint almost entirely the same as the contact (collision) constraint.

And finally, this piece here is replaced by Baumgarte stabilization. Baumgarte is just an additive term, that was pre-calculated up here. There isn't much to Baumgarte since it's so simple. You calculate the position error of the constraint, and then take a small factor of it (like 0.2) and feed that directly into the velocity constraint (be careful to scale it by dt properly).

I found all these differences by comparing the impulse engine github repo with Catto's Box2D Lite github repo. I suggest anyone else curious about evolving from the impulse method to the sequential impulses method to compare these two repositories.

To figure out how to derive the differences between the repositories, then go to box2d.org/downloads. Erin Catto has documented his derivation very well in his earlier GDC lectures. Erin had a background where he understood classical mechanics, and then noted that his strategy of clamping and caching the accumulated impulse was equivalent to a Gauss-Seidel matrix solver, thus mathematically proving his strategy to be a good one.

The naive impulse strategy was used for many years before Erin's materials were published, and at the time other people were using similar strategies to Erin, but it was all more or less difficult information to find and learn about (or just plain kept secret). For example, we can see back in 1995 the same equations popping up in Chris Hecker's nice magazine article. These equations will be found in Erin's resources, but expanded upon after arriving at them from a different strategy with more abstract math.

It is quite useful, thank you.

So, can i consider the first approach as a simplified approach of the second approach?

And I don't know what is sequential impulses, Is it another approach of collision resolution?

It's the name of the second approach

1 minute ago, Randy Gaul said:

It's the name of the second approach

Thanks. I just realized that you are the author of first article

And yes, the first approach is a simplified version of the second approach. It is missing key features needed to avoid jittering and to let shapes stack nicely in piles.