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

Question

我正在尝试编写一个函数来处理我正在编写的游戏中的移动。我所拥有的几乎可以正常工作，但在某些情况下会出现故障。

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

为此，我会沿着预定路径检查碰撞情况，如果找到交叉点，我会从该交叉点沿着我碰撞过的线段的路径进行新测试，测试幅度为剩余的运动。

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

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

(Vector2 是 Unity 库提供的类，它只是将 x 和 y 坐标保存为 float 。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 的回答，我想知道将我的数学从 float 转换为定点数是否可以解决这个问题？在实践中，我真的只是将我的值(可以在 -100 到 100 的范围内舒适地适应)转换为整数，然后在这些约束下执行数学运算？我还没有将所有问题拼凑在一起，但我可以尝试一下。如果有人有任何类似的信息，我将不胜感激。

Answer 1

理想情况下，您有一条线正好对准一个点，即线段的端点。这意味着计算中的任何错误，无论多么小，都可能说这条线没有捕获要点。我看到三种可能的解决方案:

• 分析算术并设计它以确保它没有错误地完成，也许通过使用扩展精度技术。
• 分析算法并对其进行设计，以确保它在完成时出现轻微的有利于碰撞的错误，或许可以通过添加轻微的碰撞偏差来实现。
• 稍微延长线段。

看起来第三个最简单——形成口袋的两条线段可以稍微延长一点，所以它们会交叉。那么滑动路径就不会瞄准一点；它会瞄准一个段的内部，并且会有误差。