Hey All, Im looking at writing a simple 2d impulse solver, but I have a question. Usually the problem formulation is to find all contact points, set those up as constraints, and find impulses to push objects away using PGS. My question is, when we do this, we may create new collisions when we choose some impulse to resolve a collision, but the iterations of PGS wouldn't know about it since we arent rechecking collisions on every iteration to add these new constraints to our system. Is this a expected result? It seems odd to me that the math formulation wouldn't guarantee that we would have a collision free frame even if we solved our system of constraints perfectly, since the newly applied impulses can create new constraints that we didnt have before. Am I misunderstanding something in the formulation?

D.V.D said:
It seems odd to me that the math formulation wouldn't guarantee that we would have a collision free frame even if we solved our system of constraints perfectly, since the newly applied impulses can create new constraints that we didnt have before.

Assume we add a collision test for each solver iteration, we still have cases of potential intersections. E.g. If we put many small boxes into one large hollow box, but the summed volume of the small boxes is larger than the volume of the empty space in the hollow box. Or some ragdoll has it's lower leg in front of a thin wall, but it's upper leg on the back. The joint at the knee might pull the bodies together stronger than the contact separates them. We can construct many examples where things will go wrong, and it's not possible in practice to prevent such cases from happening.

Many of those cases can be explained by the artificial idea of ‘rigid’ bodies. They can't break, they can't compress. Such thing does not exist in reality, so we can't expect to get realistic results in any case from this model.
My goal here would be the simulation converging at a resting state, but allowing penetrations. The bodies should not jump around or jitter like hell even if constraints remain violated.

D.V.D said:
a simple 2d impulse solver

That's the problem. There are good solutions to highly constrained systems of contacts, but they're not simple. Look up “LCP solver”.

On detecting object overlap, you can cut the time step in half and retry, which can get you out of the kind of situations you describe. But not in fixed time. In some situations the physics frame rate may have to drop.

Often this isn't a problem, if you're just blowing up stuff. You can tolerate some bogus interpenetration.

@JoeJ, so I understand that we can construct such cases like a box that contains rigid bodies but doesn't have room for them, but if we ignore such cases, we still get problems in environments where we do have a infinite amount of space to work with. Like when you just have a bunch of bodies fall, then there is enough space for all of them every frame but the “perfect” solution that solves all the constraints in a given frame isn't actually guaranteed to be intersection free.

@Nagle For the LCP solver, does it rely on us specifying the constraints and then finding a solution to that? My reason for asking is that to me it feels like the problem specification is the issue here, not the PGS solver.

I guess my overall question is, why is the problem specified in a mathematical sense not actually a perfect solution? For example, in graphics we have the rendering equation which is the “perfect” solution to lighting and GI but we know we can't simulate it directly so we approximate it. For physics, I thought that the perfect solution would be the constraint vectors/matrices and then us solving the system of equations this generates so that all our constraints for a given frame are solved. This does not appear to actually be the case since solving this system perfectly doesn't result in a collision free solution. Is this a accurate description of the situation? Is there a way to specify the problem mathematically where this isn't the problem? For reference, my understanding of how the problem is specified comes from this post: https://www.toptal.com/game/video-game-physics-part-iii-constrained-rigid-body-simulation

IMO the difference is that the rendering equation doesn't have as much “feedback” in the calculations: the light might bounce around a bunch, but it's not moving anything when it does so, which makes the problem easier.

AFAIK there's no known way to solve more than a single simultaneous collision perfectly. See this article for a great overview of the problem, and some imperfect solutions: https://www.myphysicslab.com/engine2D/collision-methods-en.html

Not to mention, the whole premise of impulse-based solver is you're using linear approximations of the constraints -- that means even if you *did* perfectly solve the system of impulses, you'll inevitably have penetration/errors because of the inherent errors due to the approximation. And finally, the type of solvers typically used to find the impulses are themselves iterative and approximate by nature! So IME it's better to find method(s) you can use to correct the error/penetration, trying to completely avoid it in the context of a game sim is very hard.

(I think Doom3 used a "never let things overlap" approach, however the fact that this wasn't widely adopted by Bullet/Havok/etc. suggests that there are some bad tradeoffs to such an approach.)

See this thread for some discussion on handling-vs-avoiding penetration: https://pybullet.org/Bullet/phpBB3/viewtopic.php?p=460

And this thread about some ways to deal with penetration: https://pybullet.org/Bullet/phpBB3/viewtopic.php?f=4&t=11675&p=39301&hilit=penetration#p39301

D.V.D said:
why is the problem specified in a mathematical sense not actually a perfect solution?

Because impulse/constraint physics has discontinuities. Either you have contact, or you don't. An infinitesimal movement can change the contact situation. So trying to solve the system by numeric hill climbing is not sufficient.

If you do spring/damper physics, with actual contact forces, this can be avoided. You have to have multi-point contact, so you don't get that teetering-between-two-contact points discontinuity when a cube lands on a flat surface. Now you have a system where you can hill-climb along the gradient until the error becomes infinitesimal and the objects are in a valid state. The compute load is higher, you have to cut the step size to tiny values at the beginning of a collision, and so it's hard to do in real time.

Thus, you can have accurate physics or constant-time physics, but not both.

Here's my original spring/damper ragdoll, from 1997. This is spring/damper for the contacts, has multiple contact points between pairs of bodies when necessary, and, uses Featherstone's algorithm for the character. The time step is cut until an error measure on the integrator indicates that the time step is short enough that a linear approximation is valid.

Nobody does it this way any more. But it's sound and stable.

This may be the first successful ragdoll demo.

D.V.D said:
For physics, I thought that the perfect solution would be the constraint vectors/matrices and then us solving the system of equations this generates so that all our constraints for a given frame are solved.

That's much harder than your example of the rendering equation. For rendering we can assume our geometry to be static and constant for the duration of our frame.
No longer the case for physics: Here everything changes, including the ‘relationships’ between bodies, e.g. a contact. And we don't know about future relationships, so we can't have a single and compact system of equations to represent all relations. I use the word ‘relationship’ because i forgot the proper word - maybe it was ‘bilateral’ joint, meaning a contact joint which has no effect once bodies separate from each other.

A similar situation is joint limits. A hinge joint may violate it's limit or not, and again we don't know all states our joint might have during the frame.

So we have two options:
1. Order all events (like a collision) sequentially in time, so we can update our system of equations every time it changes. We will get a correct solution. But in case of paradox situations like my boxes example, the solver would get stuck in an infinite loop. And worse: Worst case will have much higher computational cost than average case.
So that's interesting mainly if you can guarantee your number of bodies remains small.
2. Treat all events as simultaneous and lasting over the whole (sub)frame. Gives only an approximation, but we can bound the error by our timestep.

(I just see there's already a similar answer)

@raigan Thanks for the link on resolving collisions, I haven't realized that this was such a hard problem for rigid bodies to be honest and it helped put that in perspective with the examples (seems to be similar to what @nagle was mentioning). I agree that we are better off handling penetrations gracefully rather than enforcing they cannot happen due to computational constraints, I guess a lot of this is more theory for me. But you did mention that even if we solved the system of constraints, you would have penetrations due to the constraints being approximations. My argument is you would have penetrations even with perfect constraints since we are only adding constraints to the matrix for objects that collide, but the resolved positions might still collide with objects they didn't previously collide when we setup the matrix.

@joej has mentioned this as well, but the difference between the rendering equation and collision responses is that our geometry changes as we resolve more collisions (or at least positions and orientations do, so it feedbacks onto itself). I agree that this is the case, I think from @joej ‘s post, my working idea was the second option of treating all events as simultaneous and lasting for the whole frame. If we treat them this way, can we build a system of equations that guarantees its solutions won’t penetrate after it is solved. My working idea on how to do this would be the following;

• Represent all geometry of each object as some sort of equation (maybe a SDF?)
• Add n^2 penetration constraints for each object vs all others such that each object doesn't overlap (we need the equation/SDF here to specify the constraint)
• Solve this matrix

The above can be done for small demos with simple geometry I think pretty easily if our geometry is a circle since then we can specify penetration constraints without a contact point. The part that was confusing me is that the source code on github I was seeing for physics engines don't appear to try to approximate this. Instead, they do the following:

• Find all collisions in the scene
• Specify a constraint for each collision/contact point in our matrix
• Solve the matrix

This was confusing me because solving the above does not guarantee you don't have collisions in a particular frame, even if the matrix is solved perfectly. You would need to represent all your geometry as some sort of math equation so that you can use it to write out a constraint that doesn't rely on having a contact point. So if object A collides with object B, resolving this contact point might make object B now collide with object C which it wasn't colliding with before so its constraint wasn't in our matrix when we solved it. So the physics engines I see on github are sorta “distributing” this computation across frames, and hoping that overtime, we won't have new collisions created as we resolve contact points since things will stabilize. It makes sense to do it this way, but I guess I was surprised this was the case.

Thanks everyone for the info! I hope I correctly reiterated how this all works in the above.