GJK algorithm 3D

It’s time to talk about GJK algorithm 3D. It is more complicated than the 2D one because it needs one extra case to check. The basic concepts are still the same that are used in 2D , I wrote  about them here. You still need to know some basic math like cross product and dot product to understand how it works. Now, we can use the real cross product to find new directions to check for origin point(0,0,0). Here is a video to show how it works:

 

I found some good optimizations for algorithm on Shiny Piexels. For example we can use 4 vector3 variables instead of a std::vector  for the simplex and interchange them instead of adding and removing form the vector. Also the code is easy to fallow. For tetrahedron  there are 3 cases to check if  the origin is inside or outside. Read comments in source code to understand better.The origin can not be “below” cbd face, because we already checked that.

I tried to explain visually how I see the 4 cases for tetrahedron in 3D. If we are in the first 3 cases we need to perform another 2 checks to see in which direction is the origin of Minkowski difference. These two checks are similar to triangle case.

Gjk ABC

 gjk ACD case 2

gjkADB

 

gjkabcd

I used this code for one of my school homework ,so I used a specific structure. But you have to look only in CollisionDetection/Box/ GJK classes. I wanted to move only one cube  same like in 2D where I moved only one shape. Use w,a,s,d to move the cube and arrows and mouse to move through the scene.

GJK_3D_OpenGL with VS2013.sln, but you can copy resources and build another project

Only GJK_3D_algorithmC++


Tagged under:
blog comments powered by Disqus