MPRToolbox precision

Discuss any questions about BEPUphysics or problems encountered.
Post Reply
ashkatchap
Posts: 4
Joined: Sun Feb 03, 2019 4:30 am

MPRToolbox precision

Post by ashkatchap »

Hi

I'm learning physics programming using this library and others, and I encountered problems with MPR. Afaik MPR should be correct enough for any shape pair as long as it is not too big (from the point of view of a float and operating with it).

I changed slightly some files so that all collisions are handled by MPR instead of using GJK as an optimization to avoid using MPR by changing:
- Inside `NarrowPhaseHelper.cs`, the collisionManager for any pair of shapes is replaced with `Factories.ConvexConvex`.
- Inside `GeneretalConvexPairTester.cs` changes to use always `DoDeepContact` instead of using sometimes `DoShallowContact`.

After doing this changes strange things happen, like shapes jumping or going through another ones even when they were resting still on top of another shape. This happens when any shape is large enough (500 or 1000 units in any side is enough for this to happen).

For example, with a big flat static box as a ground (size 1000x1x1000) and a small box (size 1x1x1), when the small box is on top of the big one near its center or halfway to its sides, it behaves correctly, but if the small box ends up close to the sides of the big box, it goes through it.

If my understanding is correct, this should not happen even though this would be a difficult bug to trigger because of the required changes to make the bug happen continually.

Do you know what could be the cause of this problem, or how to fix it? Thank you
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: MPRToolbox precision

Post by Norbo »

A single run of MPR can be thought of as a ray cast against the inside of a convex shape (which is actually a minkowski difference in collision detection). The surface normal returned by a centroid->origin cast in minkowski space is not guaranteed to be a global minimum or even a local minimum for penetration depth. With shapes that are reasonably close to cubes and small depths, this is almost never an issue as the potential hit surface for the ray has the same normal as the minimum.
cubelikempr.jpg
cubelikempr.jpg (5.6 KiB) Viewed 10506 times
But as the shapes become stretched out and as depths increase, it becomes more likely that the ray cast doesn't find the ideal normal.
notcubelikempr.jpg
notcubelikempr.jpg (11.67 KiB) Viewed 10506 times
With a normal pointing in the wrong direction, the collision constraint can't stop penetrating motion and the object can easily fall through.

In the deep contact case, you might notice that it does multiple iterations of depth finding MPR. At least one additional cast from the origin along the normal is required to compute the depth along the previously found normal; it just does does a couple of extra iterations in an attempt to bounce the normal over to something closer to the minimum. It doesn't work consistently, though, and it can't do anything in the above case. (I only did it since it was relatively simple and the cost wasn't too high for a deep penetration routine that rarely runs.)

(It turns out there are some other minkowski space approaches that can avoid the pitfalls of MPR/GJK for collision detection. For v2 I experimented for quite a while and found a quasigradient descent, something that looks a little like MPR's portal finding stage that converges to a local minimum (plus some GJK-ish stuff to handle separated cases), and what I actually ended up using, something that looks a little like GJK but without a full simplex distance execution and generalized to penetrating cases.

I haven't seen these described before and I haven't written up the details yet so figuring them out could be a little bit tedious- I should probably do that at some point. Just in case they actually are novel, I hereby name the algorithm used by the depth refiner "tootbird search" because I want to see future research with the word tootbird in it.)
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: MPRToolbox precision

Post by Norbo »

(and of course, there may be other issues at play too- by virtue of being so rarely called, v1's deep contact routine has been subject to less inspection.)
ashkatchap
Posts: 4
Joined: Sun Feb 03, 2019 4:30 am

Re: MPRToolbox precision

Post by ashkatchap »

Really thank you a lot, for such a detailed explanation and your solutions present in v2.
I want to try v2 in my computer, but both of them (one with an integrated gpu that can only run dx10, and the other with a more modern Radeon R9 380, both using Windows 7) are unable to run the demo because of an exception when initializing the graphics, apparently a problem with SharpDX. That is a problem for another day, though.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: MPRToolbox precision

Post by Norbo »

and the other with a more modern Radeon R9 380, both using Windows 7
Hm, that's odd- that should work. It's possible I pulled in some win10 dependency in the demos along the way without realizing.
ashkatchap
Posts: 4
Joined: Sun Feb 03, 2019 4:30 am

Re: MPRToolbox precision

Post by ashkatchap »

After a lot of work implementing SAT and learning from it (and learning that even with edge culling using GAUSS it is still slow for convex-convex, but fast for spheres and cylinders, at least faster than MPR) I remembered something from your useful post, so after coming back here and reading it again slowly I was able to make MPR work by calling it a second time with a different set of centers in the case of oblong shapes. I wasn't able to understand the code you are made, that is very probably faster, but I'm glad of being able to "fix" the penetration and normal issue of MPR just by calling it an extra time when needed.

The idea is:
  1. Run MPR once and get a collision point. Check how oblong are the shapes by checking the ratio between the smallest and largest axis of the minimal bounding box of each shape. I consider a shape oblong if largestAxis/smallestAxis>2. If both shapes aren't oblong, end here.
  2. Using the minimal bounding box of the shapes , get the smallest axis of that box and "resize" the box, using the collision point from the first MPR run as the resizing origin, so that all axis are equal to that smallest axis.
  3. From that resized shape, obtain its center and run MPR again with the original shapes, but with this new centers (that will be inside the original shapes). End here.
This time MPR has a better hint of where the normal should point at, and after testing this I wasn't able to obtain a wrong normal.

The 2 in largestAxis/smallestAxis>2 is eyeballed, I don't know of a good heuristic or math that could give a better number to avoid executing MPR a second time when it isn't needed.

It would be good to be able to speed up the second MPR run somehow, but I'm ok with this. It would be even better to understand the algorithms you made, but without graphics or an explanation it would be difficult because of maths.

Thanks you a lot.
Last edited by ashkatchap on Mon Apr 15, 2019 10:56 am, edited 2 times in total.
Norbo
Site Admin
Posts: 4929
Joined: Tue Jul 04, 2006 4:45 am

Re: MPRToolbox precision

Post by Norbo »

The 2 in largestAxis/smallestAxis>2 is eyeballed, I don't know of a good heuristic or math that could give a better number to avoid executing MPR a second time when it isn't needed.
One iffy option: for shape pairs with smoothly differentiable surfaces, you can analytically differentiate the pair depth function (dot(normal, support(A, normal) - support(B, -normal))). If the derivative is zero for the found normal, you're at a local minimum. Of course, almost no shape pairs are that nicely differentiable, but you can numerically approximate it by sampling the depth function at a few discrete normals around the MPR-found normal. If they're all no better than the MPR normal, then you're at a local minimum. That could be reasonably quick for shapes with fast support functions, though I'm not sure if it would end up being a net win overall. And it won't help in situations where the MPR-found normal is a local minimum, just a bad one.
It would be good to be able to speed up the second MPR run somehow, but I'm ok with this. It would be even better to understand the algorithms you made, but without graphics or an explanation it would be difficult because of maths.
Hopefully I'll get around to a proper explanation blog post in the not too distant future- probably after v2 releases.
Post Reply