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

Question

总结

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

我一直在尝试实现 Separating-Axis-Theorem完成以下工作:

检测凸多边形和圆之间的交点。

找出可应用于圆的平移以解决相交问题，使圆几乎不接触多边形，但不再在内部。

确定碰撞的轴(问题末尾的详细信息)。

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

解决交集

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

但是，这不适合我的需要。我必须解决圆轨迹相反方向的碰撞(假设我已经有了圆的轨迹，并希望将它作为单位向量或 Angular 传递到我的函数中，以适合者为准)。

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



如何计算最小平移向量以解决我的 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

我假设多边形是凸的，并且圆沿着直线移动(至少在一段可能很小的时间间隔内)并且没有遵循一些弯曲的轨迹。如果它遵循弯曲的轨迹，那么事情就会变得更加困难。在曲线轨迹的情况下，可以保留基本概念，但实际的碰撞点(圆的碰撞分辨率点)可能更难计算。不过，我正在概述一个想法，它也可以扩展到这种情况。另外，它可以作为圆和凸多边形之间碰撞检测的主要方法。
我没有考虑所有可能的情况，可能包括特殊或极端的情况，但至少它给了你一个探索的方向。
在您的脑海中将圆与多边形之间的碰撞转换为圆心(一个点)与被圆半径加厚的多边形版本之间的碰撞r ，即 (i) 多边形的每条边向外偏移(平移)半径 r沿着垂直于它并指向多边形外部的向量，(ii) 顶点变为半径为 r 的圆弧，以多边形顶点为中心并连接适当的相邻偏移边的端点(基本上，将半径为 r 的圆放在多边形的顶点处并取它们的凸包)。

现在，圆心的当前位置是C = [ C[0], C[1] ]它一直沿直线移动，方向矢量V = [ V[0], V[1] ]指向运动方向(或者如果您愿意，可以将 V 视为检测到碰撞时圆的速度)。然后，向量方程 X = C - t * V 定义了一个轴(或者说是一条射线 - 一条有向半线)。 , 其中 t >= 0 (该轴指向过去的轨迹)。基本上，这是通过中心点 C 的半线。并且与向量 V 对齐/平行.现在，分辨率点，即您要将圆圈移动到的点是轴 X = C - t * V 的点。与加厚多边形的边界相交。
因此，您必须检查 (1) 第一个轴相交的边缘，然后 (2) 轴与与原始多边形顶点有关的圆弧相交。
假设多边形由顶点数组P = [ P[0], P[1], ..., P[N], P[0] ]给出逆时针方向。
(1) 对于每条边 P[i-1]P[i]原始多边形的，与您的碰撞相关(这些可能是在检测到碰撞的顶点处相遇的两个相邻边缘，或者实际上可能是在圆以非常高的速度移动的情况下的所有边缘并且您有很晚才检测到碰撞，因此实际碰撞甚至没有发生在那里，我把这留给你，因为你更了解你的情况的细节)执行以下操作。您有作为输入数据:

C = [ C[0], C[1] ]
V = [ V[0], V[1] ]
P[i-1] = [ P[i-1][0],  P[i-1][1] ]
P[i] = [ P[i][0],  P[i][1] ]

做:

Normal = [ P[i-1][1] - P[i][1], P[i][0] - P[i-1][0] ];
Normal = Normal / sqrt((P[i-1][1] - P[i][1])^2 + ( P[i][0] - P[i-1][0] )^2); 
// you may have calculated these already

Q_0[0] = P[i-1][0] + r*Normal[0];
Q_0[1] = P[i-1][1] + r*Normal[1];

Q_1[0] = P[i][0]+ r*Normal[0]; 
Q_1[1] = P[i][1]+ r*Normal[1]; 

求解s, t线性方程组(相交方程):

Q_0[0] + s*(Q_1[0] - Q_0[0]) = C[0] - t*V[0];
Q_0[1] + s*(Q_1[1] - Q_0[1]) = C[1] - t*V[1];

如果 0<= s <= 1和 t >= 0 ，你完成了，你的解决点是

R[0] = C[0] - t*V[0];
R[1] = C[1] - t*V[1];

别的
(2) 对于每个顶点P[i]与您的碰撞相关，请执行以下操作:
求解t二次方程(有明确的公式)

norm(P[i] - C + t*V )^2 = r^2

或扩展:

(V[0]^2 + V[1]^2) * t^2 + 2 * ( (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1] )*t + ( P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 )  - r^2 = 0

或者，如果您更喜欢类似代码的方式:

a = V[0]^2 + V[1]^2;
b = (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1];
c = (P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 - r^2;
D = b^2 - a*c;

if D < 0 there is no collision with the vertex 
i.e. no intersection between the line X = C - t*V 
and the circle of radius r centered at P[i]

else
D = sqrt(D);
t1 = ( - b - D) / a;
t2 = ( - b + D) / a;  
where t2 >= t1 

那么你的解决点是

R[0] = C[0] - t2*V[0];
R[1] = C[1] - t2*V[1];