|
Circle/Rectangle Collision Detection |
TestSubject
Member #8,989
August 2007
|
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
|
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
|
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
|
Axis-aligned or object-oriented? Arthur Kalliokoski said: 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. -- |
Mark Oates
Member #1,146
March 2001
|
gnolam said: Axis-aligned or object-oriented? just "oriented", as in "axis-aligned or oriented?" -- |
Arthur Kalliokoski
Second in Command
February 2005
|
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.
|
Arthur Kalliokoski
Second in Command
February 2005
|
James Lohr said: Didn't we have a thread on this just the other day? More like a month ago. They all watch too much MSNBC... they get ideas. |
Tobias Dammers
Member #2,604
August 2002
|
For axis-aligned rectangles: 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. --- |
TestSubject
Member #8,989
August 2007
|
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: @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.
|
LennyLen
Member #5,313
December 2004
|
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"} 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"} 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.
|
Tobias Dammers
Member #2,604
August 2002
|
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. --- |
LennyLen
Member #5,313
December 2004
|
Tobias Dammers said: 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
|
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"} 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
|
Arthur Kalliokoski said: 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
|
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"} 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"} and this: Well you want the arcsine I think. (reciprocal) They all watch too much MSNBC... they get ideas. |
LennyLen
Member #5,313
December 2004
|
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"} 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
|
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
|
Arthur Kalliokoski said: 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: 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}
|
|