First off, thanks for your work and sharing the code!

I wonder how big is the task of getting openGJK retrieve contact information (colliders penetrating into each other), to make it behave like an EPA algorithm. I saw your nice video about PyBullet + openGJK speed-up, by any chance, do you have a link for that coveted branch you mention there? :)

Thank you!

What is the minimal distance indicates for the case of collision?
I had a quick look at the code and believe the returned value is just a lower bound of the penetration depth but not the exact value.
I guess for the exact value, you would need further iterations, for example, via EPA.
If this is correct, it would be good if you could indicate it a bit more clearly.

Is it planned also to include EPA to get the correct value in the case of collisions?

I cloned the repo on my Desktop and run CMake as suggested in the readme.
Returned error:

Building Custom Rule C:/Users/user/Desktop/openGJK/CMakeLists.txt
cl : command line error D8021: invalid numeric argument '/Wunused-macros' [C:\Users\user\Desktop\openGJK\build\lib_open
gjk_ce.vcxproj]

Thanks for sharing code. I tried some examples but found a issue.
Please test these 2 polygons
A:
0.795121 -0.727851 0.0
-0.178424 -0.989183 0.0
-0.412644 -0.770664 0.0
0.566564 0.548772 0.0
B:
-0.211223 -0.511346 0.0
-0.347973 0.45872 0.0
0.277308 0.969689 0.0
I change the data in example1_c, and output is Distance : 0.508965
Here is the matlab plot of these polygons. However there is a intersection.
Could you tell me if this is a numerical issue? Thank you for your time.

I am wondering if you would be able to optionally return additional information from the GJK algorithm. Some useful data includes:

1. Tolerance (assuming you implement a tolerance stopping condition)
2. Number of iterations
3. Weights for the vertices*

The weights for the vertices are the most important for my current application. By weights, I mean the point between two vertices that is the closest. For example, given a line segment AB and a triangle CDE, let the point C be closest to the halfway point between points A and B. The weights of the vertices returned would then look something like [(0.5, 0.5), (1, 0, 0)]. Similarly, this could happen in 3D, let the triangle ABC be equilateral, with its center on the origin, and whose points all lie on the plane z=0. Let a point D be at (0, 0, 10). It is clear that the minimum distance between the point and the triangle would then be 10. The weights of the vertices returned would then look like [(0.33, 0.33, 0.33), (1)]. Hopefully that makes sense?

I have yet to read through your publication but it is my understanding that the original GJK algorithm utilizes these weights to some degree. If it is easy enough for you to return that information, that would be fantastic. If it is not, could you point me in the right direction to modify your existing code and eventually create a pull request?

Thanks!

Hi,

I seem to have a similar problem as been stated before. However instead of the /Wunused-macros I solely have a /Wunused invalid argument. I cloned the repository on my windows system and ran CMake in MSVS that returned the following error:

PS C:\Users\user\openGJK\openGJK> cmake --build build
Microsoft (R) Build Engine version 16.9.0+57a23d249 for .NET Framework
Copyright (C) Microsoft Corporation. All rights reserved.

  1>Checking Build System
  Building Custom Rule C:/Users/user/openGJK/CMakeLists.txt
cl : command line error D8021: invalid numeric argument '/Wunused' [C:\Users\user\openGJK\openGJK\build\obj_openGJK.vcxproj]

Full output of all steps are:

PS C:\Users\user\openGJK> cmake -E make_directory build
PS C:\Users\user\openGJK> cmake -E chdir build cmake -DCMAKE_BUILD_TYPE=Release
CMake Warning:
  No source or binary directory provided.  Both will be assumed to be the
  same as the current working directory, but note that this warning will


CMake Error: The source directory "C:/Users/user/openGJK/build" does not appear to contain CMakeLists.txt.
Specify --help for usage, or press the help button on the CMake GUI.
PS C:\Users\user\openGJK> cmake -E chdir build cmake -DCMAKE_BUILD_TYPE=Release ..

-- Building for: Visual Studio 16 2019
CMake Deprecation Warning at CMakeLists.txt:28 (cmake_minimum_required):
  Compatibility with CMake < 3.5 will be removed from a future version of
  CMake.

  Update the VERSION argument <min> value or use a ...<max> suffix to tell
  CMake that the project does not need compatibility with older versions.


-- Selecting Windows SDK version 10.0.19041.0 to target Windows 10.0.19044.
-- The C compiler identification is MSVC 19.28.29913.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: C:/VS2019/VC/Tools/MSVC/14.28.29910/bin/Hostx64/x64/cl.exe - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Compiler in use: MSVC
CMake Warning (dev) at CMakeLists.txt:58 (elseif):
  Policy CMP0054 is not set: Only interpret if() arguments as variables or
  keywords when unquoted.  Run "cmake --help-policy CMP0054" for policy
  details.  Use the cmake_policy command to set the policy and suppress this
  warning.

  Quoted variables like "MSVC" will no longer be dereferenced when the policy
  is set to NEW.  Since the policy is not set the OLD behavior will be used.
This warning is for project developers.  Use -Wno-dev to suppress it.
-- Version     : 3.0.3
-- Build type  : Release
-- Configuring done (5.0s)
-- Generating done (0.1s)
-- Build files have been written to: C:/Users/user/openGJK/build
PS C:\Users\user\openGJK\openGJK> cmake --build build
Microsoft (R) Build Engine version 16.9.0+57a23d249 for .NET Framework
Copyright (C) Microsoft Corporation. All rights reserved.

  1>Checking Build System
  Building Custom Rule C:/Users/user/openGJK/CMakeLists.txt
cl : command line error D8021: invalid numeric argument '/Wunused' [C:\Users\user\openGJK\openGJK\build\obj_openGJK.vcxproj]

Does anyone happen to know what the problem could be? Perhaps I missed a step?

openGJK.c, line 294, you're calling orient2d with the same parameters for B[0] and B[1] (presume it's supposed to be orient2d(pp, sb, sc)?)

Secondly, a question:
in S1D is the dimension-reducing stuff necessary? After you have dotProduct(b, t) / dotProduct(t,t) can you not just clamp that to [0,1] as the lambda?

Hello! @MattiaMontanari
Can i add go implementation of openGJK to examples folder? Go module uses c api.

The following code returns distance nan for two distinct not colliding rather simple objects.
When running equivalent python code within a pytest suite, I can see the following output on captured console too ( but this is not printed in the snippet posted here ) : MAXIMUM ITERATION NUMBER REACHED!

import numpy
import openGJK_cython as opengjk

if __name__ == "__main__":
    vert_sphere_like = numpy.array(
        [
            [-0.58600003, 0.0, 1.0],
            [0.0, -0.58600003, 1.0],
            [0.58600003, 0.0, 1.0],
            [0.0, 0.58600003, 1.0],
            [1.0, 0.0, -0.70700002],
            [1.0, 0.414, -0.414],
            [1.0, 0.414, 0.414],
            [1.0, 0.0, 0.70700002],
            [1.0, -0.414, 0.414],
            [1.0, -0.414, -0.414],
            [0.0, 1.0, -0.70700002],
            [-0.414, 1.0, -0.414],
            [-0.414, 1.0, 0.414],
            [0.0, 1.0, 0.70700002],
            [0.414, 1.0, 0.414],
            [0.414, 1.0, -0.414],
            [-1.0, 0.0, -0.70700002],
            [-1.0, -0.414, -0.414],
            [-1.0, -0.414, 0.414],
            [-1.0, 0.0, 0.70700002],
            [-1.0, 0.414, 0.414],
            [-1.0, 0.414, -0.414],
            [0.0, -1.0, -0.70700002],
            [0.414, -1.0, -0.414],
            [0.414, -1.0, 0.414],
            [0.0, -1.0, 0.70700002],
            [-0.414, -1.0, 0.414],
            [-0.414, -1.0, -0.414],
            [0.0, 0.58600003, -1.0],
            [0.58600003, 0.0, -1.0],
            [0.0, -0.58600003, -1.0],
            [-0.58600003, 0.0, -1.0],
        ],
        dtype=numpy.float64,
    )
    vert_extruded_cube = numpy.array(
        [
            [-2.5, 0.0, 0.5],
            [-3.5, 1.0, 0.5],
            [-2.5, 0.0, -0.5],
            [-3.5, 1.0, -0.5],
            [0.0, 2.5, 0.5],
            [0.0, 3.5, 0.5],
            [-1.0, 3.5, 0.5],
            [0.0, 2.5, -0.5],
            [0.0, 3.5, -0.5],
            [-1.0, 3.5, -0.5],
        ],
        dtype=numpy.float64,
    )
    distance = opengjk.pygjk(vert_sphere_like, vert_extruded_cube)
    print(distance)

The scene looks like the following screenshots ( two perspectives of same scene ):

My environment is MacOS Ventura 13.3.1 (22E261) arm64, Python 3.10.6, cpython build of openGJK ( master, commit 47df2d7 )

Hello,

I have experienced this warning message when using openGJK in my applications. I'm not sure what it indicates. The variable names in openGJK are very abbreviated and it's hard for me to understand what they denote. Furthermore, even though the warning message displays, the script doesn't seem to halt execution or return bad/nonsensical results. I'd greatly appreciate knowing what this warning message means before doing something as reckless as commenting it out. My thanks in advance for any clarification that can be provided!

On a CentOS 7 system, several compilation issues arise, as detailed below. I am providing fixes here rather than in a commit as I am not sure they are the best.

The top-level CMakeLists.txt requires CMake version 3.5 or higher. My CMake is 2.8. Changing the version line to cmake_minimum_required(VERSION 2.8) does the trick, so the version requirement could be set to 2.8 for greater system compatibility.

Compilation generates several errors such as openGJK/lib/src/openGJK.c:74:3: error: ‘for’ loop initial declarations are only allowed in C99 mode.. This can be fixed by adding set(CMAKE_C_FLAGS "-std=gnu99") to openGJK/lib/CMakeLists.txt.

Compilation finally generates the following error:

Linking C executable demo
../lib/libopenGJKlib.a(openGJK.c.o): In function `S2D':
openGJK.c:(.text+0x127): undefined reference to `pow'
openGJK.c:(.text+0x18fa): undefined reference to `sqrt'
../lib/libopenGJKlib.a(openGJK.c.o): In function `gjk':
openGJK.c:(.text+0x4191): undefined reference to `sqrt'
collect2: error: ld returned 1 exit status
make[2]: *** [example1_c/demo] Error 1
make[1]: *** [example1_c/CMakeFiles/demo.dir/all] Error 2
make: *** [all] Error 2

This can be fixed by linking against the math library in openGJK/lib/example1_c/CMakeLists.txt, but changing the linking directive to target_link_libraries(demo openGJKlib "-lm").

I am working on an application that requires being able to check for collisions between polyhedra and spheres/cylinders. I am currently figuring out how to create a bounding polyhedron for these shapes as a temporary way to use this algorithm with them but I am curious as to how hard it would be to add native support for those shapes to this GJK implementation. I have worked with basic implementations of GJK in the past and implementing spheres/cylinders mostly came down to adding support functions for them. It does not look like it would be that easy in this implementation but might it still be worth looking into adding?

Thanks for the library btw, works well and has saved me so much time!

After developing our Matlab codes using OpenGJK under windows, we would like to use our Matlab codes which call OpenGJK under ROS-Ubuntu20 (Linux). I had to recreate Mex file (Matlab under Linux needs .mexa64). I then used it for the given example, but I got this error: Invalid MEX-file - Gateway function is missing.

I used different gcc compiler (8 to 10) as well as -r2017 and -r2018 version within Matlab mex command to generate mex file, but I am getting always the same error.

Could you please help to have a valid mexa64 file of OpenGJK? If this works for you, could you please let us know what is the setting and options of Matlab mex command?

Thank you

To be able to trying to integrate a prototype of FEniCSx with openGJK, it would be beneficial to have an install-script that does not require copy-paste of headers, and that the include files are stored somewhere central, like /usr/local.

On Ubuntu 20.04.4 LTS and with gcc version 10.3.0 (Ubuntu 10.3.0-1ubuntu1~20.04).

mex(fullfile('openGJK.c'),... % Source of openGJK
'-largeArrayDims', ... % Support large arrays
optflug, ... % Compiler flag for debug/optimisation
fullfile('-I','/home/amir/MATLAB/Gabriel/OpenGJK_Master/include'),... % Folder to header files
'-outdir', pwd,... % Ouput directory for writing mex function
'-output', 'openGJK',... % Name of ouput mex file
'-DMATLAB_MEX_BUILD',... % Define variable for mex function in source files
silflag ) % Silent/verbose flag
/home/amir/MATLAB/Gabriel/OpenGJK_Master/openGJK.c: In function ‘mexFunction’:
/home/amir/MATLAB/Gabriel/OpenGJK_Master/openGJK.c:733:13: warning: implicit declaration of function ‘mxCreategkFloatMatrix’; did you mean ‘mxCreateStructMatrix’? [-Wimplicit-function-declaration]
733 | plhs[0] = mxCreategkFloatMatrix(1, 1, mxREAL);
| ^~~~~~~~~~~~~~~~~~~~~
| mxCreateStructMatrix
/home/amir/MATLAB/Gabriel/OpenGJK_Master/openGJK.c:733:11: warning: assignment to ‘mxArray *’ {aka ‘struct mxArray_tag *’} from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
733 | plhs[0] = mxCreategkFloatMatrix(1, 1, mxREAL);
| ^
/home/amir/MATLAB/Gabriel/OpenGJK_Master/openGJK.c:766:17: warning: implicit declaration of function ‘gjk’ [-Wimplicit-function-declaration]
766 | distance[0] = gjk(bd1, bd2, &s);
| ^~~

Error using mex
/usr/bin/ld: /tmp/mex_1491118059826_3560/openGJK.o: in function mexFunction': openGJK.c:(.text+0x3464): undefined reference to mxCreategkFloatMatrix'
/usr/bin/ld: openGJK.c:(.text+0x355d): undefined reference to `gjk'
collect2: error: ld returned 1 exit status

this code just outputs the minimum distance between convex objects and does not provide the closest points (witness points) on objects.

How to add this feature to the current code?

Thanks for the code! Neat and elegant.

Since the returned distance is always >=0, how can we judge if they penetrate? Using d > 1e-15 or other tolerances?

When executing cmake . on ubuntu 18.04.5 I get the error:

`CMake Error at /usr/share/cmake-3.21/Modules/FindOpenMP.cmake:184 (file):
file attempted to write a file:
.../openGJK/CMakeFiles/FindOpenMP/OpenMPTryFlag.c into a source
directory.

Call Stack (most recent call first):
/usr/share/cmake-3.21/Modules/FindOpenMP.cmake:200 (_OPENMP_WRITE_SOURCE_FILE)
/usr/share/cmake-3.21/Modules/FindOpenMP.cmake:461 (_OPENMP_GET_FLAGS)
CMakeLists.txt:71 (find_package)
`

I traced this back to an issue with the setting set(CMAKE_DISABLE_SOURCE_CHANGES ON) in .../openGJK/cmake/CMakeDefaults.cmake setting it to OFF instead worked.

Hi,

I'm interested in running the benchmarks you presented here: https://www.mattiamontanari.com/opengjk/docs/benchmarks/

But I didn't find the code for doing that.

Do you consider publishing the benchmarking code in this repo?

I am trying to compute the distance between blocks in the following figure, and it prints UNEXPECTED VALUES!!! What is the possible reason for that? Can I leave it alone?

I followed the installation instructions (create a new folder, call cmake followed by make) but ran into the following error:

../lib/libopenGJKlib.a(openGJK.c.o): In function `S2D':
openGJK.c:(.text+0x116): undefined reference to `pow'
openGJK.c:(.text+0x17c3): undefined reference to `sqrt'
../lib/libopenGJKlib.a(openGJK.c.o): In function `gjk':
openGJK.c:(.text+0x3d1b): undefined reference to `sqrt'
collect2: error: ld returned 1 exit status
example1_c/CMakeFiles/demo.dir/build.make:95: recipe for target 'example1_c/demo' failed
make[2]: *** [example1_c/demo] Error 1
CMakeFiles/Makefile2:140: recipe for target 'example1_c/CMakeFiles/demo.dir/all' failed
make[1]: *** [example1_c/CMakeFiles/demo.dir/all] Error 2
Makefile:83: recipe for target 'all' failed
make: *** [all] Error 2

I am not very experienced with cmake and make so there is a chance that I have done something wrong. I looked in the CMakeLists.txt file and noticed that you do include the -lm flag which should properly link the math library which suggests that it should work. Perhaps there is a load order issue?

In the meantime, I managed to temporarily fix it by copying openGJK.c to openGJK/example1_c and openGJK.h to openGJK/example1_c/openGJK and then running gcc main.c openGJK.c -o openGJK.bin -lm.

Please let me know if I am missing anything. Thanks!

Thanks for sharing this! I made some comparisons with other libraries and openGJK's result matched theirs very well for a bunch of different convex hulls from around 20 to 500 vertices and some icospheres. (interested in a binary collision query. ran several million queries with random global transforms).
However, when testing a simple 8-vertex cube, every once in a while (empirically around 2 in 10k fully penetrating collisions) I get strange false negatives (i.e.: opengjk gives distances of 10s of centimeters while objects are clearly colliding) like those shown below. Now I wouldn't use GJK for cubes obviously but thought of bringing this issue to your attention

From private conversation:
... And I think the S2D() function might be made faster by moving some of the hff1 & hff2 computations into the if-else clause. An example would be https://github.com/humanoid-path-planner/hpp-fcl/blob/49c54365aa84348e4e3f2cf699574c35295e30c0/src/narrowphase/gjk.cpp#L1001. The speed-up comes from doing less cross-products.

A journal paper describing the library openGJK has been submitted for review to SoftwareX. The source code and the documentation of the library will be uploaded on Github once the paper has been accepted

First of all, thanks a lot for this piece of software. I was looking quite a while to find something like this.

Besides the minimal distance between two polytopes I am also interested in the points on the involved polytope that are the closest to each other. Referring to your publications I think those points are called witness points. Is there a possibility to determine those witness points or are they by any chance already calculated inside the library and only need to be interfaced?

Hello! I have read your papers and codes, which are excellent works. I'm really interested about your work. I found there is an update in version3.0.0, where hff1 function is used to judge which Voronoi region is it belongs to. However, I found the algorithm used here is different from the way described on the paper 《Improving the GJK Algorithm for Faster and More Reliable Distance Queries Between Convex Objects》, which is the same as version 1.1. What kind of algorithm is used here?

Thank you again.