Feature: Provide api for Stuck Inside problem resolving

[Hexlord]

Expected behavior: Box2D api provides ways to fight Stuck Inside problem in general case (post-triangulation). Actual behavior: there is no way to achieve that with current Box2D api. Proposed solution: Let us mark duplicate edges as ghost, preventing their collisions from happening. This requires preparing input data (finding duplicate edges), but according to Box2D Stuck Inside solution testbed demonstration video this approach seems to work well.

The code changes are located in this branch: https://github.com/erincatto/box2d/compare/master...Hexlord:hexlord/box2d_compound_problem_draft

API is changed to allow for such parameters to be passed to polygon shapes. Compound Shapes testbed is changed: third table and third spaceship demonstrate the new approach.

There are probably some caveats I am missing, as I know little about physics simulation, but the idea was to reject duplicate edge collisions. I search for the most early spot to implement this, to limit performance impact, but I am sure there are better ways to implement it.

Also, probably, a better approach, is to allow dynamic bodies with non-closed loop of vertices, but I did not look into implementing this, I am sure its generality-breaking and would raise complexity of the physics logic, which I know little of.

[erincatto]

I think this is a cool idea. How does it handle a case like this?

I'm concerned it will early return and not push the smaller box to the left.

[Hexlord]

@erincatto Ok, just tested this. It looks perfectly fine. I tried rotating the right plank 180 deg in hope it could break something, still works fine. Gist: https://gist.github.com/Hexlord/a76a9b13249e31854769c42a35a061f2

Right pair of boxes (which form a single body) is different: bottom box has its top edge marked as ghost.

Also moved planks futher from center, still works fine.

Also without right plank rotation, just in case (works fine):

[Hexlord]

I just realized the right box falls through the ground, how could I miss this... I will take a look again tomorow after a proper sleep, sorry. But this ain't looking too good.

I would guess that ghost edge ignoring collision is to be narrowed to other collision's edge being on the side of normal direction, or go higher level and restrict body ghost edge collision count, or match identical edge collisions by their hash and prevent hash collision on that level.

One more idea: marking the neighbor of ghost edge also, with some double sided collision flag, making its normal work both ways, but probably still preventing stuck inside fighting. Doubt this could work though, as solver operates on per shape basis(or smth like this, as I understand it), it would not find doublesided edge of top box when resolving bottom box edges collision.

[erincatto]

Thanks for looking at this. My concern is that there are edge cases that lead to wrong behavior. Perhaps instead of an early return we need to use the next best face.

[Hexlord]

Ok, thanks for the inside. I actually never realized the fact that I introduced early out, I totally meant to only discard duplicate faces. After the fix, which removes early out, there seem to be no more problem with going through the ground, but table case is no longer resolved as effectively, because another face is being chosen which preserves double direction fighting.

Anyway the code changes are available in the branch: https://github.com/erincatto/box2d/compare/master...Hexlord:hexlord/box2d_compound_problem_draft

So now I am thinking is it worth it: it kinda helps - ship case is resolved, and table case is helped with, but the way it is achieved is non trivial for users of box2d. I am going to try it out in my project over some large period of time and check if there are any more problems.

I will also keep thinking about other approaches, but the very case of polyA edges colliding with polyB edges from both sides of polyB means that we are inside it, but we could never find out which side to resolve this penetration to. We could maybe subtract centroids for the direction, but any complexity in the body fixture combination immediately breaks this approach, just like Convex Hull.

I wish CPU could handle CCD for all body simulation and I would never get inside someone without spawning there :)

One more thing: in Warcraft 3 custom map named Castle Fight, one could block creeps with towers, preventing them from ever going to the war with the enemy castle. The fix to this by the map author was to make creeps temporarily ignore collisions after 60 seconds of being stuck. Crazy thought: maybe if bodyA transform relative to collisionee bodyB transform is somewhat constant, and we somehow detect that one is inside the other one (free (not inside bodyB) vertices of bodyA connections intersect bodyB), make bodyA ignore bodyB until collision with bodyB ends. It is not a truly physical simulation aspect, but so is being stuck :)

[erincatto]

Well my blog post shows how to solve the problem. Just overlap the collision.

It would be interesting to develop an algorithm for convex decomposition that also labelled internal edges and the collision algorithm handled this.

On that note, I'm going to lump this in with #513.

[Hexlord]

I was actually taking a closer look at https://youtu.be/SDGMcoA-Lt0?t=74

It is switching back and forward resulting in those forces

Maybe (keeping the ghost edges feature) preventing quick change of equation (solution) of constraint resolvement (at least when position is almost constant/velocity almost zero) would allow this to be resolved one way or another.

I will test it out when am able to. I still hope for a simple yet effective improvement :D

[Hexlord]

So I looked up some info regarding constraints, including your wonderful GDC talk, and am able to formulate my thoughts on the being-stuck problem a bit more clearly:

In a game scenario, where geometry is a triangulated non-convex polygon, which allows not the workaround described in your blog, one would think that the problem could be solved by arbitrating the fight between opposite constraints - for example, by introducing a new constraint, which regulates not the position nor velocity, but the effectiveness of the constraints themselves: so that the longer the fight, given the body is considered stuck, the more effectiveness shifts towards one of the polarities (effectively disabling some part of the constraints).

So we have our linear solver, iterating dozens of physical contraints. Then we have our other layer, (added on top just like the position constraint was added on top of the velocity constraint), some not-being-stuck constraint, but it does not search for a root, it just slowly decides which half of constraints to disable:

Move currently active constraints' polarity (property inside mapping of body to involved constraints) towards Positive (+1), over time see whether the other half of constraints becomes active, in that case move their polarity towards Negative (-1) (we need to polarize so that we can decide which half to disable but also preserve the ability to obtain more constraints as we go). So basically the first to be active takes the Positive side, and when Positive side' constraints are inactive we move currently active constraints towards Negative. We also slowly move polarity towards 0 for everyone (to recover from configuration changes), especially when body is not stuck. Now we just multiply corresponding physical constraints effect by (polarity / 2 + 1).

So it is important to determine a body being stuck, so that our logic only affects simulation (and affects polarity) when it has to: and I was hoping to achieve it just by the time component of polarity accumulation: given there are strong constraints on both ends, we consider ourself endlessly fighting between two constraints if Max(polarity) - Min(polarity) == 2 (or move away from normalization and use some constant threshold), so at that moment we consider ourselves stuck and disable half the constraints (or do it slowly over time, moving their effectiveness towards 0 just as the polarity changes).

Stacking involves constraints of different bodies, so in that case the lower body (the one being pushed down by another body) would have in first timestep its bottom constraints as active and Positive, then its top constraints would push it down not to overlap with the body above moving themselves towards Negative, then again bottom would push it up not to get stuck in the ground ever rising polarity difference. But the important detail is that those constraints are related to different body pairs. We manage our polarity state on per-body-pair basis, so in that case the ground always pushes us up, so only polarity is positivity in bottom part of the body. And another state is our positivity in our upper part of the body from the constant pressure of upper body. No negative polarity, no consideration of being stuck.

Mapping of body to constraints is actually islands in box2d: each constraint points to bodyA and bodyB, so we can put the polarity state into b2Body as a map of <pair<otherIsland, constraint_uid>, polarity>. We could hack-in constraint_uid by some hash function of its partial state (given contact index does not change), or we could use integer generator for unique constraint instantiation (which seems to contradict current implementation). Overall I think it is a solvable issue.

I hope I will try to implement those ideas when I get enough time, maybe they are absolute nonsense and I just lack important knowledge, but at least I've tried :)