4
\$\begingroup\$

I'm programming collision systems for a 2D game engine. The idea is that different systems can interact with each other. So one of the cases would be check collisions between axis aligned bounding box against a radius based circle collision. They both are implemented to react with its same type of collision returning me a minimum translation vector. So my approach is to combine them was to interpret the box with its bounding circle if the circle was in one of the corner outer regions of the box, and check collisions between both circles but if the circle is located in a side outer region of the box I interpret the circle with its bounding box and apply AABB collision.

Graphically

The question: Is that approach, a good one?

\$\endgroup\$
  • \$\begingroup\$ And what if the circle is inbetween corner and the side? \$\endgroup\$ – Kromster Mar 9 '15 at 15:36
  • 1
    \$\begingroup\$ So are you trying to avoid Circle and AABB collision by interpreting different shapes over your pre-existing shapes? Why not just calculate the collision between a circle and an AABB. \$\endgroup\$ – Andrew Wilson Mar 9 '15 at 16:15
  • \$\begingroup\$ I'm trying to recycle. Basically I want to know if this method is less efficient than others, and if so, which one to use \$\endgroup\$ – Rodolfo Castillo Mateluna Mar 9 '15 at 16:29
6
\$\begingroup\$

( Edit : the method above works only for square AABB, i'll have to think on how to improve it, sorry )

Fastest way is to :
- A) test circle against rect's outer bounding circle -> reject if too far.
- B) test circle against rect's inner bounding circle -> accept if near enough.
- C) test that the outer point of the circle (on the line joining both centers) is in the AABB.

enter image description here

enter image description here

enter image description here To do that quickly , precompute inner, outer radius for your AABBs.

Some pseudo-code to illustrate :

var sqDistanceBetweenCenters = sqDistance ( AABB.center, Circle.center );
if (sqDistanceBetweenCenters > sq ( AABB.outerRadius + Circle.radius ) ) return false;
if (sqDistanceBetweenCenters < sq ( AABB.innerRadius + Circle.radius ) ) return true;
var c1c2Vect =  ( Circle.center - AABB.center ) . normalize(); 
var outerPoint = Circle.center + Circle.radius * c1c2Vect ;
return AABB.pointInRect(outerPoint);

In most cases they won't intersect so you have very few operations.
In quite some of the remaining cases they will intersect with the inner radius, so again few operations.

\$\endgroup\$
  • \$\begingroup\$ I thought of an inner circle mechanism tiiiiime ago. Never went deeper. I will consider it thanks! \$\endgroup\$ – Rodolfo Castillo Mateluna Mar 13 '15 at 10:07
  • \$\begingroup\$ You're welcome. I updated with drawings. Notice that it works better if your AABB boxes are squarish \$\endgroup\$ – GameAlchemist Mar 13 '15 at 10:51
  • \$\begingroup\$ Apologies for being 1 year late to the party, but... there seems to be a problem. Suppose the box has dimensions of (20, 2) and the circle has radius of 1. The box is at (10, 1), the circle is at (1, 3), touching the box at (1, 2). The first two checks seem to pass (they don't return). The third check produces incorrect results: the point is outside the box, yet the two certainly collide. Is there anything I am missing? \$\endgroup\$ – Dmitry Yanushkevich May 4 '16 at 20:32
  • \$\begingroup\$ @DmitryYanushkevich : No you're not missing something, you just proved me wrong ! Even worse, even if the circle is at (1, 1.5) and is inside and not just touching, the result will be just as wrong. So the C) test has to be refined in case of rejection. I'll think about it, fell free to propose something, and thanks for your comment. \$\endgroup\$ – GameAlchemist May 5 '16 at 9:59
3
\$\begingroup\$

I've been thinking about this problem for a long time and looked at some of the answers here and on other forums. I came up with the following idea:

Suppose the circle has radius R. When looking at cases where the circle collides with the AABB , the center of the circle has to fall within a certain area around the AABB. The extreme cases are when the center is contained in the rectangle, then collision obviously occurs. Or if the distance between the center and the outer circle on the rectangle is greater than R, then collision obviously didn't occur. But what about the intermediate cases?

The idea is to find extreme points for the center of the circle to lie on. These are points where the circle is positioned in such a way that it's just touching the rectangle at one point. If we trace out all such extreme points, we get something like the following picture:

An instance of collision at only one point

As we can see the set of extreme points trace out a rounded rectangle around the AABB, this rounded rectangle is precisely the set of points that are distance R from the AABB. In fact, collision occurs if and only if the center of the circle is inside that rounded rectangle. So now we've reduced the problem to checking if a point (x, y) is inside of a rounded rectangle.

To that end we can divide the rounded rectangle into 6 parts (4 circles with centers on the vertices of the AABB, and 2 rectangles):

Division of the rounded rectangle

The 4 green circles are identical in size (all with radius R) and so are the two rectangles. Moreover the intersection of the red rectangle and the blue rectangle is precisely the AABB. So if the center of the circle is inside any of these 6 shapes, then collision occurs. If the center of the circle is in none of these 6 shapes, then collision doesn't occur.

Note that this method does not require the center of the AABB (although you would already have that information anyway) and only depends on the center and the radius of the circle.

\$\endgroup\$
  • \$\begingroup\$ This is actually exactly as I've implemented my own right now ;P I was just looking for a better solution. :D \$\endgroup\$ – Noel Widmer Jun 29 '16 at 21:59
1
\$\begingroup\$

Assuming case 1 means the center of the circle is in a lateral region, and case 2 means the center of the circle in a corner region, this approach has a problem.

Specifically, when the circle is just barely into a corner region, the square is treated as suddenly larger. If the circle was grazing the square, it will suddenly be intersecting. The behavior over time goes nonlinear...

What you actually want for case 2 is to treat the AABB's vertices each as a circle of radius zero. (You'd only have to check the vertex for current corner region.)

(Additionally, the method as you describe it becomes asymmetric on rectangular AABB's; the long sides will bulge more than the short sides, when approximated with a circle.)

\$\endgroup\$
  • \$\begingroup\$ Yes I spotted the first problem you mentioned and I'm searching for a fix. But I don't understand why it wouldn't work with non square ones \$\endgroup\$ – Rodolfo Castillo Mateluna Mar 9 '15 at 21:35
  • \$\begingroup\$ I was thinking that a non-square AABB doesn't as easily fit into a circle. I guess it does, but the circle would stick out even more on the the long sides of a rectangle, making the "grazing to the corner" sudden jab even more pronounced. \$\endgroup\$ – david van brink Mar 9 '15 at 22:06
  • 1
    \$\begingroup\$ It can fit perfectly using diag/2 as radius. But you are right it is too much inflated at the sides that's why case 2 could fail if the circle is approximating by the corner near an edge projection \$\endgroup\$ – Rodolfo Castillo Mateluna Mar 9 '15 at 22:34
0
\$\begingroup\$

Im not sure if I am missing some cases but if you use combine the AABB AABB test and then check if the distance between any of the 4 AABB vertices to the circle's center is less than circle's radius, doesnt that cover all cases? NVM, you need to check axis that is from the circle's center to the closest vertex of the AABB is less than circle's radius.

This should work:

//copy the circle center to a new point (this changes so there needs to be a copy)

Point pt = circle.center;


    //point on rectangle closest to circle 
    //(snaps the point to the rectangle, pretty much, 
    //if the circle center is inside the rectangle there isn't snapping, 
    //but this is fine since it will detect a collision as a result)

if(pt.x > rectangle.right) pt.x = rectangle.right;
if(pt.x < rectangle.left) pt.x = rectangle.left;
if(pt.y > rectangle.bottom) pt.y = rectangle.bottom;
if(pt.y < rectangle.top) pt.y = rectangle.top;


    //distance check, just use distance^2 for actual implementation

return distance(pt, circle.center) < circle.radius; 
\$\endgroup\$
  • \$\begingroup\$ In fact it does not cover all of the cases imagine a little circle approaching from a side center. The distance from a vertex and the circle will never be smaller than the radius \$\endgroup\$ – Rodolfo Castillo Mateluna Mar 10 '15 at 13:06
  • 1
    \$\begingroup\$ The code above doesnt use vertex of rect anymore, it checks if the nearest point on the perimeter of the rect to the center of circle is less than the radius. \$\endgroup\$ – user62462 Mar 10 '15 at 18:09
  • \$\begingroup\$ This works. It's perfectly acceptable to treat the axes independently to find the closest point on the rectangle to the circle's center. Check distance from that point to the circle to determine the distance to the closest point, compare against radius to determine if a collision takes place. Distance to that point will give you a "collision depth" that can be used to calculate the response. Downvotes are incorrect. \$\endgroup\$ – 3Dave Jul 27 '18 at 20:11
  • \$\begingroup\$ @RodolfoCastilloMateluna It's not checking against the corner vertices. It checks against the closest point on the rectangle to the circle's center. This is considered to be the most efficient circle vs AABB collision algorithm. This also works when the circle is inside the rectangle, if the inside is "hollow." Modifying it for a solid is trivial. \$\endgroup\$ – 3Dave Jul 27 '18 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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