Separating Axis Theorem Refinements and Expansion

Article 1 of 1
separating axis theorum refinements and expansion (you are here)

intent

In this video, javidx9 explores two techniques for collision detection and static resolution for convex polygons. While his collision detection using the Separating Axis Theorem is just as robust as his diagonals approach, his static resolution for SAT is slightly naïve. His implementation assumes the smallest possible displacement to resolve the collision is along the vector between the centers of the colliding polygon and the collided polygon, with a magnitude of the smallest displacement. This assumption is not always correct, and can lead to incorrect resolution with large overlaps. The correct resolution vector is along the normal of the axis with the smallest overlap.

This article will explore my implementation of Separating Axis Theorem detection and resolution.
This article assumes basic knowledge of two-dimensional vector math.

separating / separated axis theorem

The video above explains the Separating Axis Theorem quite well, I suggest you watch it if my explanation seems a bit muddled.

The Separating Axis Theorem states that two convex polygons overlap only if the projection of one polygon onto the every axis of another polygon overlaps with the projection of the latter onto the same axis.

implementation

My implementation relies on several objects:

vector2 {
    float x, y
    float length => square_root(x * x + y * y)
    float dot(vector2 other) => x * other.x + y * other.y;
    vector2 normalized => this / length
    vector2 normal => (y, -x).normalized
}

 polygon {
    vector2 location;
    point[] points;
    side[] sides;

    projection project(vector2 axis){
        float min = axis.dot(points[0]);
        float max = min;

        for(int i = 1; i < points.length; i++){
            float dot = axis.dot(points[i])
            if     (dot < min) min = dot;
            else if(dot > max) max = dot; 
        }

        return new projection(min, max);
    }
} 

side {
    vector2 start, end;
    vector2 normal => (end - start).normal;  
}

 projection {
    float min, max;
    bool overlap(projection other) => 
        max > other.min &&
        min < other.max;
    float overlap(projection other) =>
        minimum(max, other.max) - 
        maximum(min, other.min);
}

With these, writing Separating Axis Theorem collision detection is quite simple:

bool SAT(polygon a, polygon b){
    // smallest overlap
    float overlap = float.MaxValue;
    // axis along which the smallest overlap occurred
    vector2 oaxis = new vector2()

    // pointers to each polygon so they can be swapped
    polygon sa = a;
    polygon sb = b;

    // the same operations must be done on each shape
    for(int shape = 0; shape < 2; shape++){
        if(shape == 1)
            swap(sa, sb);

        vector2[] axes = new vector2[sa.sides.length);
        for(int i = 0; i < axes.length; i++)
            axes[i] = sa.sides[i].normal;

        for(int i = 0; i < axes.length; i++){
            vector2 axis = axes[i];
            projection pa = sa.project(axis);
            projection pb = sb.project(axis);

            if(!pa.overlap(pb))
                // no collision, no resolution
                return false; 
            else{
                float o = pa.overlap(pb);
                if(o < overlap){
                    overlap = o;
                    oaxis = axis;
                }
            }
        }
    }
    
    // if the smallest penetration normal
    //     points into shape b,
    //     flip it
    if((b.location - a.location).dot(oaxis) < 0)
        oaxis *= -1;


    // now oaxis is the axis along which
    //     the smallest penetration occurred
    // the resolution vector is that axis normal
    //     multiplied by the smallest 
    //     penetration amount
    vector2 resolution = oaxis * overlap;
    // translate the colliding shape to resolve the collision
    a.location -= resolution;

    // no collision because of static resolution
    return false;
}

references

javidx9, Convex Polygon Collisions #1 (video) published 2019-02-02 retrieved 2020-09-26
Wikipedia, Hyperplane Separation Theorem (article) retrieved 2020-09-26
Wikipedia, Euclidean Vector (article) retrieved 2020-09-26

Contact

discord: Fyre#0465
email: horace5413@gmail.com with “olc” in the subject line