[Feature Request] Returning Additional Information

[magicbycalvin]

I am wondering if you would be able to optionally return additional information from the GJK algorithm. Some useful data includes:

1. Tolerance (assuming you implement a tolerance stopping condition)
2. Number of iterations
3. Weights for the vertices*

The weights for the vertices are the most important for my current application. By weights, I mean the point between two vertices that is the closest. For example, given a line segment AB and a triangle CDE, let the point C be closest to the halfway point between points A and B. The weights of the vertices returned would then look something like [(0.5, 0.5), (1, 0, 0)]. Similarly, this could happen in 3D, let the triangle ABC be equilateral, with its center on the origin, and whose points all lie on the plane z=0. Let a point D be at (0, 0, 10). It is clear that the minimum distance between the point and the triangle would then be 10. The weights of the vertices returned would then look like [(0.33, 0.33, 0.33), (1)]. Hopefully that makes sense?

I have yet to read through your publication but it is my understanding that the original GJK algorithm utilizes these weights to some degree. If it is easy enough for you to return that information, that would be fantastic. If it is not, could you point me in the right direction to modify your existing code and eventually create a pull request?

Thanks!

[MattiaMontanari]

This is similar to #2 as the weights are the barycentric coordinates. However, the way to implement this correctly requires more referencing and data cache that I avoided to keep the code faster. Also, the separating vector is in general not unique and this may cause problems in to the applications. For these reasons, I decided not to included this feature.

However, you can easily add it: The coordinates are stored here, the paper shows how to link these to the witness points.

You'll see that the distance sub-algorithm returns the subset of points whose barycentric coordinates are greater than zero. The points with zero or negative barycentric coordinates are discarded from the simplex. So, in your example, rather than [(0.5, 0.5), (1, 0, 0)] you'll get [(0.5, 0.5), (1)]. Knowing these and the associated vertices (hence the data cache) you can compute the separating vector between the objects.

[magicbycalvin]

Excellent, thank you! I will look into that.

[maaaaadn]

To the ones previously asking for witness points. Did you implement this extra already and would like to share your contribution? Otherwise, I'll try my luck as well.

[nyers33]

With commit 'f2871569f529413e55251dc794398ebf58bcd5e5' you can access the lambdas (barycentric coordinates for each vertex) and the points from P & Q that form the simplex. Somehow these are not available in more recent commits. And the code for calculating the witness points is:

dd = gjk (bd1, bd2, &s);

// witness points
double wOnA[3];
double wOnB[3];

wOnA[0] = 0.0f; wOnA[1] = 0.0f; wOnA[2] = 0.0f;
wOnB[0] = 0.0f; wOnB[1] = 0.0f; wOnB[2] = 0.0f;
for (int idx = 0; idx < s.nvrtx; idx++)
{
    wOnA[0] += s.p[idx][0] * s.lambdas[idx];
    wOnA[1] += s.p[idx][1] * s.lambdas[idx];
    wOnA[2] += s.p[idx][2] * s.lambdas[idx];

    wOnB[0] += s.q[idx][0] * s.lambdas[idx];
    wOnB[1] += s.q[idx][1] * s.lambdas[idx];
    wOnB[2] += s.q[idx][2] * s.lambdas[idx];
}

I haven't tested it too much but works fine for the tutorial sample.

And my issue: somehow the code doesn't return the correct witness point when one of the input object is a single point (distance is correct). Any ideas?

[MattiaMontanari]

@nyers33 I cannot remember why took that away, but your code seems to be doing the right thing - thanks for sharing!

If you've got only one point and GJK exits quickly enough perhaps you end up processing garbage or default values. Can you printout what's in lambdas when you loop over idx? Maybe check also p and q. In principle it should work, if it doesn't, please share the coordinates of the polygon and point that cause issue. I can look into that.

[nyers33]

@MattiaMontanari All the values from the simplex seem to be valid.

nvrtx = 3
lambdas = {0.5, 0.1, 0.4, garbage}
s.p = {{-50., -26., 0.}, {-50., -24., 5.}, {-50., -24., 0.}, {garbage}}
s.q = {{0., 0., 3.}, {0., 0., 3.}, {0., 0., 3.}, {garbage}}

input for dataP:

8
-50.0000000 -26.0000000 0.00000000
 50.0000000 -26.0000000 0.00000000
-50.0000000 -24.0000000 0.00000000
-50.0000000 -26.0000000 5.00000000
 50.0000000 -24.0000000 5.00000000
-50.0000000 -24.0000000 5.00000000
 50.0000000 -26.0000000 5.00000000
 50.0000000 -24.0000000 0.00000000

dataQ:

1
0.00000000 0.00000000 3.00000000

witness point on P calculated from simplex values: {-50.0, -25.0, 0.5} correct answer: {0.0, -24.0, 3.0} Thank you for having a look!