False negative for penetrating boxes

[neemoh]

Thanks for sharing this! I made some comparisons with other libraries and openGJK's result matched theirs very well for a bunch of different convex hulls from around 20 to 500 vertices and some icospheres. (interested in a binary collision query. ran several million queries with random global transforms). However, when testing a simple 8-vertex cube, every once in a while (empirically around 2 in 10k fully penetrating collisions) I get strange false negatives (i.e.: opengjk gives distances of 10s of centimeters while objects are clearly colliding) like those shown below. Now I wouldn't use GJK for cubes obviously but thought of bringing this issue to your attention

[MattiaMontanari]

Thanks for reporting this, it is useful. There is nothing wrong in using GJK for cubes :). It may not be fastest at execution, but with one algorithm you can solve a broad range of distance queries. OpenGJK should allow that.

I think the issue is at initialisation, where it is assumed that the points 0 of bd1 and bd2 are a good initial guess. A better guess, with little overhead and caching even outside this library, will give more accurate results. Even though 2 in 10k is not too bad for a free library :). The thing is that testing random combination for GJK doesn't allow to dive deep and squash bugs because is not representative of the end application. For instance, if you use GJK in a physics engine, the collisions are not random as there is a pattern in the penetrating vector/overlap regions. This means that 2 in 10k may be worsen or even improve in the real application.

Having said that, your pictures clearly show a bug :) I need to replicate it please send me the list of coordinates for the two bodies and I'll look into it.

[neemoh]

Hi Mattia, Here is an example:

{0.0794482, -0.00830481, -0.149648, 0.173392, 0.0137847, -0.123445, 0.0814828, -0.164745, -0.025059, 0.175427, -0.142656, 0.00114352, -0.0233202, 0.166461, 0.071476, 0.0706238, 0.18855, 0.0976785, -0.0212856, 0.0100205, 0.196065, 0.0726585, 0.03211, 0.222267}

{-0.1, -0.1, 0.1, 0.1, -0.1, 0.1, -0.1, 0.1, 0.1, 0.1, 0.1, 0.1, -0.1, -0.1, -0.1, 0.1, -0.1, -0.1, -0.1, 0.1, -0.1, 0.1, 0.1, -0.1}

[MattiaMontanari]

@neemoh, please have look at the MR #14 for this branch where I added your inputs. The c example returns distance = 0, which is the correct answer. I cannot replicate your issue

[MattiaMontanari]

I can't reproduce this and I didn't hear back

[neemoh]

Sorry was busy. I can't replicate it either. It can be some weird bug on my side. Not worth investigating more. Thanks. By the way linker complains about libm when building on my Linux, had to link it in the cmake.