Implementation:
I've recently implemented GJK according to caseys movie:
https://mollyrocket.com/forums/viewtopic.php?t=245
It all works fine for the intersection test.
I then needed to produce some contact points. So what I did was determine the penetration depth and normal from the initial GJK result. Then push the objects apart from one another along the -normal by a scale of the penetration depth minus some epsilon, and then run GJK again.
Now after my second GJK my objects should by overlapping by a very small amount. When my GJK runs I store 3 simplex's, one for the minkowski difference, and one per object. I can now solve for some point that exists in all 3 simplex's, as described here:
https://mollyrocket.com/forums/viewtopic.php?t=438
This works okay, the point will jitter around the object a fair bit if it's not just a point collision. (e.g. a cube sitting on top of a bigger cube). But, this is ok for me. (well it seems to be so far
).So how did I find the normal? Well, I basically tested the all normals of the triangles in the simplexes for both objects. For each of these normals I determined a penetration distance for the two objects. The normal that produced the smallest penetration depth was the one I used. (I saved this penetration depth along with the normal).
Problem:
The problem that I'm having is when the normal determined is not correct. This does happen sometimes, GJK will end and the actual collision normal we want will not be found in either objects' simplex.
This can produce incorrect penetration depths and throw the whole algorithm out.
If you look at the attachment image I've attempted to illistrate the problem. You can see the normal n found (as described above). I determine the penetration depth between the two objects by using the GJK support points functions:
A = furthest point along the normal on the bottom object.
B = furthest point along the negative of the normal on the top object.
To find the penetration depth just calculate:
depth = abs(dot(A, n) - dot (B, n));
The penetration depth you can see in the diagram is clearly incorrect. Even if I could find the correct depth, It's still pushing the object sideways which obviously isn't wanted.
Question:
So basically, the algorithm should work if the normal found is one of the convex shape normals. After observing bullets btMinkowskiPenetrationDepthSolver.cpp I see that it just uses an array of normals and tests them as a penetration depth. Now I don't see how this would fix the problem either? If the actual collision normal doesn't happen to be in that big array, then there will be issues.
How do you calculate an accurate normal from the GJK results? Is the only solution EPA? (I've been able to dodge EPA thus far
)I could just store the normal for each object, and then test all of them (but this sounds stupidly expensive).
This seems to be fairly cheap so far, If I could just find the actual normal...
Any ideas?Thanks in advance,
--Phil