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

Question

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

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

为此，我沿着预期的碰撞路径进行检查，如果找到了相交点，则沿着相交的线段的路径从该相交点进行新的测试，并计算其余运动的幅度。

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

我正在使用在这里找到的简单算法来计算交集：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;
    ///sf/answers/1447570561/
    //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的范围内合适地转换）为int，然后在这些约束下执行数学运算？我还没有解决所有问题，但是我可以尝试一下。如果有人有任何类似的信息，我将不胜感激。

Answer 1

理想情况下，您有一条线精确瞄准一个点，即线段的端点。这意味着计算中的任何错误，无论多么小，都可能说这条线没有抓住重点。我看到三个潜在的解决方案：

\n\n

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

\n\n

看起来第三个是最简单的\xe2\x80\x94形成口袋的两条线段可以稍微延长一点，所以它们交叉。那么滑动路径就不会瞄准一个点；它将针对段的内部，并且存在误差范围。

\n