java - 像素完美的圆形和 Sprite 之间的快速碰撞检测

Question

我一直在考虑一些快速而出色的像素 - 圆和任何 Sprite 之间的完美碰撞检测。我需要获得 2 个碰撞点，以便稍后能够计算出法 vector 。我设法想出了一些解决方案，但是我的游戏中进行的缩放越多，这种碰撞就越不准确和不精确......看起来我在下面发布的代码是好的且正确的，因为我已经检查过它几次，花了几天时间一遍又一遍地阅读......我还目视检查了碰撞掩模和碰撞区域在下面的代码中计算得非常好，所以问题肯定不在那里，而是在这个方法中。

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

但是，如果问题确实在于数据的 float 丢失，您会建议使用什么其他解决方案来找到圆和任何其他像素完美的 Sprite 之间的 2 个碰撞点？我真的很喜欢我的解决方案，因为它相对较快

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;
}

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

编辑:好的，我正在上传图像以更好地描述我的算法。我真的尽力解释了，但如果还有什么遗漏，请告诉我!

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

Answer 1

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

如果您想要另一种可能更有效的准确方法，请寻找分离轴定理。

您可以在这里找到更多相关信息:

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

这里:

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

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