在pixel perfect中快速检测圆和精灵之间的碰撞

Question

我一直在考虑在圆和任何精灵之间进行一些快速和出色的像素完美碰撞检测。我需要得到两个碰撞点，以便稍后能够计算出它们的法向量。我设法想出了一些解决方案，但在我的游戏中进行的缩放越多，这个碰撞is...It看起来就越不准确和不精确，就好像我在下面发布的代码是好的和正确的，因为我已经检查了几次，花了几天时间反复阅读它……我还直观地检查了碰撞遮罩和碰撞区域在下面的代码中计算得很好，所以问题肯定不在那里，而是在这个方法中。

所以我猜这里的问题是浮点运算中的数据丢失，除非有人在这个方法中发现一个缺陷？

然而，如果问题真的是数据的浮动丢失，你会推荐什么其他的解决方案来找到圆圈和像素完美的任何其他精灵之间的两个冲突点？我真的很喜欢我的解决方案，因为它相对较快

int xOffset1 = (int)colRectLeft;  // left boundary of the collision area for the first sprite
int xOffset2 = (int)colCircleLeft; // left boundary of the collision area for the circle sprite
int yOffset1 = (int)colRectBottom; // bottom boundary of the collision area for the first sprite
int yOffset2 = (int)colCircleBottom; // bottom boundary of the collision area for the circle sprite
int width = (int)(colCircleRight - colCircleLeft); //width of the collision area - same for both sprites
int height = (int)(colCircleTop - colCircleBottom); // height of the collision area same for both sprites

// Pixel-perfect COLLISION DETECTION between circle and a sprite
// my custom vector classes - nothing special
Math2D.Vector_2 colRightPoint = new Math2D.Vector_2(-1, -1); // The right point of collision lying on the circle's circumference
Math2D.Vector_2 colLeftPoint = new Math2D.Vector_2(-1, -1); // the left point of collision lying on the circle's circumference
boolean colRightFound = false;
boolean colLeftFound = false;

// I'm going through y in the circle's area of collision
for (float y = yOffset2; y < yOffset2 + height; y += 1)
{
    // from equation: (x-Sx)^2 + (y-Sy)^2 = r^2
    // x1/2 = (+-)sqrt(r^2 - (y - Sy)^2) + Sx
    //(Sx, Sy) is (circle's radius, circle's radius) becouse I want the points on the circle's circumference to have positive coordinates
    float x1 =  (float) (Math.sqrt(radius*radius - (y - radius)*(y - radius)) + radius); // the right pixel on the circumference
    float x2 =  (float) (-x1 + 2*radius); // the left pixel on the circumference

    //first I check if the calculated x is inside of the previously calculated area of collision for both circle's area and a sprite's area
    if (x1 >= xOffset2 &&
        x1 <= xOffset2 + width &&
        xOffset1 + x1 - xOffset2 < rectFrameW &&
        yOffset1 + (int)y-yOffset2 < rectFrameH &&
        yOffset1 + (int)y-yOffset2 > 0 &&
        xOffset1 + x1 - xOffset2 > 0)
    {
        //I don't have to check if the point on the circle's circumference is opaque becouse it's always so just check if the same point translated to sprite's area of collision is opaque
        boolean opaqueRectPixel = go.gameData.images.get(go.pic_nr)
            .collision_mask[(int)((yOffset1 + (int)y-yOffset2)*rectFrameW +
                                  (xOffset1 + x1 - xOffset2))];

        if(opaqueRectPixel)
        {
            if(!colRightFound)
            {
                colRightPoint.x = (xOffset1 + x1 - xOffset2);
                colRightPoint.y = (yOffset1 + (int)y - yOffset2);
                colRightFound = true;
            }
            else if(!colLeftFound)
            {
                colLeftPoint.x = (xOffset1 + x1 - xOffset2);
                colLeftPoint.y = (yOffset1 + (int)y - yOffset2);
            }
        }
    }

    //the same logic for the left point on the circle's circumference
    if (x2 >= xOffset2 &&
        x2 <= xOffset2 + width &&
        xOffset1 + x2 - xOffset2 < rectFrameW &&
        yOffset1 + (int)y-yOffset2 < rectFrameH &&
        yOffset1 + (int)y-yOffset2 > 0 &&
        xOffset1 + x2 - xOffset2 > 0)
    {
        boolean opaqueRectPixel = go.gameData.images.get(go.pic_nr)
            .collision_mask[(int)((yOffset1 + (int)y-yOffset2)*rectFrameW +
                                  (xOffset1 + x2 - xOffset2))];

        if(opaqueRectPixel)
        {
            if(!colLeftFound)
            {
                colLeftPoint.x = (xOffset1 + x2 - xOffset2);
                colLeftPoint.y = (yOffset1 + (int)y - yOffset2);
                colLeftFound = true;
            }
            else if(!colRightFound)
            {
                colRightPoint.x = (xOffset1 + x2 - xOffset2);
                colRightPoint.y = (yOffset1 + (int)y - yOffset2);
            }
        }
    }

    // if both points are already found, finish
    if(colLeftFound && colRightFound)
        break;
}

编辑:实际上，我在这个方法中做的是寻找圆和精灵之间的交点

编辑:好的，我上传图片是为了更好地描述我的算法。我真的尽力解释了，但是如果还有什么遗漏的地方，请告诉我！

​

​

​

​

另外，如果你不想检查我的代码，我会接受任何其他好的解决方案来在像素完美中找到圆和任何精灵之间的交点:(...呃，我总是遇到碰撞的问题……

Answer 1

如果你绝对想要(或需要)完美的像素，你的解决方案看起来不错。在测试像素完美检测之前，不要忘记首先进行矩形到矩形的碰撞，以避免不必要的处理。

如果你想要另一种更有效的精确方法，那就去找分离轴定理吧。

你可以在这里找到更多关于它的信息：

http://rocketmandevelopment.com/blog/separation-of-axis-theorem-for-collision-detection/

还有这里：

http://www.metanetsoftware.com/technique/tutorialA.html

最后一个有很好的交互式解释和演示。享受:)

Answer 2

...as我无法在评论中显示栅格：

我没有在脑海中解析你的代码，但是从图像中我看到你试图检测边界冲突。将圆线或对角线(边框)放入光栅中可能会出现两条交叉线彼此不重叠的情况，如下所示：

1 2

2 1

其中1将是行1，而2将是行2。

然而，我仍然喜欢检查边界线和矩形预检查相结合的想法。如果你想通过精灵呈现一个栅格证明闭合的线坐标数组，你可以相互检查它们。这也可以通过边界线分割(例如北、东、西和南，或者更细的粒度-我想有一个最优的)来丰富。检查数据集中的对角证明闭合线必须表示如下所示：

X_

X x

其中x表示您的线的像素，而_是一个空的光栅位置。