Search code examples
c++algorithmmathvectorcollision-detection

GJK Algorithm triangle face tests


I am rebuilding my GJK algorithm but I'm having issues with triangular face tests for my tetrahedron. My point and edge tests are complete however.

I want to test if the origin is outside of the tetrahedron and closest to a particular triangular face.

So far my method was to calculate the normals of a triangular face and do a series of dot product tests to determine whether or not the origin is outside and closest to that face. My method has one main issue: I cannot guarantee my normals are facing outwards. See this figure I made for a better description:

As you can see the same triangle, depending on the ordering of the vertices requires different cross product 'ordering' to produce normals that face outwards. Is there any way for me to ensure they face outwards? If not, is there a better method for testing these faces? Here's an example of my process:

if (dot(ABC, AO) > 0) {
        if (dot(ACD, AO) <= 0) {
            if (dot(ADB, AO) <= 0) {
                if (dot(DCB, DO) <= 0) {
                    // closest to face of ABC

                }
            }
        }
    }
}

Reference:

ABC, ACD, ADB, DCB = triangular face normals (as you can see I'm assuming the 'left' triangle from the picture)

AO = vector from A to origin

DO = vector from A to origin


Solution

  • Let's work with face ABC. Form a normal using N = cross(B-A, C-A). If dot(N, D-A) > 0, then N is inward pointing and needs to be reversed. Finally, normalize N to get a unit normal if needed.