version 1.1.0.0 (20.1 KB) by
Philippe Lebel

Computes the coordinates where the minimum distance between two convex polyhedrons occure.

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

Philippe Lebel (2021). GJK algorithm distance of closest points in 3D (https://www.mathworks.com/matlabcentral/fileexchange/62429-gjk-algorithm-distance-of-closest-points-in-3d), MATLAB Central File Exchange. Retrieved .

Created with
R2016a

Compatible with any release

- Simulink > Simulation >

**Inspired by:**
Fast 3D Collision Detection -- GJK algorithm, Distance between a point and a triangle in 3D, geom3d, platonic_solid, Patch Slim (patchslim.m)

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Yifan HouHi 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 NajafiHi 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 Najafior if you have time, can you please go through that part that sometimes return false distance?

Philippe Lebelthe 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 NajafiThank 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.

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

Atia NajafiThank 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

Philippe Lebelas 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.

Philippe LebelHi 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 NajafiHi 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 NajafiHi 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

Philippe LebelHimangshu 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.

Himangshu KalitaHi 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.

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

Amin RamezanifarSorry, I meant 'GJK_dist.m'.

Amin RamezanifarAs 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.

Philippe Lebel@ 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. ChangDear

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.

Filmon YacobJiadong Guo