SAT Collision: Spaces between polygons in collision

by fsdss   Last Updated January 14, 2018 03:13 AM

I tried to implement SAT collision for my program, however, when ever there is a angled line in either polygons (all convex), collision detection does not work properly. I even tried two different ways of coding the algorithm, but I ended up with the same results. Both implementations follow a tutorial, but it doesn't seem to work for me.

Here is an image to show what I mean:

enter image description here

public class SAT2 {
    public static boolean collide(Shape p1, Shape p2) {

        Vector2d[] p1Vertices = p1.getVertices();
        Vector2d[] p2Vertices = p2.getVertices();

        Vector2d[] p1Edges = getEdges(p1Vertices);
        Vector2d[] p2Edges = getEdges(p2Vertices);

        for (int i = 0; i < p1Edges.length; i++) {

            //get normal
            Vector2d axis = p1Edges[i].perp(true);

            double[] a = project(p1, axis);
            double[] b = project(p2, axis);
            if (!overlap(a, b)) {
                return false;
            }
        }

        for (int i = 0; i < p2Edges.length; i++) {
            Vector2d axis = p2Edges[i].perp(false);
            double[] a = project(p1, axis);
            double[] b = project(p2, axis);
            if (!overlap(a, b)) {
                return false;
            }
        }

     return true;   
    }

    private static boolean contains(double n, double[] range) {
        double a = range[0];
        double b = range[1];
        if (b < a) {
            a = b;
            b = range[0];
        }
        return (n >= a && n < b);
    }

    private static boolean overlap(double[] a, double[] b) {
        if (contains(a[0], b)) return true;
        if (contains(a[1], b)) return true;
        if (contains(b[0], a)) return true;
        if (contains(b[1], a)) return true;
        return false;
    }

    private static Vector2d[] getEdges(Vector2d[] vertices) {
        Vector2d[] edges = new Vector2d[vertices.length];

        for (int i = 0; i < vertices.length; i++) {
            Vector2d vc = vertices[i];
            Vector2d vn = vertices[(i + 1) == vertices.length ? 0 : (i + 1)];
            edges[i] = Vector2d.sub(vc, vn);
        }

        return edges;
    }

    public static double[] project(Shape p, Vector2d axis) {
        Vector2d[] vertices = p.getVertices();
        axis.normalize();

        double min = Vector2d.dot(vertices[0], axis);
        double max = min;

        for (int i = 0; i < vertices.length; i++) {
            double proj = Vector2d.dot(vertices[i], axis);
            if (proj < min) {
                min = proj; 
            }

            if (proj > max) {
                max = proj;
            }
        }

        return new double[] {min, max};
    }
}


Related Questions


Polygon-Circle Collision Algorithm not working

Updated May 08, 2017 09:13 AM


Moving a Polygon based on Camera position [JAVA]

Updated April 14, 2015 02:35 AM


2D SAT Collision - Triangle and Square Problem

Updated November 01, 2017 23:13 PM