Bullet's Voronoi Simplex Solver

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.9073486e006]
However, the perpendicular to the edge w1w2 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.
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.9073486e006]
However, the perpendicular to the edge w1w2 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.

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Bullet's Voronoi Simplex Solver
Isn't that what Casey is doing in his GJKSAT implementation? So could we adopt his method here?
Cheers,
Dirk
Cheers,
Dirk

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.
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.

 Physics Researcher
 Posts: 23
 Joined: Mon Jun 27, 2005 9:28 am
 Location: Helmond, Netherlands
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.
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.

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
Thanks for your reply Gino.
So we should ensure that distance decreases and that a CSO vertex is not revisited. 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 nondegenerate. 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.
So we should ensure that distance decreases and that a CSO vertex is not revisited. 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 nondegenerate. 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.

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Bullet's Voronoi Simplex Solver
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
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

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Bullet's Voronoi Simplex Solver
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...

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
For 2D, we can find the sign of the search direction by computing the sign of a cross product:
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.
Code: Select all
cross(w2  w1, w1)
You can view the cross product as the signed area of a triangle. In 3D, we can use the signed volume of a tetrahedron.

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Bullet's Voronoi Simplex Solver
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
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

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.
In my example the origin is about 2cm away. We shouldn't be having numerical problems at this distance.

 Posts: 875
 Joined: Sun Jul 03, 2005 4:06 pm
 Location: Kirkland, WA
Re: Bullet's Voronoi Simplex Solver
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
Cheers,
Dirk

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.

 Posts: 324
 Joined: Fri Jul 01, 2005 5:29 am
 Location: Irvine
 Contact:
Re: Bullet's Voronoi Simplex Solver
The implications of Gino's noisy search directions causes some further trouble. Essentially, this makes GJK nonconvex. 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.
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.
Re: Bullet's Voronoi Simplex Solver
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 raycast 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 illdefined 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 raycast, 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 closesttopolygon 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 axisaligned to within some threshold. This essentially triangulates the box face, but it didn't cure all the problems. I suspect things are numerically becoming nonconvex  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.
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 raycast 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 illdefined 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 raycast, 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 closesttopolygon 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 axisaligned to within some threshold. This essentially triangulates the box face, but it didn't cure all the problems. I suspect things are numerically becoming nonconvex  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.
 Erwin Coumans
 Site Admin
 Posts: 4232
 Joined: Sun Jun 26, 2005 6:43 pm
 Location: California, USA
 Contact:
Re: Bullet's Voronoi Simplex Solver
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.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 raycast hits the back side of the box instead of the front.
Can you create a reproduction case, and report it in the issue tracker?
Agreed, unit tests would be great, contributions are welcome.p.s. Bullet could really benefit from a good automated test library.
Thanks a lot,
Erwin