A fast collision detection between a circle and a sprite in pixel perfect

Question

I've been thinking on some fast and brilliant pixel - perfect collision detection between a circle and any sprite. I need to get 2 points of collision to be able to calculate a normal vector out of them later. I managed to come up with some solution but the more scaling is done in my game, the more inaccurate and unprecise this collision is...It seems as if the code I posted below, was good and correct becouse I have been checking it already a few times and spent a few days reading it again and again... I also checked visually that the collision masks and areas of collision are calculated perfectly fine in the code below so the problem definitely doesn't lay there but in this method.

So I guess that the problem here is the loss of data in floating point arithmetic unless somebody finds a flaw in this method?

If however the problem is really with the float loss of data, what other solution would you recommend to find 2 points of collision between circle and any other sprite in pixel perfect? I really liked my solution becouse it was relatively fast

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

edit: Actually, what I'm doing in this method is finding points of intersection between circle and a sprite

edit: Ok, I'm uploading images to describe my algorithm a bit better. I really tried my best to explain it but if there's still something missing, let me know please!

Also I would accept any other good solutions to find intersection points between a circle and any sprite in pixel perfect, if you don't want to check my code :(... Eh, I'm always having problems with collisions...

Answer 1

If you absolutely want (or need) pixel perfect, your solution looks good. don't forget to first make a rectangle-to-rectangle collision before testing a pixel perfect detection, to avoid unneeded processings.

If you want another accurate method which maybe more efficient, look for Separating Axis Theorem.

You can find more information about it here :

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

and here :

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

The last one have nice interactive explanation and demonstration. Enjoy :)

Answer 2

...as I was not able to show the raster in the comments:

---

I did not mentally parse your code, however from the image I see that you try to detect borderline collisions. Putting round or diagonal (border)lines into a raster may cause occasions, where two crossing lines do not overlay each other - like this:

1 2

2 1

whereby 1 would be line 1 and 2 would be line 2.

---

However I still like the idea of checking border lines combined with rectangle pre-checks. If you would render an array of raster proved-closed line coordinates by sprites you could check them against each other. This could also be enriched by border line segmenting (such as North, East, West and South or a bit more fine grain - I guess there is an optimum). A diagonal proved-closed line in the check data set must represent something like this:

x _

x x

whereby the x represent the pixels of your line and the _ is an empty raster seat.