c# - 如何防止点-多边形滑动碰撞检测中的浮点错误

问题描述

我正在尝试编写一个函数来处理我正在编程的游戏中的运动。我所拥有的几乎可以工作，但是在某些情况下它会崩溃。

我编写了一个最小的演示示例，如下所示。在这个例子中，我试图计算一个物体的行程，由一个点和运动矢量表示。该对象的移动路径根据一组多边形进行检查，这些多边形被分解为线段以进行测试。当该对象与线段碰撞时，我希望它沿着该线段滑动（而不是停止或弹开）。

为此，我沿着我的预期路径检查是否有碰撞，如果我找到一个交叉点，我会从那个交叉点沿着我碰撞过的线段的路径进行一个新的测试，以及剩余运动的大小.

当我们沿线段滑入“口袋”时，问题就出现了。通常，碰撞检查会通过形成口袋的两条线段，并且物体会滑过。因为我平行于其中一条线段行进，并且在端点处与两条线段相交，所以我相信这个问题是由浮点错误引起的。它是否溜过，被抓住，或者被抓住一次然后在第二次检查时溜过似乎是完全随机的。

我正在使用在这里找到的简单算法计算交集：https ://stackoverflow.com/a/20679579/4208739 ，但我也尝试了许多其他算法。都表现出同样的问题。

（Vector2 是 Unity 库提供的类，它只是将 x 和 y 坐标保存为浮点数。Vector2.Dot 函数只是计算点积）。

//returns the final destination of the intended movement, given the starting position, intended direction of movement, and provided collection of line segments
//slideMax provides a hard cap on number of slides allowed before we give up
Vector2 Move(Vector2 pos, Vector2[] lineStarts, Vector2[] lineEnds, Vector2 moveDir, int slideMax)
{
    int slideCount = 0;
    while (moveDir != Vector2.zero && slideCount < slideMax)
    {
        pos = DynamicMove(pos, lineStarts, lineEnds, moveDir, out moveDir);
        slideCount++;
    }
    return pos;
}

//returns what portion of the intended movement can be performed before collision, and the vector of "slide" that the object should follow, if there is a collision
Vector2 DynamicMove(Vector2 pos, Vector2[] lineStarts, Vector2[] lineEnds, Vector2 moveDir, out Vector2 slideDir)
{
    slideDir = Vector2.zero;
    float moveRemainder = 1f;
    for (int i = 0; i < lineStarts.Length; i++)
    {
        Vector2 tSlide;
        float rem = LineProj(pos, moveDir, lineStarts[i], lineEnds[i], out tSlide);
        if (rem < moveRemainder)
        {
            moveRemainder = rem;
            slideDir = tSlide;
        }
    }
    return pos + moveDir * moveRemainder;
}

//Calculates point of collision between the intended movement and the passed in line segment, also calculate vector of slide, if applicable
float LineProj(Vector2 pos, Vector2 moveDir, Vector2 lineStart, Vector2 lineEnd, out Vector2 slideDir)
{
    slideDir = new Vector2(0, 0);
    float start = (lineStart.x - pos.x) * moveDir.y - (lineStart.y - pos.y) * moveDir.x;
    float end = (lineEnd.x - pos.x) * moveDir.y - (lineEnd.y - pos.y) * moveDir.x;
    if (start < 0 || end > 0)
        return 1;
    //https://stackoverflow.com/a/20679579/4208739
    //Uses Cramer's Rule
    float L1A = -moveDir.y;
    float L1B = moveDir.x;
    float L1C = -(pos.x *(moveDir.y + pos.y) - (moveDir.x + pos.x)*pos.y);
    float L2A = lineStart.y - lineEnd.y;
    float L2B = lineEnd.x - lineStart.x;
    float L2C = -(lineStart.x * lineEnd.y - lineEnd.x * lineStart.y);
    float D = L1A * L2B - L1B * L2A;
    float Dx = L1C * L2B - L1B * L2C;
    float Dy = L1A * L2C - L1C * L2A;
    if (D == 0)
        return 1;
    Vector2 inter = new Vector2(Dx / D, Dy / D);
    if (Vector2.Dot(inter - pos, moveDir) < 0)
        return 1;
    float t = (inter - pos).magnitude / moveDir.magnitude;
    if (t > 1)
        return 1;
    slideDir = (1 - t) * Vector2.Dot((lineEnd - lineStart).normalized, moveDir.normalized) * (lineEnd - lineStart).normalized;
    return t;
}

是否有某种方法可以计算不受此类问题影响的碰撞？我想我不能完全消除浮点错误，但是有没有办法检查至少可以保证我与口袋里的两条线段中的一条相撞？或者以这种方式处理事情是否存在更根本的错误？

如果有什么不清楚的地方，我可以画图或写例子。

编辑：对这个问题进行了更多的思考，并响应 Eric 的回答，我想知道将我的数学从浮点转换为定点是否可以解决这个问题？在实践中，我真的只是将我的值（可以舒适地适应在 -100 到 100 的范围内）转换为整数，然后在这些约束下执行数学运算？我还没有把所有的问题拼凑在一起，但我可能会尝试一下。如果有人有任何关于此类的信息，我将不胜感激。

标签： c#collision-detectiongame-physicsfloating-accuracy

c# - 如何防止点-多边形滑动碰撞检测中的浮点错误

问题描述

解决方案

推荐阅读