File Exchange

image thumbnail

Fast 3D Collision Detection -- GJK algorithm

version 1.0.0.0 (14.6 KB) by Matthew Sheen
GJK collision detection algorithm for convex 3D objects.

12 Downloads

Updated 09 May 2018

GitHub view license on GitHub

Implementation of the GJK (Gilbert-Johnson-Keerthi) collision detection algorithm in MATLAB. GJK.m function takes shape vertex data and returns whether or not the two shapes are penetrating. Only works on convex objects!
MAIN_example.m animates two polyhedra and stops when the two hit each other.

Cite As

Matthew Sheen (2020). Fast 3D Collision Detection -- GJK algorithm (https://www.github.com/mws262/MATLAB-GJK-Collision-Detection), GitHub. Retrieved .

Comments and Ratings (27)

Ke LI

Thank you for sharing this algorithm - it's very useful for my application. However, although I note Philippe's modification to the pickTetrahedron function I am still finding pathological cases which result in zero dot product dot(acd,ao)==0, leading to a false negative. For example, consider two intersecting cubes with sides of length 10. One has an origin (corner) at [0 0 0] and the other has origin (corner) at [1 1 1] or [2 2 2] or [5 5 5] or any such symmetrical point. These all give a zero dot product and a false negative. If we move away from this pathological case slightly by placing the second cube at [1.1 1.0 1.0] instead of [1 1 1] then the dot product becomes non zero and the collision is correctly detected. I'm afraid I don't understand the algorithm well enough to see how to fix this correctly without introducing false positives, so I'd be very grateful for any help you can offer. I am using this algorithm to detect intersections between a body and cells of a mesh, so this pathological case occurs much more frequently than it might in other applications.

Grant Zhou

very important feature!

Hi Atia,
I think you might have posted on the wrong page. My code does not use cartesianToBarycentric (that I recall anyway). I think you might want to comment on Philippe's extended version, found here: https://www.mathworks.com/matlabcentral/fileexchange/62429-gjk-algorithm-distance-of-closest-points-in-3d
Best,
Matt

Atia Najafi

Hello Philipe,
Thank you so much for writing GJK_dist, I am trying to clone this code to a model in simulink, and because of that some parts of code are not accepted by simulink, I had to make some little change. now my problem is with "triangulation" and "cartesianToBarycentric" are not accepted by simulink, and am receiving following error:
""The extrinsic function 'triangulation' is not available for standalone code generation. It must be eliminated for stand-alone code to be generated. It could not be eliminated because its outputs appear to influence the calling function. Fix this error by not using 'triangulation' or by ensuring that its outputs are unused.

"The extrinsic function 'cartesianToBarycentric' is not available for standalone code generation. It must be eliminated for stand-alone code to be generated. It could not be eliminated because its outputs appear to influence the calling function. Fix this error by not using 'cartesianToBarycentric' or by ensuring that its outputs are unused."

is there a way to change these two function to be acceptable by simulink?
I look forward to hearing back from you.
Thanks
Atia

Atia Najafi

Sorry I've been out of touch with this for awhile. Thanks to all for your comments/feedback/bug diagnosis. I've merged a pull request from Max Frei who fixed a bug which resulted in false positives. Thanks!

hello, i am just trying to use the program but i am not able to put the inputs of the program

I am just trying o use but i am not able to put the inputs of the program

robin

Hello Philippe, I'm curious about your implementation. It would help me a lot to have a look at your code to handle this task. Thanks a lot and hope to hear from you :)

I've written a lengthy text to answer you but somehow it only posted a little part of it...

I implemented the 3D closest distance calculation algorithm. Although this is not the textbook version of the code. It is not bullet proof but works consistently. The algorithm computes the closest distance and the points on the polyhedras where occur this closest distance.

The algorithm runs in about 1.3 ms for polyhedras of same complexity than the ones used in the GJK collision demo.

Right now, I'm working on cleaning my code and commenting it. I'm also planing to publishit here.

I've written a lengthy text to answer you but somehow it only posted a little part of it...

I implemented the 3D closest distance calculation algorithm. Although this is not the textbook version of the code. It is not bullet proof but works consistently. The algorithm computes de closest distance and the points on the polyhedras where occur this closest distance.

The algorithm runs in about 1.3 ms for polyhedras of same complexity than the ones used in the GJK collision demo.

Right now, I'm working on cleaning my code and commenting it. I'm also planing to publishit here.

very important feature! it also computes the collision points on the two polyhedras!

Hi, nice implementation of GJK. Philippe, have you tried a method for calculating the minimum distance if no collision is detected? I tried to do expand the 2D approach from http://www.dyn4j.org/2010/04/gjk-distance-closest-points/ to 3d, but I have problems to find the right feature in the Minkowski sum.

Thank you

Just replace the "if" statement arround line 150 by this. I didn't know if posting code in comment section was ok, but it seems so.

if dot(acd, ao) > 0 %Above triangle ACD
%Make this the new base triangle.
b = c;
c = d;
ab = ac;
ac = ad;
abc = acd;
elseif dot(acd, ao) < 0
adb = cross(ad,ab);%Normal to face of triangle

if dot(adb, ao) > 0 %Above triangle ADB
%Make this the new base triangle.
c = b;
b = d;
ac = ab;
ab = ad;
abc = adb;
else
flag = 1;
break; %It's inside the tetrahedron.
end
else %the origin is on the same plane as the triangle
;
end

we only see typos after we posted an uneditable text...

I think i found the problem. I'm not really familiar about how to proceed to share my finding with you on this website.

The problem was in the pickTetrahedron function. The algorithm you implemented assumed the vector "ao" would either be point upward or downward from the triangle. While it is true for 99.9% of cases, when vertices are the closest points, the vector "ao" is perpendicular to the triangle normal. Giving a 0 dot product when the normal.

Inform me on the way you'd like me to transfer the code to you and I'll share it.

Meanwhile, if you happened to have the EPA algorithm implemented and ready to share, I would like to look at it, mine is pretty noisy, I dont know why.

Thanks for letting me know, Phillippe. I'll check it out later this week. If you find a bug fix too, please let me know!

Hi,

I implemented my version own of EPA based on your implementation of GJK.

While working on this implementation, I noticed a bug in the GJK algorithm you provided. When the closest points between the two solids correspond to a pair of vertices, the algorithm states there is a collision when there is obviously none.

I am currently working to figure out a way to correct this. Please notice me if this is not a bug and I just miss used your algorithm, or if you find the solution. I will provide the solution when I find it.

Thank you.

I implemented this portion of the algorithm:
http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/

This explanation goes on to talk about how to extend this to find closest distance/points:
http://www.dyn4j.org/2010/04/gjk-distance-closest-points/

For my purposes, I had used only this version which finds if collisions have occurred. I supplemented it with the Expanding Polytope Algorithm (EPA) to get the collision point and collision normal vector.

Perhaps if I have some time in the future, I can add some extra features to this code or add my implementation of EPA.

Could there be a way to output the closest distance, or the postion where the collision occurs?

Thanks for letting me know, Harish! I updated 201, and pushed back up to git.

MATLAB changed the way you can change figure properties in 2014b.

To get a graphics object's field:
S1Coords = S1Obj.Vertices; % New -- 2014b +
S1Coords = get(S1Obj,'Vertices'); % Old -- 2014a -

To set a graphics object's field:
S1Obj.Vertices = anotherMatrix; % New -- 2014b +
set(S1Obj,'Vertices',anotherMatrix); % Old -- 2014a -

The key would be to swap all the first type of lines with the second type to make it compatible with older versions of MATLAB.

I made a version called MAIN_example_compatible.m. It should sync from GitHub within the day (or you can follow the link directly). Try running this. I don't have access to MATLAB 2014a, so I can't verify if I've caught all the changes. Please let me know if it works, thanks!

Hello now the program is working good. I downloaded the latest file and had to Change the line number 201 of GJK file to make it run in Matlab2013a.

Modified code on line 201:

point = [XData(rowIdx,colIdx), YData(rowIdx,colIdx), ZData(rowIdx,colIdx)];

Thank you Matthew.

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

Inspired by: platonic_solid

Inspired: GJK algorithm distance of closest points in 3D