What's wrong with my SAT collision response system?

Question

I'm creating a MonoGame 2D engine framework for a platforming game, and I'm having trouble creating the collision response system. Although I've gotten SAT detection to work, the response travels across the actual direction of the static body's edge rather than its normal. Reversing the axes of the normal has not worked for me and does nothing, it has only created glitches involving the body going off screen.

Since I'm trying to make a platformer, I only want the normals of the static body to be considered as directions to respond. For example, if the static body is a box, I only want the moving body to travel on 90 degree normals.

Here is a video of the problem in action: https://www.youtube.com/watch?v=-wyXfZkxis0

And the source for the "Collision" module, which has all of the relevant geometric calculations inside (translation vector algorithm at the bottom):

using System;
using Microsoft.Xna.Framework;

namespace Crossfrog.Ferrum.Engine.Modules
{
public static class Collision
{
    public static bool RectsCollide(Rectangle rect1, Rectangle rect2)
    {
        return
            rect1.X <= rect2.X + rect2.Width &&
            rect1.Y <= rect2.Y + rect2.Height &&
            rect1.X + rect1.Width >= rect2.X &&
            rect1.Y + rect1.Height >= rect2.Y;
    }
    private static float DotProduct(Vector2 v1, Vector2 v2)
    {
        return (v1.X * v2.X) + (v1.Y * v2.Y);
    }
    private static Vector2 NormalBetween(Vector2 v1, Vector2 v2)
    {
        return new Vector2(-(v1.Y - v2.Y), v1.X - v2.X);
    }
    private struct ProjectionLine
    {
        public float Start;
        public float End;
    }
    private static ProjectionLine ProjectLine(Vector2[] points, Vector2 normal)
    {
        var projectionLine = new ProjectionLine() { Start = float.MaxValue, End = float.MinValue };
        foreach (var p in points)
        {
            var projectionScale = DotProduct(p, normal);
            projectionLine.Start = Math.Min(projectionScale, projectionLine.Start);
            projectionLine.End = Math.Max(projectionScale, projectionLine.End);
        }
        return projectionLine;
    }
    private static bool CheckOverlapSAT(Vector2[] shape1, Vector2[] shape2)
    {
        for (int i = 0; i < shape1.Length; i++)
        {
            var vertex = shape1[i];
            var nextVertex = shape1[(i + 1) % shape1.Length];

            var edgeNormal = NormalBetween(vertex, nextVertex);
            var firstProjection = ProjectLine(shape1, edgeNormal);
            var secondProjection = ProjectLine(shape2, edgeNormal);

            if (!(firstProjection.Start <= secondProjection.End && firstProjection.End >= secondProjection.Start))
                return false;
        }
        return true;
    }
    public static bool ConvexPolysCollide(Vector2[] shape1, Vector2[] shape2)
    {
        return CheckOverlapSAT(shape1, shape2) && CheckOverlapSAT(shape2, shape1);
    }

    private static float? CollisionResponseAcrossLine(ProjectionLine line1, ProjectionLine line2)
    {
        if (line1.Start <= line2.Start && line1.End > line2.Start)
            return line2.Start - line1.End;
        else if (line2.Start <= line1.Start && line2.End > line1.Start)
            return line2.End - line1.Start;
        return null;
    }

    public static Vector2 MTVBetween(Vector2[] mover, Vector2[] collider)
    {
        if (!ConvexPolysCollide(mover, collider))
            return Vector2.Zero;

        float minResponseMagnitude = float.MaxValue;
        var responseNormal = Vector2.Zero;

        for (int c = 0; c < collider.Length; c++)
        {
            var cPoint = collider[c];
            var cNextPoint = collider[(c + 1) % collider.Length];

            var cEdgeNormal = NormalBetween(cPoint, cNextPoint);

            var cProjected = ProjectLine(collider, cEdgeNormal);
            var mProjected = ProjectLine(mover, cEdgeNormal);

            var responseMagnitude = CollisionResponseAcrossLine(cProjected, mProjected);
            if (responseMagnitude != null && responseMagnitude < minResponseMagnitude)
            {
                minResponseMagnitude = (float)responseMagnitude;
                responseNormal = cEdgeNormal;
            }
        }

        var normalLength = responseNormal.Length();
        responseNormal /= normalLength;
        minResponseMagnitude /= normalLength;

        var mtv = responseNormal * minResponseMagnitude;
        return mtv;
    }
}
}

user_6866837 · Answer

Your code is nearly right, just follow these steps and it should work.

Normalize your normal in NormalBetween(). Without this, your projected values are distorted and shouldn't be compared to get the right axis.

return Vector2.Normalize(new Vector2(-(v1.Y - v2.Y), v1.X - v2.X));

Use the same collision expression in CollisionResponseAcrossLine() as in CheckOverlapSAT(). Or just use one detection method for both.

if (line1.Start <= line2.Start && line1.End >= line2.Start) // use the >= operator
    return line2.Start - line1.End;
else if (line2.Start <= line1.Start && line2.End >= line1.Start) // use the >= operator
    return line2.End - line1.Start;
return null;

Compare the absolute magnitudes inside MTVBetween(). The calculated magnitudes can be negative, when they are pointing to the other direction of the normal.

if (responseMagnitude != null && Math.Abs(responseMagnitude.Value) < Math.Abs(minResponseMagnitude))

The following code is no longer needed, because we already normalized the vector in 1.

//var normalLength = responseNormal.Length();
//responseNormal /= normalLength;
//minResponseMagnitude /= normalLength;

This should get your example to work. But when you try it with two polygons, that have different seperation axes, it won't work, because in the collision response code, you only check for the axes of the static collider. The axes from the mover should also be checked, like you did in the collision detection method CheckOverlapSAT().

Calling the CheckOverlapSAT() method inside MTVBetween() seems to be redundant, you could also interrupt the MTVBetween() method, when any responseMagnitude is null.

And last but not least, consider replacing your CollisionResponseAcrossLine() code with the following:

private static float? CollisionResponseAcrossLine(ProjectionLine line1, ProjectionLine line2)
{
    float distToStartOfLine2 = line2.Start - line1.End;
    if (distToStartOfLine2 > 0)
        return null;

    float distToEndOfLine2 = line2.End - line1.Start;
    if (distToEndOfLine2 < 0)
        return null;

    if (-distToStartOfLine2 < distToEndOfLine2) // negate distToStartOfLine2, cause it's always negative
        return distToStartOfLine2;
    else
        return distToEndOfLine2;
}

This also accounts for the scenario of the player being inside an obstacle. It compares the distances to both sides and chooses the smaller one. Previously the player would always go to the same edge in this scenario.

If you want code that only supports AABBs, then you could go a simpler route without relying on the SAT. But I guess you want to support polygons too.

What's wrong with my SAT collision response system?

1 Answers