Separating axis theorem falsely triggers

Question

I'm writing some code in C++ for testing collisions using the separating axis theorem and in certain orientations it wrongly triggers that there is a collision occurring

I'm following this tutorial, however the tutorial is only in 2D and i'm trying to implement it in 3D although i think it should still be the same.

The algorithm that i have now doesn't miss any collisions but for some orientations of the two boxes it thinks that that are colliding when they're infact not. An example can be seen here, these two boxes are apparently colliding according to the code below.

The code is written in C++

BoxCollider.h

class BoxCollider :
    public Collider
{
public:
    BoxCollider(Vector3 position, Vector3 rotation, Vector3 size);


    ~BoxCollider();

    void Update();

public:
    Vector3 rotation;
    Vector3 size;
    Matrix transformMatrix;

    std::vector<Vector3> points;

    Vector3 normals[3];
};

BoxCollider.cpp

BoxCollider::BoxCollider(Vector3 position, Vector3 rotation, Vector3 size) : rotation(rotation), size(size)
{
    this->position = position;
    points.resize(8);

}

BoxCollider::~BoxCollider()
{
}

void BoxCollider::Update()
{
    Transform* eTransform = m_entity->GetComponent<Transform>();
    transformMatrix.RotateYawPitchRoll(rotation + eTransform->rotation);
    Vector3 ePos = eTransform->position;

    points[0] = transformMatrix * (Vector3( 0.5, -0.5, -0.5) * size) + position + ePos;
    points[1] = transformMatrix * (Vector3( 0.5,  0.5, -0.5) * size) + position + ePos;
    points[2] = transformMatrix * (Vector3( 0.5, -0.5,  0.5) * size) + position + ePos;
    points[3] = transformMatrix * (Vector3( 0.5,  0.5,  0.5) * size) + position + ePos;
    points[4] = transformMatrix * (Vector3(-0.5, -0.5, -0.5) * size) + position + ePos;
    points[5] = transformMatrix * (Vector3(-0.5,  0.5, -0.5) * size) + position + ePos;
    points[6] = transformMatrix * (Vector3(-0.5, -0.5,  0.5) * size) + position + ePos;
    points[7] = transformMatrix * (Vector3(-0.5,  0.5,  0.5) * size) + position + ePos;

    normals[0] = transformMatrix * Vector3(1, 0, 0);
    normals[1] = transformMatrix * Vector3(0, 1, 0);
    normals[2] = transformMatrix * Vector3(0, 0, 1);
}

The algorithm:

void EntityManager::CheckCollision(BoxCollider * col0, BoxCollider * col1)
{
    for (int i = 0; i < 3; i++) //First cube
    {
        Vector3 axis = col0->normals[i];
        axis = Vector3(axis.z, -axis.x, axis.y);


        Projection proj1 = GetProjection(col0->points, axis);
        Projection proj2 = GetProjection(col1->points, axis);

        float overlap = GetOverlap(proj1, proj2);

        if (overlap > 0.0) //The projections do not overlap
            return;
    }

    for (int i = 0; i < 3; i++) //First cube
    {
        Vector3 axis = col1->normals[i];
        axis = Vector3(axis.z, -axis.x, axis.y);

        Projection proj1 = GetProjection(col0->points, axis);
        Projection proj2 = GetProjection(col1->points, axis);

        float overlap = GetOverlap(proj1, proj2);

        if (overlap > 0.0) //The projections do not overlap
            return;
    }
}

float GetOverlap(Projection proj1, Projection proj2)
{
    float a = proj2.left - proj1.right;
    float b = proj1.left - proj2.right;

    return a > b ? a : b;
}

Projection GetProjection(std::vector<Vector3> points, Vector3 axis)
{
    float tmp = 0;
    float left = D3D10_FLOAT32_MAX, right = -D3D10_FLOAT32_MAX;

    for (int i = 0; i < points.size(); i++)
    {
        tmp = DotProduct(points[i], axis.Normalize());
        if (tmp < left)
        {
            left = tmp;
        }

        if (tmp > right)
        {
            right = tmp;
        }
    }

    return Projection(left, right, axis);
}

Answer 1

tutorial is only in 2D and i'm trying to implement it in 3D although i think it should still be the same

Unfortunately, it is not the case. The 3D case a little bit more complex. To check whether two complex shapes are colliding in 3D, you need to check every face normal (you do this), and directions which are perpendicular to an edge of each object (you miss these).

So, for boxes (A and B), with edge directions A0, A1, A2, and B0, B1, B2, we have:

• 3 normals of A
• 3 normals of B
• 9 directions: A0 x B0, A0 x B1, A0 x B2, A1 x B0, A1 x B1, A1 x B2, A2 x B0, A2 x B1, A2 x B2

So you just need to add the missing 9 checks.

Further note: you don't need to swizzle the normals. I mean this line is not needed:

    axis = Vector3(axis.z, -axis.x, axis.y);

In this case, it doesn't do any harm. But for more complex shapes, it actually could make the test incorrect.