Trying to detect collision between two polygons using Separating Axis Theorem
- by Holly
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)
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);
}
}
