File Exchange

image thumbnail

GJK algorithm distance of closest points in 3D

version 1.1.0.0 (20.1 KB) by Philippe Lebel
Computes the coordinates where the minimum distance between two convex polyhedrons occure.

6 Downloads

Updated 05 Jan 2018

View License

It uses the GJK algorithm to find the point, on the minkowsky negative sum of the polyhedrons, closest to the origin. It then uses barycentric coordinates to find the the points on those polyhedrons belonging to the selected point on the minkowsky negative sum.
A video made by Casey Muratori as well as an implementation of the GJK collision detection made by Matthew Sheen right here on matlabcentral have helped me a lot to understand what I was doing.
https://mollyrocket.com/849
https://www.mathworks.com/matlabcentral/fileexchange/57907-fast-3d-collision-detection-gjk-algorithm

Comments and Ratings (20)

Yifan Hou

Hi Philippe, there is a simple failure case for GJK_dist.

s1.Vertices = [0.1000 0 0];
s2.Vertices = [0.04 0.04 -0.04; -0.04 -0.04 -0.04; -0.04 0.04 -0.04];
GJK_dist(s1, s2)

The algorithm will get stuck in the while loop at line 59 of GJK_dist.m. Is this expected? Should I not use it for point to triangle distance?

Atia Najafi

Hi Philippe
or can you please refer me to a source for learning the method you used in this code to calculate gjk distance? I am not clear with it .
Also, for example, you said " % We verify if the point is allready contained in the simplex.
% The (itt>5 && flag == 5) condition to enter this loop is one of the main
% problems of the algorithm." I am not clear, because there is another condition abs(Norm_pts-norm(c))<0.000001, if point c is equal with one of the point in pts, so it enter to the loop, and satisfy if condition.
Thanks for your time
Atia

Atia Najafi

or if you have time, can you please go through that part that sometimes return false distance?

the projection is needed in order to compute the barycentric coordinates of the origin on the plane generated by the 3 closest points of the simplex

Atia Najafi

Thank you so much for your response Philippe, sorry if I am asking many questions, I am not very familiar with GJK-distance.
here I am not clear why you project origin on simplex plane?
%we project the origin on the simplex's plane.
origin_projected=(pts(:,1)'*d)*d;
cause "pts(:,1)" or even "origin_projected" is not necessarily origin=[0 0 0] all the time.

not necessarily more itterations, just a better way to detect if the algorithm is caught in a loop of sequence of simplex points.

Atia Najafi

Thank you so much for your clear response.
I am using this code to detect collision between a point and a cube. in some proximity it works very well, but sometimes it gives a incorrect and discrete distance, so you mean it needs to increase number of iterations?(itt>5 && flag == 5)
Itry to send a copy of my results, but it seems like I cannot attach pic here

as for your first question, i would say that the problem lies more on my conditions to determine if it has finished converging.

While i was first developing it the algorithm could get stuck in a loop where it succesively found the same series of 4 or 5 simplex. One of these set was the optimal solution but I couldn't find a good way to break out of the loop without using less mathematicaly sound conditions.

I got it to work well enough for my needs and stopped it there. I was too busy to try to improve it back in 2016.

Hi Atia,

The reason why the simplex has 3 points in it and not 4 is because from one step to an other, we are only interested in the closest 3 points to the origin. for example:

We have a simplex containing 3 points [a, b, c]. We are looking for a 4th point "d" that is the farthest in the direction of the normal of the triangle [a, b, c] (since the triangle has 2 normals we take the one that is pointing the most toward the origin).

We find the point "d" and incorporate it in the simplex. It has now 4 points. But, we also remove the point that is the farthest from the origin. If it is the point d, we have converged, if it any other point (a,b or c) we remove this point from the simplex and then continue our search with the newly formed 3 point simplex [a, c, d], for example.

Atia Najafi

Hi Phillipe,
I was wondering in GJK_dist, simplex are triangle, and pts=[a b c], objects are in 3D, so why simplex do not have 3+1 member and is not tethrahedron, also in GJK_mod a complete simplex contains 4 member
Thanks
Atia

Atia Najafi

Hi Phillipe,
Thank you so much for your effort on this code, I need this code for my program, and gonna go through that part which you mentioned need some revision, because sometimes in some proximity it calculates a false dist as you mentioned.
the only thing that is not clear is that the problem is due to main concept of gjk algorithm or is in this code?
I look forward to hearing back from you

Himangshu Kalita, you simply need to create a shape with only one point. GJK_dist will give you the two closest points (one of these two points will always be the same point).

With this information you can easily compute the normal vector to the surface by dividing the vector linking the two points by its norm.

Hi Philippe, I am trying to use your code to detect collision between a point and a 3D shape. Is it possible to find the normal vector at the point of collision? Thank you.

Thank you Amin Ramezanifar, I updated the files to avoid the error. I hope this fixes your problem.

Sorry, I meant 'GJK_dist.m'.

As I call 'GJK.m' function, there are certain cases in which line 195 breaks the outer while loop. Consequently, PP0 is not evaluated and it causes a failure in line 246.

@ L.H. Chang:

Hi,

Sorry for the delay.

The changes you are suggesting are required only for (kinda) old releases of matlab, this is why I'm more or so interested in publishing a modified version of the code pertinent only for those releases.

If you want to use the algorithm with such old matlab releases, I would suggest changing all the struct variables to simple arrays.

Example: S1.Vertices ---> S1_vertices

This change would require some amount of work but can be done with no problems.

L.H. Chang

Dear

I run your code and faced with the following fault:
>>S1=10*rand(5,3)
>>S2=10*rand(15,3)
>>GJK(S1,S2,10)

??? Attempt to reference field of non-structure array.
Error in ==> GJK>getFarthestInDir at 195
XData = shape.Vertices(:,1); % Making it more compatible with previous MATLAB releases.

Can you fix your code so that it is compatative with Matlab version R2010b.

Thanks.

Jiadong Guo

Updates

1.1.0.0

Updated for a case where we instantly converge and a variable was not assigned.

1.0.0.0

added thumbnail picture, no code was modified.

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux