possible bug for a special case in GJK?

[WaneOshin]

shouldnt these be ">" instead of ">=" ? if not , then this method wont recognize the case where the origin is ON the simplex itself (i have tested).

gjk.cpp -> do_simplex_4 - > if (Vector3.Dot(abc, ao) > 0.0) { plane_information |= 0x1; } if (Vector3.Dot(acd, ao) > 0.0) { plane_information |= 0x2; } if (Vector3.Dot(adb, ao) > 0.0) { plane_information |= 0x4; }

[felipeek]

Hi @WaneOshin ,

You are correct, the current GJK algorithm will consider that the objects are not intersecting when they are touching, without penetration.

However, I am not sure if considering this case as an intersection is meaningful. Did you identify a scenario in which this introduced a bug in the engine?

If we were to change that, EPA would need to report an intersection as well for this to have an effect (and the penetration vector would be zero in this case, which might require special handling by the engine, not sure).

[WaneOshin]

In a case where 2 identical boxes are intersecting through only one axis (like the picture below) The gjk wont detect an intersection unless the ">=" are replaced with ">". I tested this

[felipeek]

Yeah, this is clearly a bug.

I did some tests and detected that such corner cases will also make EPA fail hard, so EPA will need to be fixed as well, not only GJK. I will investigate this with more care and hopefully fix both algorithms.

Thanks for bringing this issue!

[markeasting]

@WaneOshin you can copy a permalink to the code by shift-clicking the line numbers in github ;)

https://github.com/felipeek/raw-physics/blob/6a0bea5599597ee5e914bc7c4bf6aa3ca591235f/src/physics/gjk.cpp#L138-L146

[nawedume]

Stumbled on this, @felipeek curious, why do you use EPA and Clipping? Can't you just use SAT to get the one shot contact manifold and avoid expensive EPA?

[felipeek]

@nawedume I believe that GJK+EPA could theoretically be replaced by a 3D SAT implementation. In this engine, GJK+EPA are used to detect the collision (GJK) and calculate the collision normal (EPA). I believe a complete SAT implementation would also achieve both.

I am more familiar with GJK than SAT, this is why I chose GJK. EPA is a natural extension of GJK, hence I ended up using it as well. You claim SAT is faster than GJK+EPA in 3D. I am not sure if this is true, especially for convex hulls with lots of vertices, which would require tons of plane tests. However, I am not a SAT expert, so I might be wrong. It would be very cool if somebody implemented SAT in this engine and we could do some benchmarks :)

Regarding clipping, my understanding is that clipping is necessary regardless of the collision detection algorithm that is used. Once the collision vector is obtained, it is necessary to generate the complete collision manifold. AFAIK, SAT does not generate the collision manifold out-of-the-box, thus a dedicated clipping algorithm would still be necessary. But maybe I am wrong?