Circle-Line Collision Detection Problem
- by jazzdawg
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;
}
