Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Circle/Rectangle Collision Detection

This thread is locked; no one can reply to it. rss feed Print
Circle/Rectangle Collision Detection
TestSubject
Member #8,989
August 2007
avatar

Circle/circle and rectangle/rectangle collision detection is incredibly easy, but circle/rectangle is a harder. I know that pixel-perfect can be done by pretty much testing for any overlap in the shapes, but is there a quicker way? If I do resort to pixel perfect, I'd probably first test a bounding box, to save time.

Also, if a circle bounces off of a corner, what would be the effect? What would model that? I was thinking that a 45° angle would be roughly correct, but I realized that I had no idea what would actually happen.

Mark Oates
Member #1,146
March 2001
avatar

You'll probably want to start getting into the separating axis theorem.

Are your boxes rotated? If not, it should be relatively easy to work something out without needing SAT.

Arthur Kalliokoski
Second in Command
February 2005
avatar

If circle-circle collisions are incredibly easy, it seems to me that you could "cheat" at rectangle corners by emulating an arbitrarily small circle at the corner.

For the sides of the rectangle I'd simply bounce the center of the circle (which is a point after all) off of a line that's offset from the rectangle by the radius of the circle.

They all watch too much MSNBC... they get ideas.

gnolam
Member #2,030
March 2002
avatar

Axis-aligned or object-oriented?
If the former, you can just check (center + radius > left side) && (center - radius < right side) && (center + radius > upper side) && (center - radius < lower side). The latter is slightly more complicated but works on pretty much the same principle...

If circle-circle collisions are incredibly easy

They are.

if distance from center1 to center2 < radius1 + radius2
   collision
else
   no collision

It generalizes to spheres as well. It doesn't even require any costly mathematical functions, since you can check for distance squared < radius1 squared + radius2 squared instead and do away with the square root in the distance calculation.

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

Mark Oates
Member #1,146
March 2001
avatar

gnolam said:

Axis-aligned or object-oriented?

just "oriented", as in "axis-aligned or oriented?"

Arthur Kalliokoski
Second in Command
February 2005
avatar

Detecting collisions is easier than calculating the correct collision response.

They all watch too much MSNBC... they get ideas.

james_lohr
Member #1,947
February 2002

Didn't we have a thread on this just the other day?

Anyway, one way to do it properly is to start with circle - line-segment collision. This is done by finding the perpendicular distance of the centre of the circle to the line-segment. If this is smaller than the radius of the circle and if the point of intersection of the perpendicular bisector is within the bounds of the line-segment (you don't want an infinite line of course!), then you have a collision.

Do this for each line-segment defining the rectangle to check of a collision.

Finally (or firstly, if you care about optimisation), you'll also want to check if the centre of the circle is inside the rectangle, in which case you have a collision for sure.

However, it's the usual case of : "If you were capable of writing the code to do it, you would be capable of coming up with the solution on your in own in the first place". Which means that you're probably not capable of coding it, and you should instead use someone else's code. :-X

Arthur Kalliokoski
Second in Command
February 2005
avatar

Didn't we have a thread on this just the other day?

More like a month ago.

http://www.allegro.cc/forums/thread/603872

They all watch too much MSNBC... they get ideas.

Tobias Dammers
Member #2,604
August 2002
avatar

For axis-aligned rectangles:
A circle (defined by cx, cy, and cr) and a rectangle (defined by l, t, r and b) intersect if any of the following is true:
1. (l < cx < r) AND (t - cr < cy < b + cr)
2. (l - cr < cx < r + cr) AND (t < cy < b)
3. Any one of the rectangle's corners lies inside the circle

A quick rough outer bounding box check can be added to sort out the obvious non-collisions.

For rotated rectangles, the trick is to rotate the entire thing so that the rectangle is axis-aligned.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

TestSubject
Member #8,989
August 2007
avatar

I went to go read about the separating axis theorem and then I mowed the lawn and then I got distracted which is why I'm just now responding. I sort of understand the separating axis theorem, but it isn't actually necessary. I actually came to the same conclusion as Tobias.

Individual responses:
@Mark Oates: Boxes are not rotated, but there are triangles, so I'll need to figure those out. I can probably just apply the same principles, right?

@gnolam: Wouldn't that just check for the four sides, not bouncing off of a corner?

So...triangles. They're right isosceles triangles (with two sides parallel to the x and y axis). Just check intersection on each side and if any of the corners are inside it?

Bonus new question: since the circle is moving around a map and it can be hitting something like

       ___
  __  |   |
 /  \ |___| 
 \__/ |   |
      |___|

and it could "hit a corner" by checking from partially through one block. If I want it to bounce of like a normal wall, what would be the best way to do that?

Maybe just look at the eight blocks around the circle's position (and the one where it is) and don't treat them as separate blocks, but make a collision detection algorithm that just treats the surrounding area as a bunch of lines instead of multiple blocks?

I guess I might as well put in a SS.
{"name":"6ifb6e.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/8\/983fe099c23171d333ffeaf482074a66.png","w":616,"h":676,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/8\/983fe099c23171d333ffeaf482074a66"}6ifb6e.png

LennyLen
Member #5,313
December 2004
avatar

I need to check if a circle and an AABB will collide in the next frame, and if so at what time during the frame will the collision occur.

The method I'm using is to see if the centre of the circle will intersect with the Minkowski sum of the circle and the AABB. I'm breaking it up into four steps, one for each line segment.

Determining when the collision occurs is easy if it occurs within the edge Voronoi regions, but I'm not sure how to determine if and when it will intersect the vertex Voronoi regions.

Here's a diagram to explain what I'm talking about:

{"name":"601377","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/b\/2b5b5bfd51bef53b6489e59f755da245.png","w":553,"h":295,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/b\/2b5b5bfd51bef53b6489e59f755da245"}601377

If the red line (which represents the path at which the centre of the circle will travel) intersects the blue round-cornered box (this is the Minkowski sum of the circle and the AABB), then the circle and the AABB (the black rectangle) will collide.

The vertex Voronio regions I'm interested are there areas here (magnified and shaded):

{"name":"601378","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3b25a3050833a669ef42387aef8a129.png","w":508,"h":388,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/3\/f3b25a3050833a669ef42387aef8a129"}601378

What would be the best way to determine if and when it intersects this region, when the circle could be travelling in any direction?

I'm only just starting to get a grasp of the concepts involved here, so I nice simple explanation would be appreciated. :D

Tobias Dammers
Member #2,604
August 2002
avatar

When the distance between the vertex and the circle center is equal to the circle's radius, you have a collision; when it's smaller, you have an overlap.
You do have to weed out the solutions where the collision point lies inside the line region, but that's easy.

---
Me make music: Triofobie
---
"We need Tobias and his awesome trombone, too." - Johan Halmén

LennyLen
Member #5,313
December 2004
avatar

When the distance between the vertex and the circle center is equal to the circle's radius, you have a collision; when it's smaller, you have an overlap.

That's the part I already know. ;)

Perhaps I worded my query badly. How, algorithmically, should I go about determining if the centre of the circle will pass through this region?

Arthur Kalliokoski
Second in Command
February 2005
avatar

Ever heard of Sutherland Hodgeman clipping? Then this diagram should make sense. If the center is within the upper and lower lines of the original rectangle, then you test against the right and left sides, vice versa for within right and left. Otherwise you see if the center of the circle is within a similar sized circle at each corner.

{"name":"601379","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/011fd87c494ae1d5f90fe0bb06b80626.png","w":639,"h":485,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/011fd87c494ae1d5f90fe0bb06b80626"}601379

Circle A is hitting the top edge, circle B is hitting the left edge, and circle C is hitting the lower left corner.

They all watch too much MSNBC... they get ideas.

axilmar
Member #1,204
April 2001

You can always have superfast pixel-perfect collision detection by comparing scanline boundaries between two sprites.

LennyLen
Member #5,313
December 2004
avatar

Ever heard of Sutherland Hodgeman clipping? Then this diagram should make sense.

I hadn't, no. After reading the linked article, I'm not sure how it would help with my problem. Could you explain more?

Quote:

If the center is within the upper and lower lines of the original rectangle, then you test against the right and left sides, vice versa for within right and left. Otherwise you see if the center of the circle is within a similar sized circle at each corner.

I don't want to know if two circles overlap. That is trivial. I want to know if a circle moving along a path will overlap another circle, and at what point.

axilmar said:

You can always have superfast pixel-perfect collision detection by comparing scanline boundaries between two sprites.

I can't unfortunately, as I'm not working with Allegro. The library I'm working with (and I have no choice in this, since I'm doing this for its developers) has no concept of sprites or pixels. I only have circles and lines.

Arthur Kalliokoski
Second in Command
February 2005
avatar

LennyLen said:

I want to know if a circle moving along a path will overlap another circle, and at what point.

This can be solved with this page

http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/

as the center of the stationary circle is indeed a point, and the center of the moving circle forms a loci that is the line.

{"name":"601381","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6a95be606e1925890c2b9fa5dea07365.png","w":950,"h":548,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/a\/6a95be606e1925890c2b9fa5dea07365"}601381

The vertical line is the distance at closest approach, and the slanted line is the yet-to-be-found line where the first collision occurs (hypotenuse). This hypotenuse is necessarily the sum of the two circles radii. Now apply this:

{"name":"triangle-soh-cah-toa.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c9cabcb07d486d4d4ada401a4a1f4e.png","w":400,"h":313,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/5\/e5c9cabcb07d486d4d4ada401a4a1f4e"}triangle-soh-cah-toa.png

and this:

sin.png

Well you want the arcsine I think. (reciprocal)

They all watch too much MSNBC... they get ideas.

LennyLen
Member #5,313
December 2004
avatar

Thanks Arthur, but I'd prefer to do this with vector mathematics rather than trigonometry.

I actually decided to redo my approach. I'm now going to do four circle/line-segment intersection checks instead. This way the code can be used for OBBs as well as AABBs, and for any other polygon.

The way I intend to do this check is to produce the Minkowski sum of the line segment and the circle, and see if the circle centre will intersect the capsule that is produced. This can be done with two line/line and two line/circle intersection tests.

This brings me to my next query. The following diagram shows the capsule produced when the line AB is swept by a circle of radius r.

{"name":"601402","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/a\/cafc51c989a4d6155828a509b1b4cd32.png","w":457,"h":397,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/c\/a\/cafc51c989a4d6155828a509b1b4cd32"}601402

I need to calculate the positions of points A', A'', B' and B'', so that I can test for the intersection of lines A'B' and A''B''. Here's how I think it can be done, but if anyone knows a better way, I'd love to here it:

First, create a 2D vector (dx, dy), where dx = B.x - A.x and dy = B.y - A.y. Then produce the normal to this vector N1, which will be (-dy, dx). N1 will then need to be normalized to produce a unit vector U1 (U1 = N1 * 1/N1.length). The unit vector will then be multiplied by the scalar value r, to produce the final vector, which can be added to A and B to produce A' and B' (A' = A + rU1), B' = B + rU1).

The steps for A'' and B'' will be the same, except using N2 = (dy, -dx).

Correct to this point?

Arthur Kalliokoski
Second in Command
February 2005
avatar

If I want a perpendicular line, I just multiply the slope by -1 <shrug>

They all watch too much MSNBC... they get ideas.

LennyLen
Member #5,313
December 2004
avatar

If I want a perpendicular line, I just multiply the slope by -1 <shrug>

Essentially, that's what I am doing.

I don't know the slope of the line, so it would have to be calculated using the positions of points A and B. If you have a vector (dx, dy) representing the line, then the angle of the slope is dx/dy. If you multiply that by -1 you get -dy/dx, which when put back into vector form, gives (-dy, dx) or (dy, -dx).

edit:

Well, It all seems to be working ok. Here's what I ended up with:

#SelectExpand
1bool checkCollisionCircleLine(Vec3 circleOrigin, float r, Vec3 velocity, Line l, float *t) { 2 3 // check if the circle centre's path will intersect a capsule produced by sweeping 4 // the circle around the line segment (the Minkowski sum) 5 6 float negTime = 10.0, posTime = 10.0, beginCircleTime = 10.0, endCircleTime = 10.0; 7 8 // first construct two new lines, positive and negative 9 Vec3 slope = l.end - l.origin; 10 Vec3 N = slope.normal(); 11 N.normalize(); 12 13 Vec3 posBegin = l.origin + N * r; 14 Vec3 posEnd = l.end + N * r; 15 Vec3 negBegin = l.origin + N * -r; 16 Vec3 negEnd = l.end + N * -r; 17 Line positive = Line(posBegin, posEnd); 18 Line negative = Line(negBegin, negEnd); 19 20 // we need to make a line for the path the circle will follow 21 Vec3 circleEnd = circleOrigin + velocity; 22 Line path = Line(circleOrigin, circleEnd); 23 24 // check agianst the capsule's line segments 25 negTime = checkLineLine(path, negative); 26 posTime = checkLineLine(path, positive); 27 28 // check against the capsule's circular ends 29 beginCircleTime = checkLineCircle(path, l.origin, r); 30 endCircleTime = checkLineCircle(path, l.end, r); 31 32 // find out when it first intersected the capsule 33 *t = min(negTime, posTime); 34 *t = min(*t, beginCircleTime); 35 *t = min(*t, endCircleTime); 36 37 // we only care about collisons that happen in next time frame 38 if (*t >= 0.0 && *t <= 1.0) 39 return true; 40 else 41 return false; 42 43} 44 45 46float checkLineLine(Line lineOne, Line lineTwo) { 47 48 Vec3 circleEnd; 49 float dx, dy, da, db, m, n; 50 float time = 10.0; // just needs to be greater than 1.0 51 52 dx = lineOne.end.x - lineOne.origin.x; 53 dy = lineOne.end.y - lineOne.origin.y; 54 da = lineTwo.end.x - lineTwo.origin.x; 55 db = lineTwo.end.y - lineTwo.origin.y; 56 57 if (fabs(da * dy - db * dx) != 0.0) { 58 59 m = (dx * (lineTwo.origin.y - lineOne.origin.y) + dy * (lineOne.origin.x - lineTwo.origin.x)) / (da * dy - db * dx); 60 n = (da * (lineOne.origin.y - lineTwo.origin.y) + db * (lineTwo.origin.x - lineOne.origin.x)) / (db * dx - da * dy); 61 62 if (m >= 0.0 && m <= 1.0 && n >= 0.0 && n <= 1.0) 63 time = n; 64 } 65 66 return time; 67 68} 69 70 71float checkLineCircle(Line path, Vec3 circleCentre, float r) { 72 73 float time = 10.0; // just needs to be greater than 1.0 74 Vec3 f = path.origin - circleCentre; 75 Vec3 g = path.end - path.origin; 76 float a = g.dot(g); 77 float b = 2.0 * f.dot(g); 78 float c = f.dot(f) - r * r; 79 80 float discriminant = b * b - 4.0 * a * c; 81 if( discriminant >= 0.0 ) { 82 83 discriminant = sqrt(discriminant); 84 float t1 = (-b + discriminant) / (2.0 * a); 85 float t2 = (-b - discriminant) / (2.0 * a); 86 87 if( t1 >= 0.0 && t1 <= 1.0 ) { 88 89 if( t2 >= 0.0 && t2 <= 1.0 ) 90 time = min(t1, t2); 91 else 92 time = t1; 93 94 } 95 else if( t2 >= 0.0 && t2 <= 1.0 ) 96 time = t2; 97 98 } 99 100 return time; 101 102}

Go to: