I recently followed this guide (http://www.dyn4j.org/2010/01/sat/) in my attempts to implement SAT in JavaScript/2d canvas. Alongside this material, I’ve scoured this site and many others for existing SAT implementations and help.

My project uses spacial segmentation, with each cell noting which object/s reside in it. When a cell contains more than one object, the SAT collision detection method runs on pairs of objects that can collide with each other (objects have a list of other objects they can collide with). This returns the overlap between axis projections (I think – although the result is the same if I opt for a Boolean approach).

For context, my current implementation is checking if a falling shape (at this point it doesn’t matter what the shape is as the result is the same) collides with a static “platform”.

The issue I’m having is false positives, where as soon as the falling object enters the cell of the platform, it detects a collision (almost as if it is colliding with the cell itself – which isn’t possible because the cell is never passed and is incompatible with the algorithm). That said, breakpoints reveal that there ARE instances where the overlap < 0 and the algorithm exits early. The following images demonstrate:

Example 1

Example 2 (adjusted cell sizes)

I feel like I must be doing something fundamental incorrectly, or that I’m being ignorant to something mathematically obvious. My hunch is that my overlap method is flawed.

I would really appreciate some fresh eyes over my code and any suggestions for fixes, thank you.

Notes:

– My mathematics capability is questionable, but I think I understand the concepts in use.

– I haven’t implemented penetration correction just yet.

– This is my first time using js/canvas and I’m a student (with limited time left to sort this out).

EDIT: I’m aware circles and SAT are typically incompatible – the “circle” in the images is a custom, regular polygon with something like 16 sides (and the result is the same for anything less round)…

My SAT class:

```
class SAT {
static detectCollision(pShapeA, pShapeB) { // Arguments are Shape.js objects. Have pos/rot/scale, mVertices[] and mEdges[].
var
i,
axesA = SAT.getAxes(pShapeA), // Get axes orthogonal to faces of shape A.
axesB = SAT.getAxes(pShapeB), // Get axes orthogonal to faces of shape B.
p1, p2,
overlap,
mtvAxis;
for (i = 0; i < axesA.length; i += 1) { // Project all vertices of each shape onto each of shape As axes.
p1 = SAT.project(pShapeA, axesA[i]);
p2 = SAT.project(pShapeB, axesA[i]);
overlap = SAT.overlap(p1, p2); // Calculate the amount of overlap (if any) between the projections min and max values.
if (overlap < 0) return overlap;
}
for (i = 0; i < axesB.length; i += 1) { // Project all vertices of each shape onto each of shape Bs axes.
p1 = SAT.project(pShapeA, axesB[i]);
p2 = SAT.project(pShapeB, axesB[i]);
overlap = SAT.overlap(p1, p2);
if (overlap < 0) return overlap; // Separation defined - exit algorithm.
}
return overlap; // No projections failed to overlap on any axis.
}
static getAxes(pShape) { // Calculate the normalised, normal vectors of a given shapes edges.
var
i,
count,
normal,
axes = [];
// All shapes will be regular, so if number of sides is even, only need to check half the axes.
if (pShape.mEdges.length % 2 === 0) {
count = pShape.mEdges.length / 2;
}
else {
count = pShape.mEdges.length;
}
for (i = 0; i < count; i += 1) {
//normal = pShape.mEdges[i].crossProduct(new Vector(0, 0, 1)).normalise(); // Get the normal to the current edge vector.
normal = new Vector(pShape.mEdges[i].getY(), -pShape.mEdges[i].getX()); // Shape objects calculate their edge vectors as vertices[x].subtract(vertices[y]).
axes.push(normal.normalise());
}
return axes;
}
static project(pShape, pAxis) {
pShape.mVertices[0].setZ(1);
var
i,
min = pAxis.dotProduct(pShape.mVertices[0].normalise()),
max = min,
curr; // Current projection.
for (i = 1; i < pShape.mVertices.length; i += 1) {
pShape.mVertices[i].setZ(1);
curr = pAxis.dotProduct(pShape.mVertices[i].normalise());
if (curr < min) {
min = curr;
}
else if (curr > max) {
max = curr;
}
}
return [min, max];
}
static overlap(pProjA, pProjB) { // Projections passed as an array [min, max].
var
a = pProjA[0], // projA min
b = pProjA[1], // projA max
c = pProjB[0], // projB min
d = pProjB[1]; // projB max
// Complete overlap.
if (a === c && b === d) return b - a;
// No collision.
if (a < c && b < c) return b - c; // Neg value - ab is left of cd & !overlapping.
if (c < a && d < a) return d - a; // As above but reversed.
// Absorption (one inside other).
if (a >= c && a < d && b <= d) {
if (a - c < d - b) return (b - a) + (a - c); // Check for smallest overlap option.
else return (b - a) + (d - b);
}
if (c >= a && c < b && d <= b) {
if (c - a < b - d) return (d - c) + (c - a); // Check for smallest overlap option.
else return (d - c) + (b - d);
}
// Partial overlap. Testing for less conditions since they SHOULD have already been exhausted...
if (b < d) return b - c;
else return d - a;
//if (a < c && b > c && b < d) return b - c;
//if (c < a && d > a && d < b) return d - a;
alert('Missing conditional'); // Isn't being called.
}
}
```