I'm trying to implement collision detection for concave polygons in Javascript/p5.js using the Separating Axis Theorem. I've been following the following tutorial on how to use it: http://www.dyn4j.org/2010/01/sat/
However, my check is always returning true, no matter the positioning of the two polygons. Here's my code:
function SAT(shape1, shape2)
{
let axes1 = getAxes(shape1);
let axes2 = getAxes(shape2);
let colliding = true;
for (let i = 0; i < axes1.length; i++)
{
let axis = axes1[i];
let p1 = shape1.project(axis);
let p2 = shape2.project(axis);
if (!p1.overlap(p2)) colliding = false;
}
for (let i = 0; i < axes2.length; i++)
{
let axis = axes2[i];
let p1 = shape1.project(axis);
let p2 = shape2.project(axis);
if (!p1.overlap(p2)) colliding = false;
}
return colliding;
}
function getAxes(shape)
{
let axes = [];
for (let i = 0; i < shape.vertices.length; i++)
{
let p1 = shape.vertices[i];
let p2 = shape.vertices[i + 1 == shape.vertices.length ? 0 : i + 1];
let edge = p1.sub(p2);
let normal = createVector(-edge.y, edge.x);
axes[i] = normal;
}
return axes;
}
class Projection
{
constructor(min, max)
{
this.min = min;
this.max = max;
}
overlap(other)
{
if (this.max < other.min || other.max < this.min) return false;
else return true;
}
}
class PolygonCollider extends Component
{
constructor(gameObject)
{
super(gameObject);
this.untransformedVertices = [];
this.vertices = [];
...
}
setVerts(verts)
{
if (verts && verts.length > 2)
{
this.untransformedVertices = verts;
this.vertices = this.transform.getTransformedPoints(verts);
return this;
}
else return false;
}
project(axis)
{
let min = axis.dot(this.vertices[0]);
let max = min;
for (let i = 1; i < this.vertices.length; i++)
{
let p = axis.dot(this.vertices[i]);
if (p < min) min = p;
else if (p > max) max = p;
}
return new Projection(min, max);
}
update()
{
this.vertices = this.transform.getTransformedPoints(this.untransformedVertices);
}
...
}
Vertices are transformed with the following function, using a defined scale, rotation and position:
getTransformedPoints(points)
{
let transformed = [];
for (let i = 0; i < points.length; i++)
{
let rX = ((this.scale.x * points[i].x) * Math.cos(this.rotation)) - ((this.scale.y * points[i].y) * Math.sin(this.rotation));
let rY = ((this.scale.x * points[i].x) * Math.sin(this.rotation)) + ((this.scale.y * points[i].y) * Math.cos(this.rotation));
transformed[i] = createVector(rX + this.position.x, rY + this.position.y);
}
return transformed;
}
The SAT method is always returning true. I believe I'm checking for the overlap incorrectly, but I can't figure out what exactly I'm doing wrong.
So, it turns out the issue with my implementation lied with p5.js, a library I am using in this case.
In the
getAxes
method, I was subtractingp1
fromp2
using p5's built inp5.Vector.sub
function. This didn't have the desired effect. I'm not sure, but I believe the issue was that it wasn't creating a new vector that was the difference of the equation. I fixed this simply by creating the new vector myself as such:createVector(p2.x - p1.x, p2.y - p1.y);