SAT Polygon Circle Collision - resolve the intersection in the direction of velocity & determine side of collision

Question

Summary

This question is in JavaScript, but an answer in any language, pseudo-code, or just the maths would be great!

I have been trying to implement the Separating-Axis-Theorem to accomplish the following:

• Detecting an intersection between a convex polygon and a circle.
• Finding out a translation that can be applied to the circle to resolve the intersection, so that the circle is barely touching the polygon but no longer inside.
• Determining the axis of the collision (details at the end of the question).

I have successfully completed the first bullet point and you can see my javascript code at the end of the question. I am having difficulties with the other parts.

Resolving the intersection

There are plenty of examples online on how to resolve the intersection in the direction with the smallest/shortest overlap of the circle. You can see in my code at the end that I already have this calculated.

However this does not suit my needs. I must resolve the collision in the opposite direction of the circle's trajectory (assume I already have the circle's trajectory and would like to pass it into my function as a unit-vector or angle, whichever suits).

You can see the difference between the shortest resolution and the intended resolution in the below image:

How can I calculate the minimum translation vector for resolving the intersection inside my test_CIRCLE_POLY function, but that is to be applied in a specific direction, the opposite of the circle's trajectory?

My ideas/attempts:

• My first idea was to add an additional axis to the axes that must be tested in the SAT algorithm, and this axis would be perpendicular to the circle's trajectory. I would then resolve based on the overlap when projecting onto this axis. This would sort of work, but would resolve way to far in most situations. It won't result in the minimum translation. So this won't be satisfactory.
• My second idea was to continue to use magnitude of the shortest overlap, but change the direction to be the opposite of the circle's trajectory. This looks promising, but there are probably many edge-cases that I haven't accounted for. Maybe this is a nice place to start.

Determining side/axis of collision

I've figured out a way to determine which sides of the polygon the circle is colliding with. For each tested axis of the polygon, I would simply check for overlap. If there is overlap, that side is colliding.

This solution will not be acceptable once again, as I would like to figure out only one side depending on the circle's trajectory.

My intended solution would tell me, in the example image below, that axis A is the axis of collision, and not axis B. This is because once the intersection is resolved, axis A is the axis corresponding to the side of the polygon that is just barely touching the circle.

My ideas/attempts:

• Currently I assume the axis of collision is that perpendicular to the MTV (minimum translation vector). This is currently incorrect, but should be the correct axis once I've updated the intersection resolution process in the first half of the question. So that part should be tackled first.

• Alternatively I've considered creating a line from the circle's previous position and their current position + radius, and checking which sides intersect with this line. However, there's still ambiguity, because on occasion there will be more than one side intersecting with the line.

My code so far

function test_CIRCLE_POLY(circle, poly, circleTrajectory) {
    // circleTrajectory is currently not being used

    let axesToTest = [];
    let shortestOverlap = +Infinity;
    let shortestOverlapAxis;

    // Figure out polygon axes that must be checked

    for (let i = 0; i < poly.vertices.length; i++) {
        let vertex1 = poly.vertices[i];
        let vertex2 = poly.vertices[i + 1] || poly.vertices[0]; // neighbouring vertex
        let axis = vertex1.sub(vertex2).perp_norm();
        axesToTest.push(axis);
    }

    // Figure out circle axis that must be checked

    let closestVertex;
    let closestVertexDistSqr = +Infinity;

    for (let vertex of poly.vertices) {
        let distSqr = circle.center.sub(vertex).magSqr();

        if (distSqr < closestVertexDistSqr) {
            closestVertexDistSqr = distSqr;
            closestVertex = vertex;
        }
    }

    let axis = closestVertex.sub(circle.center).norm();
    axesToTest.push(axis);

    // Test for overlap

    for (let axis of axesToTest) {
        let circleProj = proj_CIRCLE(circle, axis);
        let polyProj = proj_POLY(poly, axis);
        let overlap = getLineOverlap(circleProj.min, circleProj.max, polyProj.min, polyProj.max);

        if (overlap === 0) {
            // guaranteed no intersection
            return { intersecting: false };
        }

        if (Math.abs(overlap) < Math.abs(shortestOverlap)) {
            shortestOverlap = overlap;
            shortestOverlapAxis = axis;
        }
    }

    return {
        intersecting: true,
        resolutionVector: shortestOverlapAxis.mul(-shortestOverlap),
        // this resolution vector is not satisfactory, I need the shortest resolution with a given direction, which would be an angle passed into this function from the trajectory of the circle
        collisionAxis: shortestOverlapAxis.perp(),
        // this axis is incorrect, I need the axis to be based on the trajectory of the circle which I would pass into this function as an angle
    };
}

function proj_POLY(poly, axis) {
    let min = +Infinity;
    let max = -Infinity;

    for (let vertex of poly.vertices) {
        let proj = vertex.projNorm_mag(axis);
        min = Math.min(proj, min);
        max = Math.max(proj, max);
    }

    return { min, max };
}

function proj_CIRCLE(circle, axis) {
    let proj = circle.center.projNorm_mag(axis);
    let min = proj - circle.radius;
    let max = proj + circle.radius;

    return { min, max };
}

// Check for overlap of two 1 dimensional lines
function getLineOverlap(min1, max1, min2, max2) {
    let min = Math.max(min1, min2);
    let max = Math.min(max1, max2);

    // if negative, no overlap
    let result = Math.max(max - min, 0);

    // add positive/negative sign depending on direction of overlap
    return result * ((min1 < min2) ? 1 : -1);
};

Answer 1

I am assuming the polygon is convex and that the circle is moving along a straight line (at least for a some possibly small interval of time) and is not following some curved trajectory. If it is following a curved trajectory, then things get harder. In the case of curved trajectories, the basic ideas could be kept, but the actual point of collision (the point of collision resolution for the circle) might be harder to calculate. Still, I am outlining an idea, which could be extended to that case too. Plus, it could be adopted as a main approach for collision detection between a circle and a convex polygon.

I have not considered all possible cases, which may include special or extreme situations, but at least it gives you a direction to explore.

Transform in your mind the collision between the circle and the polygon into a collision between the center of the circle (a point) and a version of the polygon thickened by the circle's radius r, i.e. (i) each edge of the polygon is offset (translated) outwards by radius r along a vector perpendicular to it and pointing outside of the polygon, (ii) the vertices become circular arcs of radius r, centered at the polygons vertices and connecting the endpoints of the appropriate neighboring offset edges (basically, put circles of radius r at the vertices of the polygon and take their convex hull).

Now, the current position of the circle's center is C = [ C[0], C[1] ] and it has been moving along a straight line with direction vector V = [ V[0], V[1] ] pointing along the direction of motion (or if you prefer, think of V as the velocity of the circle at the moment when you have detected the collision). Then, there is an axis (or let's say a ray - a directed half-line) defined by the vector equation X = C - t * V, where t >= 0 (this axis is pointing to the past trajectory). Basically, this is the half-line that passes through the center point C and is aligned with/parallel to the vector V. Now, the point of resolution, i.e. the point where you want to move your circle to is the point where the axis X = C - t * V intersects the boundary of the thickened polygon.

So you have to check (1) first axis intersection for edges and then (2) axis intersection with circular arcs pertaining to the vertices of the original polygon.

Assume the polygon is given by an array of vertices P = [ P[0], P[1], ..., P[N], P[0] ] oriented counterclockwise.

(1) For each edge P[i-1]P[i] of the original polygon, relevant to your collision (these could be the two neighboring edges meeting at the vertex based on which the collision is detected, or it could be actually all edges in the case of the circle moving with very high speed and you have detected the collision very late, so that the actual collision did not even happen there, I leave this up to you, because you know better the details of your situation) do the following. You have as input data:

C = [ C[0], C[1] ]
V = [ V[0], V[1] ]
P[i-1] = [ P[i-1][0],  P[i-1][1] ]
P[i] = [ P[i][0],  P[i][1] ]

Do:

Normal = [ P[i-1][1] - P[i][1], P[i][0] - P[i-1][0] ];
Normal = Normal / sqrt((P[i-1][1] - P[i][1])^2 + ( P[i][0] - P[i-1][0] )^2); 
// you may have calculated these already

Q_0[0] = P[i-1][0] + r*Normal[0];
Q_0[1] = P[i-1][1] + r*Normal[1];

Q_1[0] = P[i][0]+ r*Normal[0]; 
Q_1[1] = P[i][1]+ r*Normal[1]; 

Solve for s, t the linear system of equations (the equation for intersecting ):

Q_0[0] + s*(Q_1[0] - Q_0[0]) = C[0] - t*V[0];
Q_0[1] + s*(Q_1[1] - Q_0[1]) = C[1] - t*V[1];

if 0<= s <= 1 and t >= 0, you are done, and your point of resolution is

R[0] = C[0] - t*V[0];
R[1] = C[1] - t*V[1];

else

(2) For the each vertex P[i] relevant to your collision, do the following: solve for t the quadratic equation (there is an explicit formula)

norm(P[i] - C + t*V )^2 = r^2

or expanded:

(V[0]^2 + V[1]^2) * t^2 + 2 * ( (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1] )*t + ( P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 )  - r^2 = 0

or if you prefer in a more code-like way:

a = V[0]^2 + V[1]^2;
b = (P[i][0] - C[0])*V[0] + (P[i][1] - C[1])*V[1];
c = (P[i][0] - C[0])^2 + (P[i][1] - C[1])^2 - r^2;
D = b^2 - a*c;

if D < 0 there is no collision with the vertex 
i.e. no intersection between the line X = C - t*V 
and the circle of radius r centered at P[i]

else
D = sqrt(D);
t1 = ( - b - D) / a;
t2 = ( - b + D) / a;  
where t2 >= t1 

Then your point of resolution is

R[0] = C[0] - t2*V[0];
R[1] = C[1] - t2*V[1];

Answer 2

It's probably not what you're looking for, but here's a way to do it (if you're not looking for perfect precision) :
You can try to approximate the position instead of calculating it.

The way you set up your code has a big advantage : You have the last position of the circle before the collision. Thanks to that, you can just "iterate" through the trajectory and try to find a position that is closest to the intersection position. I'll assume you already have a function that tells you if a circle is intersecting with the polygon. Code (C++) :

// What we need :

Vector startPos; // Last position of the circle before the collision
Vector currentPos; // Current, unwanted position
Vector dir; // Direction (a unit vector) of the circle's velocity
float distance = compute_distance(startPos, currentPos); // The distance from startPos to currentPos.
Polygon polygon; // The polygon
Circle circle; // The circle.
unsigned int iterations_count = 10; // The number of iterations that will be done. The higher this number, the more precise the resolution.

// The algorithm :

float currentDistance = distance / 2.f; // We start at the half of the distance.
Circle temp_copy; // A copy of the real circle to "play" with.
for (int i = 0; i < iterations_count; ++i) {
    temp_copy.pos = startPos + currentDistance * dir;
    if (checkForCollision(temp_copy, polygon)) {
        currentDistance -= currentDistance / 2.f; // We go towards startPos by the half of the current distance.
    }
    else {
        currentDistance += currentDistance / 2.f; // We go towards currentPos by the half of the current distance.
    }
}
    
// currentDistance now contains the distance between startPos and the intersection point
// And this is where you should place your circle :
Vector intersectionPoint = startPos + currentDistance * dir;

I haven't tested this code so I hope there's no big mistake in there. It's also not optimized and there are a few problems with this approach (the intersection point could end up inside the polygon) so it still needs to be improved but I think you get the idea. The other (big, depending on what you're doing) problem with this is that it's an approximation and not a perfect answer.
Hope this helps !