Separating axis theorem algorithm not working

Question

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;

    }

}

J.J · Accepted Answer · 2014-12-17 11:30:46Z

0

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.

answered Dec 17, 2014 at 11:30

J.J

466 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Daniel Messias Over a year ago

I've checked axes values, the min and max values after projection and some clear cut cases of projections that do and don't overlap. It all appears to be working fine separately. I'm using just two squares to test for collision at the moment so the numbers are easier to work with when I debug. I tried swapping the perpendicular just to see if it made any difference, but no. It may be I need to implement left and right code based on the vertices later, but that doesn't appear to be the main problem.

Daniel Messias Over a year ago

SOLVED Ok I was an idiot, the vertices I was passing to my polygon_polygon function were relative to the origin of the shape, rather than the actual co-ordinates in the world. I just added the position of the center of the shape to all the vertices to fix it. Thanks for all the help though!

J.J Over a year ago

:) okay. i have faced something like this before, like you:D

J.J Over a year ago

i think this implementation is not enough efficient , if you move the line :var axes2:Array<Vec2> = MathTools.getAxes(poly2Verts); after the first loop. it would be faster.

Daniel Messias Over a year ago

Good point, won't need to unnecessarily generate the second set of axis if there is a return earlier then. Cheers

Collectives™ on Stack Overflow

Separating axis theorem algorithm not working

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related