Circle-Line Collision Detection Problem

Question

I am currently developing a breakout clone and I have hit a roadblock in getting collision detection between a ball (circle) and a brick (convex polygon) working correctly. I am using a Circle-Line collision detection test where each line represents and edge on the convex polygon brick.

For the majority of the time the Circle-Line test works properly and the points of collision are resolved correctly.

Collision detection working correctly.

However, occasionally my collision detection code returns false due to a negative discriminant when the ball is actually intersecting the brick.

Collision detection failing.

I am aware of the inefficiency with this method and I am using axis aligned bounding boxes to cut down on the number of bricks tested. My main concern is if there are any mathematical bugs in my code below.

/* 
 * from and to are points at the start and end of the convex polygons edge.
 * This function is called for every edge in the convex polygon until a
 * collision is detected. 
 */

bool circleLineCollision(Vec2f from, Vec2f to)
{
    Vec2f lFrom, lTo, lLine;
    Vec2f line, normal;
    Vec2f intersectPt1, intersectPt2;
    float a, b, c, disc, sqrt_disc, u, v, nn, vn;
    bool one = false, two = false;

    // set line vectors
    lFrom = from - ball.circle.centre;      // localised
    lTo = to - ball.circle.centre;          // localised
    lLine = lFrom - lTo;                    // localised
    line = from - to;

    // calculate a, b & c values
    a = lLine.dot(lLine);
    b = 2 * (lLine.dot(lFrom));
    c = (lFrom.dot(lFrom)) - (ball.circle.radius * ball.circle.radius);

    // discriminant
    disc = (b * b) - (4 * a * c);

    if (disc < 0.0f)
    {
        // no intersections
        return false;
    }
    else if (disc == 0.0f)
    {
        // one intersection
        u = -b / (2 * a);

        intersectPt1 = from + (lLine.scale(u));
        one = pointOnLine(intersectPt1, from, to);

        if (!one)
            return false;
        return true;
    }
    else
    {
        // two intersections
        sqrt_disc = sqrt(disc);
        u = (-b + sqrt_disc) / (2 * a);
        v = (-b - sqrt_disc) / (2 * a);
        intersectPt1 = from + (lLine.scale(u));
        intersectPt2 = from + (lLine.scale(v));

        one = pointOnLine(intersectPt1, from, to);
        two = pointOnLine(intersectPt2, from, to);

        if (!one && !two)
            return false;
        return true;
    }
}

bool pointOnLine(Vec2f p, Vec2f from, Vec2f to)
{
    if (p.x >= min(from.x, to.x) && p.x <= max(from.x, to.x) && 
        p.y >= min(from.y, to.y) && p.y <= max(from.y, to.y))
        return true;
    return false;
}

Answer 1

The segment running from A to B can be computed as

P(t) = A + D · t where D is B - A and t runs from 0 to 1

Now the circle is centered on the origin (move A and B if necessary to put the center in the origin) and has radius r.

You have an intersection if for some t you get that the P has the same length of r or, equivalently, that the length of P squared is equivalent to r²

The length squared of a vector is obtained doing the dot product of a vector by himself (this is so true that if one finds a suitable operation for the dot product he can define a new and consistent concept of length)

P · P = (A + D · t) · (A + D · t) =

A·A + 2 A · D t + D · D t²

We want to find for which t we get P · P = r² so we end up to ask ourself when

A·A + 2 A · D t + D · D t² = r²

or when

D · D t² + 2 A · D t + A·A-r² = 0

this is the very famous Quadratic equation

at² +bt +c = 0

with

a = D·D; b = 2 A · D and c = A·A-r²

We have to check if the determinant b² - 4ac is positive and so we find 2 values of t that give us the intersections points P(t).

t must be between 0 and 1 otherwise we found solutions that lie on the line passing through A and B but that are before A or after B

[EDIT]

Since other questions may find some help to this answer, I decided to try to simplify the the reasoning in this edit using some images. This is the starting condition. Now focus on the segment A_B

D is the vector that moves A into B so if t is between 0 and 1, D·t is a "proper fraction" of D so the point A + D·t lies in the A_B segment: the brown points comes when t is between 0 and 1 and the dark green one is when t > 1.

Now we can simplify things if we move the circle's center into the Origin. This can be always done because is a simply change of coordinate system that preserve geometry, angles, intersection, measures etc.

Now we have a simply way to compute the lenght of P when t varies and say for which t P crosses the circle's boundaries.

As you see P' is in length greater than r while P" is less than r. Since both the vector lenght and r are positive numbers, the relation of order of being greater or less than are preserved is we compute the relation between the lenghts squared and the radius squared. P*1 and P*2 are the point that makes the |P|² equal to r²

As mentioned in the pre-edit section, we arrive to get a quadratic equation where t is our variable. As is known solution values of t range from the case when t is a couple of complex numbers - that means no intersection; the case when t are two equal solution - that means that there is one intersection; the case when there are two distinct solutions- that means that there are two intersections.

The Discriminant is used to discriminate the previous condition and a validity test is done on t to see if it a valid intersection but outside our segment - i.e. the solution t has to be real and between 0 and 1 to be considered a proper intersection that fall in the segment A_B