Collision Points in GJK

Question

Is there a way to modify a Gilbert-Johnson-Keerthi Algorithm so it finds points of the collision between two bodies instead of a true/false result ? From what I've understood the received distance value could be used to find these points. I searched the web but didn't find any hints.

Answer 1

What you are asking for is not well-posed. If they are colliding, then a point of intersection is undefined -- since the intersection is actually a region of overlap and thus could be any number of possible points. Instead, you should think about a "point of intersection" as a coordinate in space-time, (dx,dy,dz,t), representing the time of impact, together with a translation vector between the two bodies giving you their relative configurations.

One way to modify GJK to compute a space-time intersection is to do a binary search over the swept volume to find the moment of time right before impact. Using this data, you can compute a separating axis and corresponding extremal points for both bodies, which gives you a close approximation of the point of impact. This approach can also be fast if you reuse the simplices from previous iterations of the search to speed up subsequent tests. Christer Ercisson has some notes on this technique here: http://realtimecollisiondetection.net/pubs/SIGGRAPH04_Ericson_GJK_notes.pdf

Answer 2

This paper covers your question i believe, and is up to date. i'm don't have anycode. and not going to re-explain it, but, the author also has a pres up on YouTube explaining it. working on the code now, and their is very little examples. but this is what you want. you can use the "less effective" way mentioned. in the paper as a. as it will work just fine for your work. unless you goal is extremely high performance.

"Improving the GJK algorithm for faster and more reliable distance queries between convex objects"

MATTIA MONTANARI and NIK PETRINIC University of Oxford

ETTORE BARBIERI Queen Mary University of London

https://ora.ox.ac.uk/objects/uuid:69c743d9-73de-4aff-8e6f-b4dd7c010907/download_file?safe_filename=GJK.PDF&file_format=application%2Fpdf&type_of_work=Journal+article