2
\$\begingroup\$

I've been trying to get proper collision detection with SAT in 3D. I started of with this post: How many and which axes to use for 3D OBB collision with SAT.

I've been trying to get the right axis to test, which I thought would be correct, but they are still giving me false positives. All actual collision seem to work.

What I try is the following:

  • Get the model for the objects in my game.
  • Get the corners for the objects
  • Adjust these corners to my object's location
  • Get the axis
  • Check for overlap when projecting the corners on these axis

When positioning the object in this way:

enter image description here

Then I get a false positive. (Although these are axis aligned, they should be able to rotate)

I've been stuck on this for quit a while now, so I feel like I'm missing something I just can't find. Also if this approach is an overkill and there is a better way, please also let me know.

I hate to just go like here's my code, but breaking it up in pieces will probably make it more confusing, so.. here's my code:

#define NOMINMAX

#include "../../stdafx.h"
#include "CollisionSystem.h"
#include "../../Core/MovingGameObject.h"
#include "../Objects/StaticObjects/Skull.h"
#include "../Objects/StaticObjects/Primitives/Plane.h"
#include <limits>
#include <cmath>

using namespace DirectX;

namespace JurreGame {
    CollisionSystem::CollisionSystem()
    {
    }


    CollisionSystem::~CollisionSystem()
    {
    }

    void CollisionSystem::CheckCollisionBetween(GameObject* objectA, GameObject* objectB)
    {
        XMFLOAT4X4 modelA = objectA->GetModel();
        XMMATRIX modelAMatrix = XMLoadFloat4x4(&modelA);
        XMMATRIX invModel = XMMatrixInverse(&XMMatrixDeterminant(modelAMatrix), modelAMatrix);
        XMFLOAT4X4 invModel4x4;
        XMStoreFloat4x4(&invModel4x4, invModel);
        XMMATRIX modelBMatrix = XMLoadFloat4x4(&objectB->GetModel());
        XMMATRIX aAlignedObjectBModel = XMMatrixMultiply(invModel, modelBMatrix);


        /* Corners positions
            x y z
        0 = - - +
        1 = + - +
        2 = + + +
        3 = - + +
        4 = - - -
        5 = + - -
        6 = + + -
        7 = - + -

        axis for the planes are:
        X Axis => (3) - + + vs + + + (2)
        Y Axis => (3) - + + vs - - + (0)
        Z Axis => (3) - + + vs - + - (7)
        */

        // https://gamedev.stackexchange.com/questions/44500/how-many-and-which-axis-to-use-for-3d-obb-collision-with-sat

        // Get's the corners calculated for the extends.
        XMFLOAT3 objectACorners[8];
        objectA->bounds.GetCorners(objectACorners);
        XMFLOAT3 objectBCorners[8];
        objectB->bounds.GetCorners(objectBCorners);

        // translates them to world space
        for (int i = 0; i < 8; i++) {
            XMStoreFloat3(&objectACorners[i], XMVector3Transform(XMLoadFloat3(&objectACorners[i]), modelAMatrix));
            XMStoreFloat3(&objectBCorners[i], XMVector3Transform(XMLoadFloat3(&objectBCorners[i]), modelBMatrix));
        }

        XMVECTOR ObjectAaxis1 = XMVectorSubtract(XMLoadFloat3(&objectACorners[2]), XMLoadFloat3(&objectACorners[3]));
        XMVECTOR ObjectAaxis2 = XMVectorSubtract(XMLoadFloat3(&objectACorners[3]), XMLoadFloat3(&objectACorners[0]));
        XMVECTOR ObjectAaxis3 = XMVectorSubtract(XMLoadFloat3(&objectACorners[3]), XMLoadFloat3(&objectACorners[7]));

        XMVECTOR ObjectBaxis1 = XMVectorSubtract(XMLoadFloat3(&objectBCorners[2]), XMLoadFloat3(&objectBCorners[3]));
        XMVECTOR ObjectBaxis2 = XMVectorSubtract(XMLoadFloat3(&objectBCorners[3]), XMLoadFloat3(&objectBCorners[0]));
        XMVECTOR ObjectBaxis3 = XMVectorSubtract(XMLoadFloat3(&objectBCorners[3]), XMLoadFloat3(&objectBCorners[7]));

        XMVECTOR crossaxis1 = XMVector3Cross(ObjectAaxis1, ObjectBaxis1);
        XMVECTOR crossaxis2 = XMVector3Cross(ObjectAaxis1, ObjectBaxis2);
        XMVECTOR crossaxis3 = XMVector3Cross(ObjectAaxis1, ObjectBaxis3);
        XMVECTOR crossaxis4 = XMVector3Cross(ObjectAaxis2, ObjectBaxis1);
        XMVECTOR crossaxis5 = XMVector3Cross(ObjectAaxis2, ObjectBaxis2);
        XMVECTOR crossaxis6 = XMVector3Cross(ObjectAaxis2, ObjectBaxis3);
        XMVECTOR crossaxis7 = XMVector3Cross(ObjectAaxis3, ObjectBaxis1);
        XMVECTOR crossaxis8 = XMVector3Cross(ObjectAaxis3, ObjectBaxis2);
        XMVECTOR crossaxis9 = XMVector3Cross(ObjectAaxis3, ObjectBaxis3);

        /**

        if (HasOverlap(objectACorners, objectBCorners, ObjectAaxis1)) { OutputDebugString(L"Has overlap on ObjectAaxis1\n"); }
        if (HasOverlap(objectACorners, objectBCorners, ObjectAaxis2)) { OutputDebugString(L"Has overlap on ObjectAaxis2\n"); }
        if (HasOverlap(objectACorners, objectBCorners, ObjectAaxis3)) { OutputDebugString(L"Has overlap on ObjectAaxis3\n"); }
        if (HasOverlap(objectACorners, objectBCorners, ObjectBaxis1)) { OutputDebugString(L"Has overlap on ObjectBaxis1\n"); }
        if (HasOverlap(objectACorners, objectBCorners, ObjectBaxis2)) { OutputDebugString(L"Has overlap on ObjectBaxis2\n"); }
        if (HasOverlap(objectACorners, objectBCorners, ObjectBaxis3)) { OutputDebugString(L"Has overlap on ObjectBaxis3\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis1))   { OutputDebugString(L"Has overlap on crossaxis1\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis2))   { OutputDebugString(L"Has overlap on crossaxis2\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis3))   { OutputDebugString(L"Has overlap on crossaxis3\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis4))   { OutputDebugString(L"Has overlap on crossaxis4\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis5))   { OutputDebugString(L"Has overlap on crossaxis5\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis6))   { OutputDebugString(L"Has overlap on crossaxis6\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis7))   { OutputDebugString(L"Has overlap on crossaxis7\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis8))   { OutputDebugString(L"Has overlap on crossaxis8\n"); }
        if (HasOverlap(objectACorners, objectBCorners, crossaxis9))   { OutputDebugString(L"Has overlap on crossaxis9\n"); }

        */
        if (!HasOverlap(objectACorners, objectBCorners, ObjectAaxis1)) { OutputDebugString(L"No overlap on ObjectAaxis1\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, ObjectAaxis2)) { OutputDebugString(L"No overlap on ObjectAaxis2\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, ObjectAaxis3)) { OutputDebugString(L"No overlap on ObjectAaxis3\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, ObjectBaxis1)) { OutputDebugString(L"No overlap on ObjectBaxis1\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, ObjectBaxis2)) { OutputDebugString(L"No overlap on ObjectBaxis2\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, ObjectBaxis3)) { OutputDebugString(L"No overlap on ObjectBaxis3\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis1))   { OutputDebugString(L"No overlap on crossaxis1\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis2))   { OutputDebugString(L"No overlap on crossaxis2\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis3))   { OutputDebugString(L"No overlap on crossaxis3\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis4))   { OutputDebugString(L"No overlap on crossaxis4\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis5))   { OutputDebugString(L"No overlap on crossaxis5\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis6))   { OutputDebugString(L"No overlap on crossaxis6\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis7))   { OutputDebugString(L"No overlap on crossaxis7\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis8))   { OutputDebugString(L"No overlap on crossaxis8\n"); }
        else if (!HasOverlap(objectACorners, objectBCorners, crossaxis9))   { OutputDebugString(L"No overlap on crossaxis9\n"); }
        else {
            OutputDebugString(L"Has collision\n");
        }
    }

    bool CollisionSystem::HasOverlap(XMFLOAT3 objectACorners[], XMFLOAT3 objectBCorners[], XMVECTOR axis) {
        float minA = std::numeric_limits<float>::max(), maxA = std::numeric_limits<float>::lowest();
        float minB = std::numeric_limits<float>::max(), maxB = std::numeric_limits<float>::lowest();
        if (XMVectorGetX(XMVector3Length(axis)) == 0.0f) {
            return true;
        }

        for (int i = 0; i < 8; i++) {
            //XMVECTOR cornerA = ProjectPoint(XMLoadFloat3(&objectACorners[i]), axis);
            //float lengthA = XMVectorGetX(XMVector3Length(cornerA));
            XMVECTOR dotProductA = XMVector3Dot(XMLoadFloat3(&objectACorners[i]), axis);
            float lengthA = XMVectorGetX(XMVector3Length(dotProductA));

            minA = fmin(minA, lengthA);
            maxA = fmax(maxA, lengthA);

            // XMVECTOR cornerB = ProjectPoint(XMLoadFloat3(&objectBCorners[i]), axis);
            // float lengthB = XMVectorGetX(XMVector3Length(cornerB));
            XMVECTOR dotProductB = XMVector3Dot(XMLoadFloat3(&objectBCorners[i]), axis);
            float lengthB = XMVectorGetX(XMVector3Length(dotProductB));

            minB = fmin(minB, lengthB);
            maxB = fmax(maxB, lengthB);

        }
        float longSpan = fmax(maxA, maxB) - fmin(minA, minB);
        float sumSpan = maxA - minA + maxB - minB;
        return longSpan < sumSpan;

        //return minB <= maxA && maxB >= minA;
    }

    XMVECTOR CollisionSystem::ProjectPoint(XMVECTOR point, XMVECTOR axis)
    {
        return (XMVector3Dot(point, axis) / XMVector3Dot(axis, axis)) * axis;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Aren't those just axis aligned bounding boxes? \$\endgroup\$ – Bálint Jul 29 '18 at 15:35
  • \$\begingroup\$ They are in this example, but they can rotate. But either way, SAT shouldn't give a false positive in this case I'm assuming \$\endgroup\$ – Raymond de la Croix Jul 29 '18 at 16:19
  • 1
    \$\begingroup\$ Your dot products are not correct. The vector dot product produces a scalar, though XMVector3Dot for some reason decides to copy that scalar into 3 vector components. When you take the length of that tripled-up vector instead of just reading one of its components, you get a value that's sqrt(3) times greater than the real dot product. That alone won't account for the error though, since it will make both the mins & maxes larger, preserving any gap that should be there. \$\endgroup\$ – DMGregory Jul 31 '18 at 12:00
  • 1
    \$\begingroup\$ Can you try logging each axis you check, and each corner's projection onto that axis, for the two skulls example that you show above? That should give us some idea of whether the axes are wrong, or the projections, or if something else funny is happening. \$\endgroup\$ – DMGregory Jul 31 '18 at 13:18
  • \$\begingroup\$ Thanks a lot for your input. I was unaware of XMVector3Dot doing this. I will give it a shot and I'll inform you of my findings. \$\endgroup\$ – Raymond de la Croix Jul 31 '18 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.