# Problem with my GJK implementation

This topic is 787 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I tried implementing the GJK algorithm for convex collision detection by using this video and this page but my implementation doest work correctly, I assume there is something wrong around the 4th case (Tetrahedron), here is my code:

private static Vector3 Support(List<Vector3> Vertices, Vector3 Direction){
float highest = float.MinValue;
Vector3 support = Vector3.Zero;

for (int i = 0; i < Vertices.Count; ++i) {
Vector3 v = Vertices[i];
float dot = Vector3.Dot(Direction, v);

if (dot > highest) {
highest = dot;
support = v;
}
}

return support;
}

public static bool Collides(CollisionShape Shape1, CollisionShape Shape2){
Vector3 D = Vector3.UnitX;
Vector3 S = Support(Shape1.Vertices, D) - Support(Shape2.Vertices,-D);

List<Vector3> Points = new List<Vector3>();

D = -S;
int Steps = 0;
while(Steps < 50){
Vector3 A = Support(Shape1.Vertices, D) - Support(Shape2.Vertices,-D);

if( Vector3.Dot(Points.Last(), D) < 0 )
return false;

if( ContainsOrigin(Points, ref D) )
return true;
Steps++;
}
return false;
}

private static Vector3 TripleProduct(Vector3 A, Vector3 B, Vector3 C){
return Vector3.Cross( Vector3.Cross(A,B), C );
}

private static bool ContainsOrigin(List<Vector3> Array, ref Vector3 Direction){

if(Array.Count == 4)
return Tetrahedron(Array, ref Direction);

Vector3 A = Array.Last();
Vector3 AO = -A;

if(Array.Count == 3){

Vector3 B = Array[1];
Vector3 C = Array[0];

Vector3 AB = B - A;
Vector3 AC = C - A;
Vector3 ABC = Vector3.Cross(AB, AC);

if( Vector3.Dot(Vector3.Cross(ABC, AC), AO) > 0){
if(Vector3.Dot(AC, AO) > 0){
Array.Remove(B);
Direction = TripleProduct(AC,AO,AC);

}else{
if(Vector3.Dot(AB, AO) > 0){
Array.Remove(C);
Direction = TripleProduct(AB,AO,AB);

}else{
Array.Remove(B);
Array.Remove(C);
Direction = AO;

}
}
}else{
if(Vector3.Dot( Vector3.Cross(ABC, AB), AO) > 0 ){
if(Vector3.Dot(AB, AO) > 0){
Array.Remove(C);
Direction = TripleProduct(AB,AO,AB);

}else{
Array.Remove(B);
Array.Remove(C);
Direction = AO;
}
}else{
if( Vector3.Dot(ABC, AO) > 0){
Direction = ABC;
}else{
Vector3 C0 = Array[0];
Array[0] = Array[1];
Array[1] = C0;
Direction -= ABC;
}
}
}
}else{
Vector3 B = Array[0];
Vector3 AB = B - A;

if(Vector3.Dot(AB, AO) > 0)
Direction = TripleProduct(AB, AO, AB);
else
Direction = AO;

}
return false;
}

private static bool Tetrahedron(List<Vector3> Array, ref Vector3 Direction){

Vector3 AO = -Array.Last();
Vector3 AB = Array[2] - Array.Last();
Vector3 AC = Array[1] - Array.Last();

Vector3 ABC = Vector3.Cross(AB, AC);

//CASE 1
if (Vector3.Dot(AO, ABC) > 0)
{
CheckTetrahedron(Array, AO, AB, AC, ABC, Direction);
}

//CASE 2:

Vector3 AD = Array.First() - Array.Last();

if (Vector3.Dot(ACD,AO) > 0)
{

//in front of triangle ACD
Array[2] = Array[1];
Array[1] = Array[0];
AB = AC;
ABC = ACD;

CheckTetrahedron(Array, AO, AB, AC, ABC, Direction);
}

//same direaction with ao
{

Array[1] = Array[2];
Array[2] = Array[0];

AC = AB;

CheckTetrahedron(Array, AO, AB, AC, ABC, Direction);
}

//origin in tetrahedron
return true;
}

private static bool CheckTetrahedron(List<Vector3> Array, Vector3 AO, Vector3 AB, Vector3 AC, Vector3 ABC, Vector3 Direction)
{

Vector3 ab_abc = Vector3.Cross(AB, ABC);

if (Vector3.Dot(AO, ab_abc) > 0)
{
Array.RemoveAt(0);
Direction = Vector3.Cross(Vector3.Cross(AB, AO), AB);

return false;
}

Vector3 acp = Vector3.Cross(ABC, AC);

if (Vector3.Dot(AO,acp) > 0)
{
Array.RemoveAt(0);
Direction = Vector3.Cross(Vector3.Cross(AC, AO), AC);

return false;
}

Array.RemoveAt(Array.Count-1);

Direction = ABC;

return false;
}


Does anyone has a functional, comented 3d implementation I can take a look at or know where the problem is?

Thanks for the help.

##### Share on other sites

Erin Catto's GDC presentation is also very intuitive to understand, you should take look at it.

BTW, you're not implementing GJK. The algorithm you showed doesn't find the closest points between two hulls, it just tells you whether they're overlapping or not. It is also called SAT-GJK. This wasn't very helpfull for me in the context of physics engines.

Edited by Irlan Robson

##### Share on other sites

Thanks for the resource, What advantage GJK gives you over SAT-GJK when detecting collision? Which one is faster? And which one in easier to implement?

##### Share on other sites

GJK finds the closest points and with some effort you can find the closest features (see b3GJKFeaturePair.cpp). SAT-GJK  simply performs a boolean query and can become a little hard to debug because it doesn't have enough bookeeping for visualizing what leads to the final results (closest points).

Of course the performance depends of implementation, but generally your algorithm should be faster and easier to implement since it doesn't keep track of the barycentric coordinates for each simplex vertex.

##### Share on other sites
Interesting, out of curosity what would you use a GJK implementation for? Also do you have a SAT-GJK implementation for me to see?

##### Share on other sites

GJK is used frequently in collision detection and resolution, for example. It is a must have when implementing a robust physics engine nowadays. Here is a fresh resource showing its usabiliy:

http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf

No SAT-GJK for you. You can copy GJK and simplify it. But again I'm not sure if is worth it :) .

##### Share on other sites

GJK true to the original algorithm finds closest points. The algorithm can be "adopted" to perform an early-out without finding closest points once *any* axis of separation is detected. That is the only difference.

##### Share on other sites

GJK is used frequently in collision detection and resolution, for example. It is a must have when implementing a robust physics engine nowadays. Here is a fresh resource showing its usabiliy:

http://box2d.org/files/GDC2015/DirkGregorius_Contacts.pdf

No SAT-GJK for you. You can copy GJK and simplify it. But again I'm not sure if is worth it :) .

Why do you think it wont be worth it?It would be too time consuming? Do you know of any other algorithm to achieve this? Also, do you recommend me to instead use a physics library like bullet?

##### Share on other sites

Because once you have a true, reliably, and optimized GJK implementation SAT-GJK becomes an unnecessary optimization.

Yes, alternatively there is SAT, which runs extremely fast on some shape pairs like a sphere or a capsule vs. a box for example. All of this is explained in Dirk's presentation in my last post. If you choose to go with SAT be prepared to learn some new topics.

No problem with using Bullet for collision detection, but you've already done a great job implementing SAT-GJK, so why not stick with this and only use Bullet if you need more than collision detection? :)

##### Share on other sites

Actually Zaphyk I have implemented this optimization some years ago and found a copy in my old files. Be aware that this is totally not recommended for anything but studying due to the unecessary optimizations or readability. However at the time it just worked  :wink:.

CGJK.h

CGJK.cpp

Hope that helps.

Edited by Irlan Robson

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634051
• Total Posts
3015253
×