SAT Polygon Circle Collision - 解决速度方向的交点并确定碰撞的一侧

Question

概括

这个问题是用 JavaScript 编写的，但是用任何语言、伪代码或数学来回答都会很棒！

我一直在尝试实施Separating-Axis-Theorem来完成以下工作：

• 检测凸多边形和圆之间的交点。
• 找出可以应用于圆的平移以解决交点，以便圆几乎不接触多边形但不再在内部。
• 确定碰撞轴（问题末尾的详细信息）。

我已成功完成第一个要点，您可以在问题末尾看到我的 javascript 代码。我在其他部分遇到困难。

解决交叉点

网上有很多关于如何解决圆的最小/最短重叠方向上的交点的例子。你可以在我最后的代码中看到我已经计算过了。

但是，这不适合我的需求。我必须解决与圆轨迹相反方向的碰撞（假设我已经有了圆的轨迹，并希望将其作为单位向量或角度，以适合的方式传递到我的函数中）。

您可以在下图中看到最短分辨率和预期分辨率之间的差异：

如何计算用于解析test_CIRCLE_POLY函数内部相交的最小平移向量，但要应用于特定方向，与圆的轨迹相反？

我的想法/尝试：

• 我的第一个想法是在 SAT 算法中必须测试的轴上添加一个额外的轴，这个轴将垂直于圆的轨迹。然后，当投影到该轴上时，我将根据重叠进行解析。这会起作用，但在大多数情况下会解决很远的问题。它不会导致最低翻译。所以这不会令人满意。
• 我的第二个想法是继续使用最短重叠的幅度，但将方向更改为与圆的轨迹相反。这看起来很有希望，但可能还有很多我没有考虑到的边缘情况。也许这是一个不错的起点。

确定碰撞的侧面/轴

我已经找到了一种方法来确定圆与多边形的哪一边碰撞。对于多边形的每个测试轴，我只会检查重叠。如果有重叠，那一边就是碰撞。

该解决方案是不能接受的一次，因为我想弄清楚只有一个视圆的轨迹上。

我的预期解决方案会告诉我，在下面的示例图像中，轴 A 是碰撞轴，而不是轴 B。这是因为一旦解决了交点，轴 A 就是与多边形边对应的轴只是勉强触及圆圈。

我的想法/尝试：

• 目前我假设碰撞轴垂直于 MTV（最小平移向量）。这目前是不正确的，但是一旦我在问题的前半部分更新了相交解析过程，它应该是正确的轴。所以这部分应该首先解决。

• 或者，我已经考虑从圆的先前位置和它们的当前位置 + 半径创建一条线，并检查哪边与这条线相交。然而，仍然存在歧义，因为有时会有不止一侧与线相交。

到目前为止我的代码

function test_CIRCLE_POLY(circle, poly, circleTrajectory) {
    // circleTrajectory is currently not being used

    let axesToTest = [];
    let shortestOverlap = +Infinity;
    let shortestOverlapAxis;

    // Figure out polygon axes that must be checked

    for (let i = 0; i < poly.vertices.length; i++) {
        let vertex1 = poly.vertices[i];
        let vertex2 = poly.vertices[i + 1] || poly.vertices[0]; // neighbouring vertex
        let axis = vertex1.sub(vertex2).perp_norm();
        axesToTest.push(axis);
    }

    // Figure out circle axis that must be checked

    let closestVertex;
    let closestVertexDistSqr = +Infinity;

    for (let vertex of poly.vertices) {
        let distSqr = circle.center.sub(vertex).magSqr();

        if (distSqr < closestVertexDistSqr) {
            closestVertexDistSqr = distSqr;
            closestVertex = vertex;
        }
    }

    let axis = closestVertex.sub(circle.center).norm();
    axesToTest.push(axis);

    // Test for overlap

    for (let axis of axesToTest) {
        let circleProj = proj_CIRCLE(circle, axis);
        let polyProj = proj_POLY(poly, axis);
        let overlap = getLineOverlap(circleProj.min, circleProj.max, polyProj.min, polyProj.max);

        if (overlap === 0) {
            // guaranteed no intersection
            return { intersecting: false };
        }

        if (Math.abs(overlap) < Math.abs(shortestOverlap)) {
            shortestOverlap = overlap;
            shortestOverlapAxis = axis;
        }
    }

    return {
        intersecting: true,
        resolutionVector: shortestOverlapAxis.mul(-shortestOverlap),
        // this resolution vector is not satisfactory, I need the shortest resolution with a given direction, which would be an angle passed into this function from the trajectory of the circle
        collisionAxis: shortestOverlapAxis.perp(),
        // this axis is incorrect, I need the axis to be based on the trajectory of the circle which I would pass into this function as an angle
    };
}

function proj_POLY(poly, axis) {
    let min = +Infinity;
    let max = -Infinity;

    for (let vertex of poly.vertices) {
        let proj = vertex.projNorm_mag(axis);
        min = Math.min(proj, min);
        max = Math.max(proj, max);
    }

    return { min, max };
}

function proj_CIRCLE(circle, axis) {
    let proj = circle.center.projNorm_mag(axis);
    let min = proj - circle.radius;
    let max = proj + circle.radius;

    return { min, max };
}

// Check for overlap of two 1 dimensional lines
function getLineOverlap(min1, max1, min2, max2) {
    let min = Math.max(min1, min2);
    let max = Math.min(max1, max2);

    // if negative, no overlap
    let result = Math.max(max - min, 0);

    // add positive/negative sign depending on direction of overlap
    return result * ((min1 < min2) ? 1 : -1);
};

Answer 1

这可能不是您正在寻找的，但这里有一种方法可以做到这一点（如果您不是在寻找完美的精度）：
您可以尝试近似位置而不是计算它。

设置代码的方式有一个很大的优势：您可以在碰撞之前获得圆的最后位置。因此，您可以“迭代”轨迹并尝试找到最接近交叉点位置的位置。我假设您已经有一个函数可以告诉您圆是否与多边形相交。代码（C++）：

// What we need :

Vector startPos; // Last position of the circle before the collision
Vector currentPos; // Current, unwanted position
Vector dir; // Direction (a unit vector) of the circle's velocity
float distance = compute_distance(startPos, currentPos); // The distance from startPos to currentPos.
Polygon polygon; // The polygon
Circle circle; // The circle.
unsigned int iterations_count = 10; // The number of iterations that will be done. The higher this number, the more precise the resolution.

// The algorithm :

float currentDistance = distance / 2.f; // We start at the half of the distance.
Circle temp_copy; // A copy of the real circle to "play" with.
for (int i = 0; i < iterations_count; ++i) {
    temp_copy.pos = startPos + currentDistance * dir;
    if (checkForCollision(temp_copy, polygon)) {
        currentDistance -= currentDistance / 2.f; // We go towards startPos by the half of the current distance.
    }
    else {
        currentDistance += currentDistance / 2.f; // We go towards currentPos by the half of the current distance.
    }
}
    
// currentDistance now contains the distance between startPos and the intersection point
// And this is where you should place your circle :
Vector intersectionPoint = startPos + currentDistance * dir;

我还没有测试过这段代码，所以我希望其中没有大错误。它也没有优化，并且这种方法存在一些问题（交点可能最终位于多边形内部），因此它仍然需要改进，但我认为您明白了。另一个（很大，取决于你在做什么）问题是它是一个近似值，而不是一个完美的答案。
希望这可以帮助 ！