在 OpenGL 引擎中正确获取 OBB-Triangle 碰撞检测

Question

我想实现地形碰撞。我有一个名为 GeoTerrain 的 class。它的构造函数将图片作为参数，然后用三角形构建一个地形，每个亮像素的顶点都高，每个暗像素的顶点都低。这让我不得不在 OBB 撞击地形时对其实施适当的碰撞检测。但我的临时解决方案远非稳健。

这是我目前的做法：每个表面三角形都有自己的小碰撞盒，由 6 个顶点组成（三角形表面上的 3 个顶点和三个附加顶点，它们基本上是 3 个表面顶点，但向下移动表面法线（因此它们位于可见表面下方）。

原因：因为我不知道如何在没有碰撞盒体积的情况下计算最小平移向量。

抱歉，代码太长了 - 我尽量多发表评论：

// This method resides in the Hitbox class.
// The hitbox instance then checks against the other object (parameter):
private IntersectionObject TestIntersectionTerrain(GeoTerrain terra)
{
    Vector3 mtv = new Vector3(0, 0, 0);
    Vector3 mtvTotal = new Vector3(0, 0, 0);
    float shape1Min, shape1Max, shape2Min, shape2Max;

    // Select all triangles within reach of the OBB hitbox:
    List<GeoTriangle> triangles = terra.GetTrianglesForHitbox(this);

    // Loop through all triangles and check collision
    // (cannot be more than 8 triangles, right now)
    foreach (GeoTriangle triangle in triangles)
    {
        bool bothOverlap = false;
        mtv = Vector3.Zero;
        bool error;
        bool breakDone = false;
        float mtvDistance = float.MaxValue;
        float mtvDirection = 1;

        // loop through all hitbox normals (three normals):
        for (int i = 0; i < mNormals.Length; i++)
        {
            error = false;

            // project the current vertices of objects' hitbox and triangle hitbox to find
            // both shapes' minimum and maximum:
            SATtest(CurrentHitBoxNormals[i], CurrentHitBoxVertices, out shape1Min, out shape1Max);
            SATtest(CurrentHitBoxNormals[i], triangle.VerticesHitbox, out shape2Min, out shape2Max);
            if (!Overlaps(shape1Min, shape1Max, shape2Min, shape2Max))
            {
                bothOverlap = false;
                breakDone = true;
                break;
            }
            else
            {
                // calculate MTV: 
                CalculateOverlap(
                    CurrentHitBoxNormals[i], // normals (here, the meshes' hitbox normals)
                    ref shape1Min,
                    ref shape1Max,
                    ref shape2Min,
                    ref shape2Max, 
                    out error,
                    ref mtvDistance,
                    ref mtv,
                    ref mtvDirection,
                    mCenterTranslated, // object's hitbox volume center (world space)
                    triangle.CenterHitbox); // triangle's hitbox volume center (world space)
            }

            // do the same but now for the triangle's normal
            // (right now this unnecessarily also gets looped 3 times):
            SATtest(triangle.Normal, CurrentHitBoxVertices, out shape1Min, out shape1Max);
            SATtest(triangle.Normal, triangle.VerticesHitbox, out shape2Min, out shape2Max);
            if (!Overlaps(shape1Min, shape1Max, shape2Min, shape2Max))
            {
                bothOverlap = false;
                breakDone = true;
            }
            else
            {
                CalculateOverlap(triangle.Normal, ref shape1Min, ref shape1Max, ref shape2Min, ref shape2Max,
                    out error, ref mtvDistance, ref mtv, ref mtvDirection, mCenterTranslated, triangle.CenterHitbox);
                bothOverlap = true;
            }
        }
        if (bothOverlap && !breakDone && mtv != Vector3.Zero)
        {
            // add the current mtv to the total MTV (of all triangles)
            // but only add more to it, if the current MTV has a bigger shift in
            // one direction than the previous MTVs:
            mtvTotal.X = Math.Abs(mtv.X) > Math.Abs(mtvTotal.X) ? mtv.X : mtvTotal.X;
            mtvTotal.Y = Math.Abs(mtv.Y) > Math.Abs(mtvTotal.Y) ? mtv.Y : mtvTotal.Y;
            mtvTotal.Z = Math.Abs(mtv.Z) > Math.Abs(mtvTotal.Z) ? mtv.Z : mtvTotal.Z;
        }

    }

    if (mtvTotal != Vector3.Zero)
    {
        IntersectionObject o = new IntersectionObject();
        o.IntersectingGameObject = terra.Owner;
        o.MinimumTranslationVector = mtvTotal;
        o.MeshNumber = 0;
        o.MeshName = terra.Owner.Name;

        return o;
    }
    else
    {
        return null;
    }
}

private void CalculateOverlap(Vector3 axis, ref float shape1Min, ref float shape1Max, ref float shape2Min, ref float shape2Max, out bool error, ref float mtvDistance, ref Vector3 mtv, ref float mtvDirection, Vector3 posA, Vector3 posB)
{
    float d0 = (shape2Max - shape1Min); 
    float d1 = (shape1Max - shape2Min);
    float intersectionDepthScaled = (shape1Min < shape2Min)? (shape1Max - shape2Min) : (shape1Min - shape2Max);

    float axisLengthSquared = Vector3.Dot(axis, axis);
    if (axisLengthSquared < 1.0e-8f)
    {
        error = true;
        return;
    }
    float intersectionDepthSquared = (intersectionDepthScaled * intersectionDepthScaled) / axisLengthSquared;

    error = false;

    if (intersectionDepthSquared < mtvDistance || mtvDistance < 0)
    {
        mtvDistance = intersectionDepthSquared;
        mtv = axis * (intersectionDepthScaled / axisLengthSquared);
        float notSameDirection = Vector3.Dot(posA - posB, mtv);
        mtvDirection =  notSameDirection < 0 ? -1.0f : 1.0f;
        mtv = mtv * mtvDirection;
    }

}

问题是：它可以工作，但不能在边缘工作。使用我的方法（三角形表面下方的隐形碰撞箱），玩家有时会撞到一堵看不见的墙，因为 MTV 告诉他向上移动（好）和侧向移动（不好）。从数学上讲这是正确的，因为如果玩家沉入假三角形体积，mtv 当然可以决定在需要时将他移回到多个轴上。

有什么方法可以通过检查平面三角形来获得 MTV 吗？我找到了几个链接，告诉我 "if" 有一个交叉点。但是我没有找到获得 MTV 的可以理解的解决方案。我想我需要找出玩家必须沿表面法线向后移动多少？

编辑 (2019-02-12 22:00)

我根据第一个答案更新了代码。但是在应用计算的 MTV 时，我仍然会出现奇怪的行为。这是我当前的算法：

我的更新碰撞检测算法方法是：

获取靠近玩家的三角形列表
获取 OBB 顶点和法线
遍历该三角形列表并为每个三角形做（现在最多 ~8 个）：
使用三角形的法线并投影三角形的顶点和 OBB 的顶点。
使用 OBB 的法线 #1 并投影三角形的顶点和 OBB 的顶点。
使用 OBB 的法线 #2 并投影三角形的顶点和 OBB 的顶点。
使用 OBB 的法线 #3 并投影三角形的顶点和 OBB 的顶点。
交叉你告诉我的向量（第 5 步到第 13 步）并将三角形的顶点和 OBB 的顶点投影到这些向量的规范化版本上
仅当前一步导致重叠时才执行每个步骤。然后将重叠长度存储在一个数组中（13 个单元格，每个步骤一个）
如果每个投影都导致重叠，请通过计算最小重叠和相应的轴向量来查找 mtv。
将此向量乘以重叠并将其用作 MTV。

差不多吧？

Answer 1

SAT（分离轴定理）算法将很容易地为您提供最小平移向量，适用于任何类型的凸形，还可以包括三角形、四边形、平面多边形。

以蛮力的方式，SAT 分两步进行，再经过几步才能获得 MTV。

查找要测试的最小分离轴列表。
- 例如，对于 OBB，您需要考虑三个方向面和边的三个方向。
将两个凸形投影到分离轴上，得到投影间隔。
- 例如，对于每个形状，将其所有顶点与轴进行点积方向.
- 最小值和最大值将为您提供每个形状的间隔。
如果两个区间不相交，对象是spearate，不相交。
如果所有间隔在每个spearation轴上相交，则对象相交。
要找到MTV，找到所有散布轴间隔中的最小重叠。
区间重叠，结合分离轴方向，给你MTV

对于凸多面体，要测试的分离轴非常简单。他们是：

每个形状的表面法线，称之为A和B。
A的每条边与B的每条边的叉积
有一些优化，例如，不需要用相反方向，或相似方向。
例如，需要测试 OBB 的三个面法线和三个边缘方向。

注意：MTV 可能并不总是解决您问题的最佳方法，尤其是当我们谈论地形时。

在 OpenGL 引擎中正确获取 OBB-Triangle 碰撞检测

Getting OBB-Triangle collision detection right in OpenGL engine

c#

mesh

collision-detection

bounding-box