时间戳

首页 > 解决方案 > 分离轴定理错误触发

c++ - 分离轴定理错误触发

问题描述

我正在用 C++ 编写一些代码来使用分离轴定理测试碰撞，并且在某些方向上它错误地触发了发生碰撞

我正在关注本教程，但是该教程仅是 2D 的，我正在尝试以 3D 实现它，尽管我认为它应该仍然是相同的。

我现在拥有的算法不会错过任何碰撞，但是对于两个框的某些方向，它认为它们实际上没有发生碰撞。可以在这里看到一个例子，根据下面的代码，这两个盒子显然是碰撞的。

假碰撞

代码是用 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);
}

算法：

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);
}

标签： c++collision-detectioncollisionseparating-axis-theorem

解决方案

教程仅在 2D 中，我正在尝试在 3D 中实现它，尽管我认为它应该仍然是相同的

不幸的是，事实并非如此。3D 案例稍微复杂一些。要检查两个复杂形状是否在 3D 中发生碰撞，您需要检查每个面的法线（您这样做）以及垂直于每个对象边缘的方向（您会错过这些）。

因此，对于边缘方向为 A0、A1、A2 和 B0、B1、B2 的框（A 和 B），我们有：

  • A的3个法线
  • B的3个法线
  • 9 个方向：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

所以你只需要添加缺少的 9 个检查。

进一步说明：您不需要调整法线。我的意思是不需要这条线：

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

在这种情况下，它不会造成任何伤害。但对于更复杂的形状，它实际上可能会使测试不正确。

推荐阅读