Search code examples
javascriptcollision-detectionoverlap

JavaScript Separating Axis Theorem

I'm trying to wrap my head around using the Separating Axis Theorem in JavaScript to detect two squares colliding (one rotated, one not). As hard as I try, I can't figure out what this would look like in JavaScript, nor can I find any JavaScript examples. Please help, an explanation with plain numbers or JavaScript code would be most useful.

Update: After researching lots of geometry and math theories I've decided to roll out a simplified SAT implementation in a GitHub repo. You can find a working copy of SAT in JavaScript here: https://github.com/ashblue/canvas-sat

Solution

  • Transforming polygons

    First you have to transform all points of your convex polygons (squares in this case) so they are all in the same space, by applying a rotation of angle.

    For future support of scaling, translation, etc. I recommend doing this through matrix transforms. You'll have to code your own Matrix class or find some library that has this functionality already (I'm sure there are plenty of options).

    Then you'll use code in the vain of:

    var transform = new Matrix();
transform.appendRotation(alpha);
points = transform.transformPoints(points);

    Where points is an array of Point objects or so.

    Collision algorithm overview

    So that's all before you get to any collision stuff. Regarding the collision algorithm, it's standard practice to try and separate 2 convex polygons (squares in your case) using the following steps:

    • For each polygon edge (edges of both polygon 0 and polygon 1):
      • Classify both polgyons as "in front", "spanning" or "behind" the edge.
      • If both polygons are on different sides (1 "in front" and 1 "behind"), there is no collision, and you can stop the algorithm (early exit).
    • If you get here, no edge was able to separate the polgyons: The polygons intersect/collide.

    Note that conceptually, the "separating axis" is the axis perpendicular to the edge we're classifying the polygons with.

    Classifying polygons with regards to an edge

    In order to do this, we'll classify a polygon's points/vertices with regards to the edge. If all points are on one side, the polygon's on that side. Otherwise, the polygon's spanning the edge (partially on one side, partially on the other side).

    To classify points, we first need to get the edge's normal:

    // this code assumes p0 and p1 are instances of some Vector3D class

var p0 = edge[0]; // first point of edge
var p1 = edge[1]; // second point of edge
var v = p1.subtract(p0);
var normal = new Vector3D(0, 0, 1).crossProduct(v);
normal.normalize();

    The above code uses the cross-product of the edge direction and the z-vector to get the normal. Ofcourse, you should pre-calculate this for each edge instead.

    Note: The normal represents the separating axis from the SAT.

    Next, we can classify an arbitrary point by first making it relative to the edge (subtracting an edge point), and using the dot-product with the normal:

    // point is the point to classify as "in front" or "behind" the edge
var point = point.subtract(p0);
var distance = point.dotProduct(normal);
var inFront = distance >= 0;

    Now, inFront is true if the point is in front or on the edge, and false otherwise.

    Note that, when you loop over a polygon's points to classify the polygon, you can also exit early if you have at least 1 point in front and 1 behind, since then it's already determined that the polygon is spanning the edge (and not in front or behind).

    So as you can see, you still have quite a bit of coding to do. Find some js library with Matrix and Vector3D classes or so and use that to implement the above. Represent your collision shapes (polygons) as sequences of Point and Edge instances.

    Hopefully, this will get you started.