Separating axis theorem algorithm not working

276 views Asked by At

Writing a separating axis implementation based off the following guide, using Haxe. Can't seem to figure out why it's not working, tested individual parts but it always returns true for collisions even when there isn't one no matter what.

Any help appreciated! :D

public static function polygon_polygon(poly1Pos:Vec2, poly1Verts:Array<Vec2>, poly2Pos:Vec2, poly2Verts:Array<Vec2>):Bool
{
    var axes1:Array<Vec2> = MathTools.getAxes(poly1Verts);
    var axes2:Array<Vec2> = MathTools.getAxes(poly2Verts);

    for (i in 0...axes1.length)
    {
        var p1:Projection = MathTools.project(axes1[i], poly1Verts);
        var p2:Projection = MathTools.project(axes1[i], poly2Verts);

        if (!p1.overlap(p2))
        {
            return false;
        }
    }
    for (i in 0...axes2.length)
    {
        var p1:Projection = MathTools.project(axes2[i], poly1Verts);
        var p2:Projection = MathTools.project(axes2[i], poly2Verts);

        if (!p1.overlap(p2))
        {
            return false;
        }
    }
    return true;
}

/**
 * Gets a list of normalized axis from a list of vertices
 */
public static function getAxes(verts:Array<Vec2>):Array<Vec2>
{
    var axes:Array<Vec2> = new Array<Vec2>();
    for (i in 0...verts.length)
    {
        var p1:Vec2 = verts[i];
        var p2:Vec2 = verts[i + 1 == verts.length ? 0 : i + 1];
        var normal:Vec2 = p1.getSubtract(p2).getPerpendicular().getNormal();
        axes[i] = normal;
    }
    return axes;
}

/**
 * Projects a set of vertices onto an axis
 */
public static function project(axis:Vec2, verts:Array<Vec2>):Projection
{
    var min:Float = axis.dot(verts[0]);
    var max:Float = min;
    for (i in 1...verts.length)
    {
        var p:Float = axis.dot(verts[i]);
        if (p < min) min = p;
        else if (p > max) max = p;
    }
    return new Projection(min, max);
}

class Projection
{

    public var min:Float;
    public var max:Float;

    public function new(min:Float, max:Float) 
    {
        this.min = min;
        this.max = max;
    }

    public function overlap(p:Projection):Bool
    {
        if (max < p.min || p.max < min) return false;
        else return true;

    }

}
1

There are 1 answers

5
J.J On BEST ANSWER

Are you sure vertices are being transformed? then check the perpendicular is right or left, it must be chosen based on how the vertices are ordered, CW or CCW.