There are numerous resources regarding GJK on the internet. This site is mostly for the ones interested in programming their own algorithm rather than taking a finished product.
What is GJK?
With the GJK (Gilbert–Johnson–Keerthi) algorithm, one can determine whether two convex shapes are intersecting or not. The algorith itself can be used in 2d or 3d.
I will not go into great detail since this is mainly covered in the video which can be found at mollyrocket (first link in the list above). I will focus on my implementation and emphasize on the difficulties i encountered (esp. the tetrahedral case).
Disclaimer: I am not a professional programmer. My implementation may not be the fastest or most beautiful. The path of improvement is long and wide. All the info provided on this site is not meant to be a 'zero to GJK'. For a general point of entry i recommend the links above (especially the first one)!
Header - files:
First we define the two classes (shape & simplex) for the headerfile gjk.h:
shape negate(); // x -> -x ; y -> -y ; z -> -z float dot(shape d); // dot product
shape cross(shape cpt); // cross product of two vectors(shapes)
void set(shape set); // set a vector(shape) to a given x/y/z value(s)
shape rot_x(float rot_x); // rotates a shape around the x-axis
shape rot_y(float rot_y); // rotates a shape around the y-axis
shape rot_z(float rot_z); // rotates a shape around the z-axis
};
A shape consists of three values x/y/z. Later we will create arrays of shape-class objects. When talking of 'shape(s)' i will either refer to a point defined by three cartesian coordinates (x/y/z) or a quantity of points. The context should make it clear, which one im talking about.
The (header)functions defined obove are:
negate() - change the algebraic sign of the elements x/y/z
dot(shape d) - dot product of two shapes
cross(shape cpt) - cross product of two shapes
set(shape set) - change the values of a shape
rot_x/y/z(float rot_x/y/z) - rotate a shape (mainly for visualization)
class simplex
{
public:
void add(shape simplex_add); // add a new point to the simplex (list)
void set_zero(void); // (re)sets all points in the simplex-list to zero
void del(int id); // delete vector from the simplex with given id (id = 0, 1, 2)
shape getLast(void); // returns the last added point
shape get(int id); // returns the x/y/z - values of a given index of the simples with id (= 0 ... 3)
int size(void); // returns the amount of points in the simplex list (0 ... 4)
The class simplex and its functions are used to store the points of the simplex and manipulate the list. There can be a total maximum of four points in the simplex.
GJK function(s):
001
bool gjk(shape *A, shape *B, int dim_a, int dim_b);
This will be our main GJK-function into which we will feed the arrays of x/y/z-shapes into. dim_a and dim_b are the number of shapes (each one defined by a x/y/z-value) we feed into the function. It will return true when there is an intersection between the two convex shapes and false if there is no intersection. Further down is an example on how to call the function in detail.
return_shape.x = x;
return_shape.y = y * cos(rot_x * PI / 180.0) - z * sin(rot_x * PI / 180.0);
return_shape.z = y * sin(rot_x * PI / 180.0) + z * cos(rot_x * PI / 180.0);
Deletes an entry from the simplex list. This function takes an id (1 ... 4) and removes this entry from the simplex. Then the list is then being collapsed, so that if we add a new entry to the list, this newly added point will always be at the end.
if (id < 0 or id > 3)
{
std::cout << "cannot fetch simplex point with given index " << id << std::endl;
}
else
{
return_shape.x = x[id];
return_shape.y = y[id];
return_shape.z = z[id];
The call of the function gjk() is here illustrated with a triangle (ts1[] - one side of a tetrahedron) and a square (cs1_1[] - one side of a cube). These two polygons are being tested on collision.
GJK - main function:
We define two variables of type bool (check_failsafe and check). The bool check will indicate if there is a collision or not (which will be returned at the end). The bool check_failsafe is being triggered, when the algorithm gets stuck and subsequently adds and removes the same points. This will result in an infinite loop. Usually one or two tetrahedral cases are enough to determine if there is a collision or not. If the algorithm goes through the tetrahedral case 10 times, a new search direction is chosen randomly. The number 10 is chosen completely arbitrary.
In the first while loop, the geometrical middle points of the two shapes are calculated using the function mass_middle_point(). Then the direction between these two points is calculated.
We clear the simplex (simplex.set_zero()) and add the first point to the list (simplex.add(support_function(A, B, dim_a, dim_b, d));). support_function(A, B, dim_a, dim_b, d) determines the point farthest away in the Minkowski difference along a given direction d. After that we negate the search direction and start the second while loop. Here we start with adding a new point to the simplex. Then it is checked, if the size of the simplex is four (tetrahedral case). If that is true, we increment the variable for the fail safe.
If the last added point to the simplex is not exceeding the point of origin, then there is no collision and we can end here. We set check and check_failsafe to false and break both while loops: There is no collision!
If the last added point in the simplex (towards the search direction) list is exceeding the point of origin, we don't know yet if there is a collision between the two convex shapes. The function containsOrigin(simplex, d) is called.
Based on how many points there are in the simplex list the function containsOrigin(simplex, d) does the following:
line-case: 2 points in the simplex list: determine the new search direction towards the point of origin
triangle-case: 3 points in the simplex list: similar to the case above (determine a new search direction towards the point of origin)
tetrahedral case: 4 points in the simplex list: determine, which face of the tetrahedron is closest to the origin. Delete the point of the simplex, which is not element of this side and feed this triangle back into the loop.
Each time after the function containsOrigin(simplex, d) is called, a new point is added to the simplex list according to the determined search direction and then it is checked, whether this point exceeds the origin.
The function containsOrigin(simplex, d) also checks, if the point of origin is contained in the tetrahedron (more further down).
This function (support_function()) takes the two shapes and a search direction and computes the point in the Minkowski difference, which is farthest away in this given direction.
The function containsOrigin(simplex& simplex, shape& d):
shape ac_c_ab = ac.cross(ab); // ac_c_ab = AC x AB float v_abc = ac_c_ab.dot(a0);
shape ab_c_ad = ab.cross(ad); // ab_c_ad = AB x AD float v_abd = ab_c_ad.dot(a0);
shape ad_c_ac = ad.cross(ac); // ad_c_ac = AD x AC float v_acd = ad_c_ac.dot(a0);
int amount_neg = 0;
int amount_pos = 0;
if (v_acd > 0)
amount_pos++;
else
amount_neg++;
if (v_abd > 0)
amount_pos++;
else
amount_neg++;
if (v_abc > 0)
amount_pos++;
else
amount_neg++;
if (amount_pos == 3) // origin enclosed in the tetrahedron -> there is a collision
{
return true;
}
else if (amount_neg == 3) // origin enclosed in the tetrahedron -> there is a collision
{
return true;
}
else // remove this point
{
if (amount_neg == 2 and amount_pos == 1)
{
if (v_acd > 0)
{
simplex.del(3); // remove this point
d.set(ad_c_ac); // set new search direction
}
else if (v_abd > 0)
{
simplex.del(2); // remove this point
d.set(ab_c_ad); // set new search direction
}
else
{
simplex.del(1); // remove this point
d.set(ac_c_ab); // set new search direction
}
}
else if (amount_neg == 1 and amount_pos == 2)
{
if (v_acd < 0)
{
ad_c_ac.negate();
simplex.del(3); // remove this point
d.set(ad_c_ac); // set new search direction
}
else if (v_abd < 0)
{
ab_c_ad.negate();
simplex.del(2); // remove this point
d.set(ab_c_ad); // set new search direction
}
else
{
ac_c_ab.negate();
simplex.del(1); // remove this point
d.set(ac_c_ab); // set new search direction
}
}
else
{
std::cout << "error(number pos/neg)" << std::endl;
}
}
}
else if (simplex.size() == 3) // triangle case
{
shape return_sd;
return_sd.x = 0;
return_sd.y = 0;
return_sd.z = 0;
shape b = simplex.get(1);
shape c = simplex.get(0);
The last point in the simplex is always taken as a point of reference. Then, based on how many points are in the simplex list, a new search direction is being determined and if there are four points in the simplex list, one is being removed.
I will not explain the cases where two and three points are in the simplex list since these cases are well described in the video which can be found at http://mollyrocket.com/849.
The tetrahedral case
The tetrahedral case however is not covered in the video. We know which three sides we have to test of the tetrahedron, because we evolved a triangle into a tetrahedron. The search direction from the triangle to the tetrahedron was towards the origin. Therefore the origin can not be closest to the original triangle. First we extract the three points and compute the face normal vectors of the three triangle sides we need to check. Then we calculate the dor product of these normal vectors with a0.
We count the amount of positive and negative dot products. If all are negative or all are positive, we can conclude that the point of origin is inside the tetrahedron. If not, we remove the according point and set a new search direction.
Picture of the main cases:
The picture above shows the case, where the algorith stops after the line-case. Red and green are the two shapes, which are being tested on collision and white their geometrical middle points. The yellow dots are the points of the Minkowski difference. First the red point in the Minkowski difference is added to the simplex and then the green one. After that, the case that there is no collision is being determined (line-case). The big green square at the bottom right is the indicator for no collision (green).
Above the tetrahedral case: A third (blue) and fourth (pink) point is added to the simplex list, which spans now a tetrahedron. For each of the three triangles the geometric middle point and the surface normal is drawn. The point of origin lies inside of the tetrahedron and there is a collision.
Like above: collision with alle surface normals pointing to the outside of the tetrahedron.
Above the tetrahedral case where a collision is uncertain and the new search direction (red) is determined by negating the surface normal (turquoise).
Above the tetrahedral case with three iterations (three pink points added, and 3 red search direction). One can see clearly, that the tetrahedrons are propagating towards the origin.