Minkowski Portal Refinement (MPR) for 2D

[zzzzrrr]

Hello,

I've been working on a narrow phase collision detection method that folks may be interested in for the 2D case. It's based on the Minkowski Portal Refinement Algorithm (MPR), developed by Gary Snethen, and featured in Game Programming Gems 7.

I've created a small applet to demonstrate the concept:
http://code.google.com/p/mpr2d/
You can also find more information here:
http://xenocollide.snethen.com/

I've started work to incorporate it into my physics engine, Blaze, which is based on Chipmunk and Erin Catto's Sequential Impulse (SI) method.
http://www.dsource.org/projects/blaze

As it stands, I think I have a fairly solid implementation. I'm sure there are other optimizations that can be made, so maybe I can draw some interest/help from other experienced people. Ideally I would like to extend this method to include some sort of hybrid GJK/MPA routine for continuous collision detection (CCD). I there is a lot of potential here...

Take care,
Mason

[zzzzrrr]

MPR2D is now featured in the Blaze physics engine for polygon-polygon collision detection.

You can download the demo here: http://svn.dsource.org/projects/blaze/d ... -Demos.zip

Press SPACE to see contact points, or 'B' for AABB info.

MPR2D Home:
http://code.google.com/p/mpr2d/
Blaze Home:
http://www.dsource.org/projects/blaze

Blaze was born from the Chipmunk Physics engine, which uses Erin Catto's SI solver....

Feedback is appreciated!

~Mason

[zzzzrrr]

CCD in my little 2D engine is fairly solid. In it's current form, I'm using MPR for penetrations and GJK for distance.

Check out demo #9. Inject high speed block-bullets with the mouse.

http://svn.dsource.org/projects/blaze/d ... -Demos.zip

Cheers,
Mason

[Erwin Coumans]

Nice demo,

I assume you are using Brian Mirtich's convervative advancement for CCD, just like Bullet subsimplex/gjk/rotational query, Gino's gjk convex cast, fast and catch, and more recently Box2D ccd?

Thanks,
Erwin

[raigan2]

It would be great if someone could explain their CCD process in a bit more detail; I still don't understand how you avoid doing n^2 tests: finding the earliest collision requires a full collision pass, which tests everything vs everything.. and since a full pass is required after each collision (to find the next earliest collision) you either end up with a lot of tests, or you need a complicated scheduling/contact graph/island system.

[Erwin Coumans]

It would be great if someone could explain their CCD process in a bit more detail; I still don't understand how you avoid doing n^2 tests: finding the earliest collision requires a full collision pass, which tests everything vs everything.. and since a full pass is required after each collision (to find the next earliest collision) you either end up with a lot of tests, or you need a complicated scheduling/contact graph/island system.

Most approaches (Brian Mirtich, Gino vd Bergen, Stephane Redon, Young Kim, me, Erin Catto to name a few) are performing following steps when doing continuous physics (CP)

• kinetic broadphase based on swept AABBs reducing n^2 pairs to smaller number of potential overlapping pairs
  Kinetic broadphase examples are timewarp, kinetic sweep and prune and discrete broadphases with swept AABBs
• CCD: compute the smallest time of impact fraction for a pair of moving objects
• CP: advance small groups of objects to the next time of impact.

Mirtich's Timewarp explains the idea of merging and splitting simulation islands. It tries to localize the proceeding (or rolling back) time of impact events, rather then handling discontinuities globally.

There are various simplifications and shortcuts that improve performance.

• You can cheat by only moving objects to the earliest time of impact, and loosing the rest of the frame. This can result in a visual slow down.
• Avoiding splitting and merging islands by using a conservatively large island, based on temporal bounding boxes that includes the maximum allowed motion within one timestep.
• Allowing for a reasonable penetration reduces the number of potential splits/merge considerably. This means performing CCD on smaller enclosed objects. This usually gives enough play room in contact situations.

I discussed this with Erin Catto, and I think he implemented such approach in Box2D.

Have you tried implementing any of this?

zzzzrrr, do you following a similar approach? Can you share some experiences?
Thanks,
Erwin

[raigan2]

Thanks; I have implemented CCD for rope, and it works well, but was simplified by the fact that I'm treating the rigid bodies as read-only until the next frame. Having the rope's topology known (like having a non-changing contact graph/island) also simplifies things.

Here's a single simulation step:

-advance rigid bodies and rope
-generate rigid body collision constraints
-solve constraints (including rope collisions generated last frame)
-generate rope collision constraints (CCD)

Rigid collisions aren't swept, I'm instead generating constraints for any potential collisions (by looking one step into the future, as well as proximity in the present) and then only solving them if they're violated. This involves doing a bit of collision detection in the solver (determining if a point lies within the voronoi region of the feature it's constrained to).

It's working well, but it's much slower that Box2D, which is depressing. The voronoi tests are very simple, it seems like the performance problems are more caused by the fact that I have dozens of extra constraints to deal with.


One of the reasons I've avoided full CCD is that I'm not proficient enough to able to implement a performant sweep-and-prune broadphase (currently I'm using a very simple grid-based system).

More importantly, my solver is position-based, which causes two problems:

1) CCD as you describe it implies a velocity-level solver, because bodies are advanced to the first collision, the collision is solved (by altering velocities), and then we move in. It's not clear to me how CCD would work in the context of a position-based solver, other than by generating constraints (which will all be solved together), which is how my current scheme operates.

2) Since the position of objects is modified with each solver iteration, this can generate collisions.. so some sort of conservative/predictive/pessimistic generation of potential collision constraints is needed anyway.


The final complication is the fact that my system can't deal with penetration.. which is something I swore I would never attempt, since penetration always seems to happen anyway, but was sort of forced into: I needed concave-concave collision (which is working great in the current system) and none of the penetration-based methods I tried worked very well. More importantly, my swept-rope collision completely fails if there's any penetration (imagine in 2D a rope wrapped around a square, and having a vertex of that square pass through another square's corner.. the rope becomes "tangled" on the second square's corner).

I'm extremely reluctant to leave my solver since it's quite magically stable!

[Erwin Coumans]

1) CCD as you describe it implies a velocity-level solver, because bodies are advanced to the first collision, the collision is solved (by altering velocities), and then we move in. It's not clear to me how CCD would work in the context of a position-based solver, other than by generating constraints (which will all be solved together), which is how my current scheme operates.

There should be no difference between 1st order velocity-level or 0-order position-level constraint solving in combination with CCD and CP. In both cases, at the time of impact, a discontinuity happens and contact constraints have to be solved, and the direction of motion typically changes. This means the time of impact queue needs to be recomputed for objects involved. So even with velocity-level solving the position and velocity of objects involved change. Why do you think that position level differs?

2) Since the position of objects is modified with each solver iteration, this can generate collisions.. so some sort of conservative/predictive/pessimistic generation of potential collision constraints is needed anyway.

Predictive generation of contacts is exactly what CCD is about: it gives you the next time of impact and contact points. This means you simply simulate up to the next toi. So if we assume that CCD provides this information, what exactly is the problem?

The final complication is the fact that my system can't deal with penetration.. which is something I swore I would never attempt, since penetration always seems to happen anyway, but was sort of forced into: I needed concave-concave collision (which is working great in the current system) and none of the penetration-based methods I tried worked very well. More importantly, my swept-rope collision completely fails if there's any penetration (imagine in 2D a rope wrapped around a square, and having a vertex of that square pass through another square's corner.. the rope becomes "tangled" on the second square's corner).

Shallow penetration should not cause issues, but it is possible to combine CCD with zero-penetration. Doom 3 and later idSoftware games use zero penetration, in combination with some clever rules between objects that are in contact. Jan Paul van Waveren provided me a paper and further information that will be part of a chapter on continuous collision detection in my upcoming book. In practice of several games we found it works very well to allow a little bit of penetration. Especially in contact situation, allowing a tiny bit of penetration reduces the number of TOI events dramatically.

I'm extremely reluctant to leave my solver since it's quite magically stable!

Is your system 2D or 3D? If 2D, how does stability compare to Box2D?

Thanks,
Erwin

by the way, concave-concave collision deserves its own topic. Bullet's penetration-based method seems to work pretty well in actual games, including for concave objects. For better quality I would recommend using convex decomposition. It is possible to use 3D concave triangle meshes in Bullet and ODE (like GIMPACT etc), but it convex decomposition gives better stability and contact information. Havok and Ageia PhysX also avoid concave triangle meshes in favor of convex decomposition.

[raigan2]

There should be no difference between 1st order velocity-level or 0-order position-level constraint solving in combination with CCD and CP. In both cases, at the time of impact, a discontinuity happens and contact constraints have to be solved, and the direction of motion typically changes. This means the time of impact queue needs to be recomputed for objects involved. So even with velocity-level solving the position and velocity of objects involved change. Why do you think that position level differs?

The problem is the "contact constraints have to be solved" part -- at the TOI, you _can't_ solve position constraints because they aren't violated!! I may be boneheadedly missing something.. my understanding is that CCD with a velocity-level solver is iterative, with each pass through looking something like this:

-advance to TOI
-solve collision (modify velocity of 2 objects)
-continue (i.e calculate next TOI/interacting pair)

As you said, rather than solving the collision, you can add it to a list and solve it together with the other constraints.. the problem is that since the velocities aren't changed, objects still pass through each other (before the solver step, during the "generate constraints" swept-collision step) and this incorrect movement can generates other constraints which should never exist, and which cause problems (fighting each other or "ghost" collisions between two non-touching objects).

The only solution I could find is to perform some simple collision-type queries, which is where I am currently. The other alternative was, as you mentioned earlier, to just move to the time of first impact and stop, however this tends to undermine one of the big advantages of this solver, which is that it supports large mass ratios (1:100).. if you stop at time of first impact, you get heavy objects stopped dead by tiny ones. Probably some rule-based solution might work, but I gave up on it.

I think a better approach might be to use a velocity-level solver for the CCD part (again, I might be totally wrong about what everyone else is doing, but AFAIK this just means cancelling the velocity of the contact point along the collision normal).

Predictive generation of contacts is exactly what CCD is about: it gives you the next time of impact and contact points. This means you simply simulate up to the next toi. So if we assume that CCD provides this information, what exactly is the problem?

As I mentioned, the problem is that you can't actually do anything useful at the TOI, since the error is at the velocity level.

Shallow penetration should not cause issues, but it is possible to combine CCD with zero-penetration. Doom 3 and later idSoftware games use zero penetration, in combination with some clever rules between objects that are in contact. Jan Paul van Waveren provided me a paper and further information that will be part of a chapter on continuous collision detection in my upcoming book. In practice of several games we found it works very well to allow a little bit of penetration. Especially in contact situation, allowing a tiny bit of penetration reduces the number of TOI events dramatically.

I definitely agree that being able to deal with some amount of overlap is important, since it _always_ happens in practice (especially when you're not a numerical computing genius). My system can handle penetration in that objects which are penetrating will be pushed out of each other, BUT only if collision constraints were generated before they were penetrating (i.e using distance queries, not penetration-depth). So far this works great, and lets us handle concave shapes -- the only problem being the usual super-thin + super-fast-rotating objects, in which case my predictive collision generation fails (since it's a linear approximation).

Is your system 2D or 3D? If 2D, how does stability compare to Box2D?

2D; I actually haven't been able to build Box2D for about a year (at some point Erin changed something which broke compilation under code::blocks and it's never worked for me since.. plus I haven't had the energy to fight with stupid c++ build crap) so I'm not sure about the recent state, but it's much better behaved than the split-impulse solver for articulated bodies.

The main thing is that you don't need to tweak anything, it just converges -- you can randomly position the objects and they'll snap together, without any "only move things by X amount per iteration" type hacking -- and it can handle large mass ratios. I don't know about stacking -- friction is still being figured out -- but for articulated characters it's great.

It's the Muller PBD-solver, applied to rigid bodies. I'm not an expert on numerical solvers, but I _think_ it's a non-linear solver, similar to "damped least-squares fit". At least, the third formula on this page looks very similar to the formula presented in the PBD solver: http://en.wikipedia.org/wiki/Gauss-Newton_algorithm

One great thing I've noticed is that if the situation is impossible (i.e a chain of bodies with the two ends anchored too far from each other) it doesn't explode/oscillate like the impulse-based solvers tend to do, it just gets as close as it can to a solution.

by the way, concave-concave collision deserves its own topic. Bullet's penetration-based method seems to work pretty well in actual games, including for concave objects. For better quality I would recommend using convex decomposition. It is possible to use 3D concave triangle meshes in Bullet and ODE (like GIMPACT etc), but it convex decomposition gives better stability and contact information. Havok and Ageia PhysX also avoid concave triangle meshes in favor of convex decomposition.

[/quote]

My main gripe with convex decomposition is that it assumes static/rigid shapes, and we're trying to do very fluid, morphing vector shapes. We've even got some "skinned physics" working -- collision geometry verts can be bound (with different weights) to multiple bones, and constraints involving the geometry will correctly adjust the bones' states. Not sure if this is super-useful/needed though

The main issue we're running into is the software-engineering side -- it's really difficult for us not-great-coders to figure out a nice system which hides everything, so that the solver doesn't care whether things are skinned or rigid, and just treats everything generically as a big pile of DOF and constraints involving the DOF.

[Erwin Coumans]

As I mentioned, the problem is that you can't actually do anything useful at the TOI, since the error is at the velocity level.
[...]
BUT only if collision constraints were generated before they were penetrating

We have dealt with this in some games by generating 'future' contact/non-penetration constraints that happen at the time of impact. So they are generated before bodies are penetrating, perhaps similar to some of Trinkle-Steward approaches.

Have you considered this?

the only problem being the usual super-thin + super-fast-rotating objects, in which case my predictive collision generation fails (since it's a linear approximation).

You could try to linearize the rotation too, and project/combine linear and angular motion. This conservative advancement CCD approach is described in Mirtich's PhD thesis, and more recently in the 'Fast' and 'Catch' papers by Zhang/Kim et al. But again, you will need to allow some penetration, otherwise you get stuck into a 0 time-of-impact situation.

My main gripe with convex decomposition is that it assumes static/rigid shapes, and we're trying to do very fluid, morphing vector shapes.

I got not much experience in deformable objects, but that might change: we are adding a softbody contribution to Bullet for upcoming version, dealing with rope, cloth and deformable volumes. This approach differs significant from PBD, but softbody versus softbody collision detection is still work in progress.

Thanks,
Erwin

[raigan2]

We have dealt with this in some games by generating 'future' contact/non-penetration constraints that happen at the time of impact. So they are generated before bodies are penetrating, perhaps similar to some of Trinkle-Steward approaches.

Have you considered this?

I'm not sure what you mean by "happen at the time of impact" -- once you reach that point in time while moving things forward during CCD, you start solving those constraints?

What I'm doing is very similar to the Steward-Trinkle stuff I've read (from what I understand). Sadly it's also as slow -- especially for "round" shapes made of many tiny faces.. too many constraints get generated.

If you simply mean using CCD queries in order to generate constraints for collisions which _may_ occur during the next/current frame, this is what we do. My problem with this is that it's slow in two ways -- one, you're generating a lot of constraints that never need to be solved (even if you early-out during processing, you at least need to calculate the current value of the constraint function) , and also you can't just solve all of these constraints since many of them don't make sense (i.e objects are far apart: during prediction they passed through each other so a constraint was generated, but now that we're solving, other constraints/collisions have kept them from following the predicted path).. so you need to do some collision/geometric query type stuff to ensure it still makes sense to apply the constraint, which makes them more expensive. Plus, the rules for determining whether a constraint makes sense are very "ad-hoc".

At least, this is my theory for why Box2D is much faster when it comes to collision. If there's some way to use a position-level solver during CCD in the same way that velocity-level solvers are used, I'd really like to hear about it!

[Erin Catto]

raigan: The issues you state illustrate a big problem with position based systems. You have to allow the system to violate the position constraint before you can apply any correction. Correct me if I'm wrong, but you can't prevent penetration, you can only try to measure it without missing something. This makes the whole problem much more nonlinear than velocity constraints, which are linear by definition.

In a velocity based system the position corrections should be much smaller and therefore are typically close to being linear.

[raigan2]

That makes sense.. I guess I'm just screwed!

[pcm2008]

Hi,
I've recently discovered MPR as a collision detection/ penetration depth algorithm. I think it's good but I think the original paper for 2D (from XenoCollide) has a flaw.
Take a look at this image from the 2D applet. It looks like the MPR has problems with long objects.
I think the problem is the refinement step. I don't think that one should choose the portal that contains the origin as the refined portal. Most likely one should choose the portal that has the property: the projection of the origin on the portal is contained in that portal. Try and rerun the steps of the algorithm for this case and see where the MPR starts to go wrong.
The reason I think the projection rule should be used is that if the origin is contained in the Minkowski sum (difference) then the shortest distance (penetration distance) will ALWAYS be a projection of the origin to one of the exterior edges, for the 2D case.
This rule might alter the ability of the MPR to also detect if two objects penetrate but one could use GJK to detect if the objects penetrate (very fast) and then use MPR for penetration distance/direction.

[Xeno]

Hi,
I've recently discovered MPR as a collision detection/ penetration depth algorithm. I think it's good but I think the original paper for 2D (from XenoCollide) has a flaw.

Maybe I can help. What is the actual problem you're seeing?

I'm having trouble interpreting the image you provided. Can you explain how the image demonstrates the problem?

---Xeno (Gary Snethen)
http://xenocollide.com