Trying to detect collision between two polygons using Separating Axis Theorem

Posted by Holly on Game Development See other posts from Game Development or by Holly
Published on 2012-10-20T14:29:50Z Indexed on 2012/10/20 17:15 UTC
Read the original article Hit count: 285

The only collision experience i've had was with simple rectangles, i wanted to find something that would allow me to define polygonal areas for collision and have been trying to make sense of SAT using these two links

Though i'm a bit iffy with the math for the most part i feel like i understand the theory! Except my implementation somewhere down the line must be off as:

(excuse the hideous font) enter image description here

As mentioned above i have defined a CollisionPolygon class where most of my theory is implemented and then have a helper class called Vect which was meant to be for Vectors but has also been used to contain a vertex given that both just have two float values.

I've tried stepping through the function and inspecting the values to solve things but given so many axes and vectors and new math to work out as i go i'm struggling to find the erroneous calculation(s) and would really appreciate any help. Apologies if this is not suitable as a question!

CollisionPolygon.java:

package biz.hireholly.gameplay;

import android.graphics.Canvas;
import android.graphics.Color;
import android.graphics.Paint;
import biz.hireholly.gameplay.Types.Vect;


public class CollisionPolygon {

    Paint paint;

    private Vect[] vertices;
    private Vect[] separationAxes;

    CollisionPolygon(Vect[] vertices){
        this.vertices = vertices;

        //compute edges and separations axes

        separationAxes = new Vect[vertices.length];
        for (int i = 0; i < vertices.length; i++) {
            // get the current vertex
            Vect p1 = vertices[i];
            // get the next vertex
            Vect p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
            // subtract the two to get the edge vector
            Vect edge = p1.subtract(p2);
            // get either perpendicular vector
            Vect normal = edge.perp();
            // the perp method is just (x, y) => (-y, x) or (y, -x)
            separationAxes[i] = normal; 
        }

        paint = new Paint();
        paint.setColor(Color.RED);

    }

    public void draw(Canvas c, int xPos, int yPos){

        for (int i = 0; i < vertices.length; i++) {
            Vect v1 = vertices[i];
            Vect v2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
            c.drawLine(
                    xPos + v1.x,
                    yPos + v1.y, 
                    xPos + v2.x, 
                    yPos + v2.y,
                    paint);
        }
    }

    /* consider changing to a static function */
    public boolean intersects(CollisionPolygon p){

        // loop over this polygons separation exes
        for (Vect axis : separationAxes) {
              // project both shapes onto the axis
            Vect p1 = this.minMaxProjection(axis);
            Vect p2 = p.minMaxProjection(axis);
              // do the projections overlap?
            if (!p1.overlap(p2)) {
                // then we can guarantee that the shapes do not overlap
                return false;
            }
        }

        // loop over the other polygons separation axes
        Vect[] sepAxesOther = p.getSeparationAxes();
        for (Vect axis : sepAxesOther) {
              // project both shapes onto the axis
            Vect p1 = this.minMaxProjection(axis);
            Vect p2 = p.minMaxProjection(axis);
              // do the projections overlap?
            if (!p1.overlap(p2)) {
                // then we can guarantee that the shapes do not overlap
                return false;
            }
        }
        // if we get here then we know that every axis had overlap on it
        // so we can guarantee an intersection
        return true;
    }

    /* Note projections wont actually be acurate if the axes aren't normalised 
     * but that's not necessary since we just need a boolean return from our 
     * intersects not a Minimum Translation Vector.
     */
    private Vect minMaxProjection(Vect axis) {
        float min = axis.dot(vertices[0]);
        float max = min;
        for (int i = 1; i < vertices.length; i++) {
            float p = axis.dot(vertices[i]);
            if (p < min) {
                min = p;
            }
            else if (p > max) {
                max = p;
            }
        }
        Vect minMaxProj = new Vect(min, max);
        return minMaxProj;
    }

    public Vect[] getSeparationAxes() {
        return separationAxes;
    }

    public Vect[] getVertices() {
        return vertices;
    }


}

Vect.java:

package biz.hireholly.gameplay.Types;

/* NOTE: Can also be used to hold vertices! Projections, coordinates ect */

public class Vect{
    public float x;
    public float y;

    public Vect(float x, float y){
        this.x = x;
        this.y = y;
    }

    public Vect perp() {
        return new Vect(-y, x);
    }

    public Vect subtract(Vect other) {
        return new Vect(x - other.x, y - other.y);
    }

    public boolean overlap(Vect other) {
        if( other.x <= y || other.y >= x){
            return true;
        }
        return false;
    }
    /* used specifically for my SAT implementation which i'm figuring out as i go,
     * references for later..
     * http://www.gamedev.net/page/resources/_/technical/game-programming/2d-rotated-rectangle-collision-r2604
     * http://www.codezealot.org/archives/55
     */
    public float scalarDotProjection(Vect other) {
        //multiplier = dot product / length^2
        float multiplier = dot(other) / (x*x + y*y);
        //to get the x/y of the projection vector multiply by x/y of axis
        float projX = multiplier * x;
        float projY = multiplier * y;
        //we want to return the dot product of the projection, it's meaningless but useful in our SAT case
        return dot(new Vect(projX,projY));

    }
    public float dot(Vect other){
        return (other.x*x + other.y*y);
    }

}

© Game Development or respective owner

Related posts about java

Related posts about android