version 1.0.0.0 (5.53 KB) by
Matthew Sheen

GJK collision detection algorithm for convex 3D objects.

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.

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

Created with
R2014b

Compatible with any release

**Inspired by:**
platonic_solid

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.

Utkarsh MishraHi,

Thank you very much for the algorithm but I think there is a memory leak somewhere.

In my program, I need to run GJK for more than 50k times and I see a huge increase in the RAM usage.

Can anyone please confirm if this really exists?

Ke LISimon RichardsThank 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 ZhouJingjing Mengvery important feature!

Matthew SheenHi 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 NajafiHello 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 NajafiMatthew SheenSorry 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!

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

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

robinMartin HallmannHello 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 :)

Philippe LebelI'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.

Philippe LebelI'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.

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

Martin HallmannHi, 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

Philippe LebelJust 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

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

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

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

Philippe LebelHi,

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.

Matthew SheenI 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.

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

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

Harish Babu KankanalaMatthew SheenMATLAB 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!

Harish Babu KankanalaHello 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.