Bullet's Voronoi Simplex Solver

Please don't post Bullet support questions here, use the above forums instead.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

I found another problem with my GJK implementation in Box2D.

Say the current simplex is a line segment:
w1 = [0.021119118, 79.584320]
w2 = [0.020964622, -31.515678]

Using Cramer's rule we get the barycentric coordinates of the closest point on the segment to the origin:
alpha1 = 0.28366950
alpha2 = 0.71633053

And we get the point closest to the origin:
v = [0.021008449, 1.9073486e-006]

However, the perpendicular to the edge w1-w2 is:
perp = [111.10000, -0.00015449524]

Note the sign of v.y and perp.y do not agree. In my test case, using p to find the next support point gives the wrong answer. Using the perpendicular gives the correct answer.

Using the closest point p as the search direction for the support point fails. IMO, there is no need to use the closest point as the search direction. Instead we should use the normal vector on the current feature.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Bullet's Voronoi Simplex Solver

Post by Dirk Gregorius »

Isn't that what Casey is doing in his GJK-SAT implementation? So could we adopt his method here?


Cheers,
-Dirk
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

Yes, Casey is using this technique to find the search direction.

It is still unresolved if we need to compute the closest point to converge the distance algorithm for polytopes. As Gino has pointed out, it may be enough to detect a repeated support point.
gino
Physics Researcher
Posts: 22
Joined: Mon Jun 27, 2005 9:28 am
Location: Helmond, Netherlands
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by gino »

What you are suggesting is when only polytopes are used, you can do without the closest point computation, or at least you can skip all intermediate closest point computations and keep only the final one. Termination can be governed by detection of a repeated support point (vertex of the CSO, not vertex of either polytope!). The last found simplex before the bad support point is the final simplex containing the closest point.

I've never tried this but I suspect that this scenario can go bad in the following way: Suppose your simpex is close to being affinely dependent (a needle). The normal computed from this needle is noisy and shoots off the support point to a vertex of the CSO that has not yet been returned but is nevertheless a bad one. I have seen this happening for near contacts of objects that differ greatly in magnitude. The algorithm continues using this bogus support point, and finds a support point that has been returend earlier. Now, the simplex with the bogus support point is returned as final simplex.
In 2D, the chances of a perp vector suffering from cancellation are not so linkely, so you could get away with it in 2D. The sketched scenario is very real for 3D, since here the normal is computed from a cross product which can be very noisy.

In my code, I do compute the closest point and use its squared distance to the origin as upper bound. Each new iteration should reduce the squared distance by a significant amount (squared distance times the machine epsilon). If it does not, then GJK terminates. This approach is fool proof, since any bad support point will trigger termination.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

Thanks for your reply Gino.

So we should ensure that distance decreases and that a CSO vertex is not re-visited. I like this better than using a tolerance. I've seen cases where the tolerance was too loose and GJK terminated prematurely. If we tighten the tolerance than we starting getting duplicate vertices. So it seems there is no point to the tolerance based termination for polytopes.

I also got some premature terminations from the length tolerance. This is now unnecessary when the search direction comes from a face normal on the simplex. Here we should simply verify that the simplex is non-degenerate. I'm curious if it is possible for the simplex to become degenerate given the other termination conditions and the nature of GJK.

Finally, I've noticed a case where GJK cycles between 3 vertices. Therefore, I think we need to store the entire history of vertices to check for duplicates. I store the vertices by index pair, so this check is quick and exact.

Edit: storing the history is not appropriate, I've found cases where this leads to early termination. Therefore, we can only check to see if the new simplex is different than the previous simplex. Other types of cycling will be caught by ensure the distance decreases. I think we can use the distance decrease criteria exclusively, but it is a bit more expensive because it requires an additional simplex solve.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Bullet's Voronoi Simplex Solver

Post by Dirk Gregorius »

But how do I know the orientation of the search direction? Let's assume I have a triangle simplex ABC and the associated normal n = AB x AC. Now the origin can either be below or above the triangle. So the search direction can either be n or -n. Do I have to additionally test on which side the origin is located?

Also when creating the triangle normal Gino pointed out lately that it is numerically more robust to choose the two shortest edges to build the cross product. What about the edge case. Any suggestions here as well?

Cheers,
-Dirk
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Bullet's Voronoi Simplex Solver

Post by Dirk Gregorius »

Maybe we can also share degenerate test cases to test our GJK implementations. Erwin has such a test case contributed by Pierre in the extras folder. It would be great to have a small suite of pathological cases. So if you want to share them I could make them available somehow...
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

For 2D, we can find the sign of the search direction by computing the sign of a cross product:

Code: Select all

cross(w2 - w1, w1)
The sign tells us if the origin is to the left or right of the face. If the cross product is zero we can pick an arbitrary sign knowing that the distance won't decrease.

You can view the cross product as the signed area of a triangle. In 3D, we can use the signed volume of a tetrahedron.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Bullet's Voronoi Simplex Solver

Post by Dirk Gregorius »

Ok, so we need to find the direction in an extra step. But why is this numerical more robust than projecting the origin onto the segment w1->w2? Is there a reason or is this just luck. Also the cross product is not really numerical friendly, right?

Also, if I understand the presented problem correctly the origin is actually very close to the segement w1->w2. Shouldn't we detect such cases and take this as a hint?


Cheers,
-Dirk
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

In my example, numerical error comes when interpolating on the line segment to find the closest point (via Cramer's rule and barycentric coordinates). The signs of the cross products are correct. I encourage you to write a test program using the numbers a I provided above. In 2D, computing the face normal is exact: (x, y) -> (y, -x). I suspect that in 3D we are better off using cross products to find the search direction than using the results of Cramer's rule.

In my example the origin is about 2cm away. We shouldn't be having numerical problems at this distance.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Bullet's Voronoi Simplex Solver

Post by Dirk Gregorius »

In your example the segment is basically parallel to the Y axis and two cm away from the origin. The direction from the closest point calculation points incorretly slightly down, while the perp vector points slightly up. So what is actually going wrong in you simulation? I assum that when using closest point you get w2 again and terminate, because you don't get any closer. Using perp might give you a new support point which moves you closer to the origin if I assume that you have some needle like simplex. Is this happening or what goes wrong and why does using the perp helps with this in general and not just in this specific case?

Cheers,
-Dirk
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

Yeah, it picks the wrong support point and terminates prematurely. The simplex is just a line segment. I guess you could call that a needle.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erin Catto »

The implications of Gino's noisy search directions causes some further trouble. Essentially, this makes GJK non-convex. If the distance increases can we assume that the previous distance was the minimum? If not, then this hypothetical case is not solvable by GJK. If the previous distance was the minimum then we need to store the previous simplex for our result.

Perhaps we need to detect the degenerate simplex and compute better search directions. For example, we can treat a degenerate triangle as a point or line segment.
langford
Posts: 2
Joined: Mon Jul 06, 2009 2:39 pm

Re: Bullet's Voronoi Simplex Solver

Post by langford »

Glad to see there's active discussion in this area. Bullet collision detection leaks like a sieve!

I create a box primitive and shoot a ray from an interactive camera I can fly around. Things look good until I apply a slight rotation to the box, then there are *many* missed detections or wrong detections, e.g. the ray-cast hits the back side of the box instead of the front.

I spent quite some time stepping through this, and it seems the problem is almost exactly in the area you guys are discussing.

It seems the support map is basically ill-defined for a quad (box) shape, so I'm not sure how the algorithm is supposed to work at all... but basically what happens is that when iterating a ray-cast, the converged contact point will have a closest distance to the box that is perpendicular to the quad face. In this case the support map function could return any of the four quad faces as being "closest". That is exactly what happens is that the algorithm of determing and rejecting the simplex point wanders around these four points as it attempts to converge. It often gets "lucky" with an answer, but sometimes the following happens:

It picks up four simplex points, all the points of the quad. The code does not properly detect this degenerate simplex (a planar quad). and then rejects two of the simplex points. This causes the code to fall back onto thinking the simplex is a line (it is not) thus kicking the iteration of closest-to-polygon point onto the line (not in the triangle where it belongs), and thus *increasing* distance from previous iteration and causing the code to bail out. (I think the code bailing out is just a bug, but the fix to this entire problem isn't trivial).

I tried one fix of modifying the support function to return the center of the plane when the direction was axis-aligned to within some threshold. This essentially triangulates the box face, but it didn't cure all the problems. I suspect things are numerically becoming non-convex - I think someone already mentioned that here.

I hope you guys have a fix soon!

Jacob

p.s. Bullet could really benefit from a good automated test library.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Bullet's Voronoi Simplex Solver

Post by Erwin Coumans »

langford wrote:Bullet collision detection leaks like a sieve!
I create a box primitive and shoot a ray from an interactive camera I can fly around. Things look good until I apply a slight rotation to the box, then there are *many* missed detections or wrong detections, e.g. the ray-cast hits the back side of the box instead of the front.
There are no such collision problems reported in the issue tracker. Raycasting is not using GJK, but directly the support map in combination with conservative advancement.

Can you create a reproduction case, and report it in the issue tracker?
p.s. Bullet could really benefit from a good automated test library.
Agreed, unit tests would be great, contributions are welcome.
Thanks a lot,
Erwin
Post Reply