Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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;
}
share|improve this question
    
I can't find any difference between lLine and line... –  FxIII Oct 10 '11 at 9:21
    
The pointOnLine test can be simplified and done before computing the actual point. –  FxIII Oct 10 '11 at 9:25
    
how sqrt_disc is computed? –  FxIII Oct 10 '11 at 9:26
    
Sorry FxIII I must have gotten a little confused when I was localising my vectors I didn't realise the vectors would equal the same when they were subtracted from each other. I was cleaning up my code a bit before I posted and I forgot to put sqrt_disc = sqrt(disc); back in. Thanks very much for your answer below it helped me a lot. –  jazzdawg Oct 10 '11 at 11:19

1 Answer 1

up vote 18 down vote accepted

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

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

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. starting condition This is the starting condition. Now focus on the segment A_B

Segment running from A to 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.

circle moving to center

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.

Examples

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

share|improve this answer
3  
This is the right algorithm to use. A really good description of how to it works can be found in Real Time Rendering Third Edition, pages 787 to 791. If you can find it in a library, well worth a look. –  Darcy Rayner Oct 10 '11 at 10:55
4  
With the 8th upvote to this answer, I have reached 2k reputation points. I greatly appreciate the trust you have placed in me. This is both a recognition of my efforts and a stimulus to continue to do my best in producing highest possible quality answer. Thank you –  FxIII Oct 13 '11 at 7:11
    
Hang on, does this account for the two corner cases correctly? For instance, a circle may cross the plane defined by the line outside of t0 <= t <= t1, but hit the end points of the line segment a bit later. You need to check the minimum distance between the line end points and the circles path. If that distance is smaller than the circle radius, then the line has been hit. –  Darcy Rayner Oct 16 '11 at 1:31
    
@DarcyRayner do you mean the case when both points are inside the circle area? –  FxIII Oct 16 '11 at 8:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.