Collision between AABB and Circle

Question

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.

The question: Is that approach, a good one?

Answer 1

( 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.

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.

Answer 2

To detect collisions between a circle and an AABB, you should find the closest point from the AABB to the circle. You can run the below code snippet and try to move the purple point which represents the AABB center to watch the position of the closest point.

<iframe src="https://www.desmos.com/calculator/u32th8uhli?embed" width="500px" height="500px" style="border: 1px solid #ccc" frameborder=0></iframe>

The math behind it is to clamp the distance from AABB to circle on each axis separately. The value will be clamped on each axis if the distance is greater than the extent(half-width or height) or less than the negative extent. Like the below figure shows: (Forgive my clumsy finger).
The pseudo-code is:

func CheckCollision(){
    vector3 distance = AABB.Center - Circle.Center;
    //Clamp(value,min,max)
    vector3 clampDst = Clamp(distance, -AABB.Bounds, AABB.Bounds);
    vector3 closestPoint = AABB.Center + clampDst;
    return (closestPoint - Circle.Center).SqrMagnitude > Circle.Radius;
}

Answer 3

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:

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):

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.

Answer 4

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.)

Answer 5

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; 

Answer 6

There's almost certainly a cleaner way to write this, but I wasn't able to find a fully-formed solution that returns a proper collision manifold for contact resolution anywhere on the web. Just a bunch of half-baked stuff. So I wrote and tested this. I think it works correctly for all cases, but I was especially concerned with the case where the circle is fully inside of the AABB for my use-case.

Red = circle that is colliding
Green = new position of circle after contact resolution
Blue Dot = point-of-contact
Orange Line = contact resolution vector (normal * depth)

struct Rectangle { float x, y, width, height; };

bool dlb_CheckCollisionCircleRec(Vector2 center, float radius, Rectangle rec, Vector2 &contact, Vector2 &normal, float &depth)
{
    float xOverlap = 0;
    float yOverlap = 0;

    Vector2 pt = center;  // circle center point constrained to box
    if (pt.x < rec.x) {
        pt.x = rec.x;
    } else if (pt.x >= rec.x + rec.width) {
        pt.x = rec.x + rec.width;
    } else {
        float recCenterX = rec.x + rec.width / 2;
        xOverlap = pt.x < recCenterX ? rec.x - pt.x : (rec.x + rec.width) - pt.x;
    }

    if (pt.y < rec.y) {
        pt.y = rec.y;
    } else if (pt.y >= rec.y + rec.height) {
        pt.y = rec.y + rec.height;
    } else {
        float recCenterY = rec.y + rec.height / 2;
        yOverlap = pt.y < recCenterY ? rec.y - pt.y : (rec.y + rec.height) - pt.y;
    }

    if (Vector2DistanceSqr(pt, center) < radius*radius) {
        contact = pt;  // closest point to "pt" on the surface of the box
        if (fabsf(xOverlap) < fabsf(yOverlap)) {
            contact.x += xOverlap;
        } else if (fabsf(yOverlap) < fabsf(xOverlap)) {
            contact.y += yOverlap;
        }

        Vector2 pen = Vector2Subtract(center, contact);
        depth = radius - Vector2Length(pen);
        normal = Vector2Normalize(pen);

        if (xOverlap && yOverlap) {
            depth -= radius*2;
        }
        return true;
    }
    return false;
}

This is how I use it in the code. Note that the dot product check is optional, and is there to allow circles with outward velocities to escape the rectangle as opposed to getting stuck inside of it.

struct Vector2 { float x, y; };

float Vector2DotProduct(Vector2 v1, Vector2 v2) {
    return v1.x*v2.x + v1.y*v2.y;
}

Vector2 contact{};
Vector2 normal{};
float depth{};
if (dlb_CheckCollisionCircleRec(entity.position, entity.radius, tileRect, contact, normal, depth)) {
    entity.colliding = true;
    if (Vector2DotProduct(entity.velocity, normal) < 0) {
        entity.position.x += normal.x * depth;
        entity.position.y += normal.y * depth;
    }
}