Understanding 2D Physics Engines with Phaser 3, Part 8: Triangle Collisions

Triangle vs Triangle Collision Detection with Rotation

In a prior post I took a quick look at GetRectagleToRectangle method of Phaser's Geom.Intersects class and noted that it seems to deal with rotated rectangles, not just AABB's. It did so by looping through every combination the 4 bounding edges of the two rectangles to see if there is any intersection. This got me curious as to how Phaser detects intersections for more "complicated" shapes, such as triangles.

In the world of generic physics engines, I do not think that triangles are typically used as physics bodies, however, along with the triangle to triangle methods explored below, Phaser provides a lot of other methods to detect overlaps between different shapes. I can imagine using the triangle vs circle intersection method might be useful in creating a Asteroids game, for example.

Anyway, this post only goes as far as the collision detection part and does not go into collision resolution or response. So this post is definitely more about studying Phaser's geometry functions.

Triangles with Rotation

The same Phaser class also has a method to detect intersections between two triangles.

<static> TriangleToTriangle(triangleA, triangleB)

The documentation states:

Checks if two Triangles intersect.

A Triangle intersects another Triangle if any pair of their lines intersects or if any point of one Triangle is within the other Triangle. Thus, the Triangles are considered "solid".

The underlying code (reproduced in full below) is actually long and complex.

The blue part checks for intersection between all combinations of the 3 triangle A edges vs 3 triangle B edges.

(I have explored the Line to Line and other shapes methods in my series on raycasting, here)

This in itself would not cover the case, if one of the triangles fit entirely inside the other, and it is the red highlighted code that checks for this condition.

Decompose method (associated with the Geom.Triangle object) is called to push all of the vertices of a triangle into an array.

Then ContainsArray method (associated with the Geom.Triangle object) is called to get the points that is "within" the triangle. Finding whether a point is contained within anything other than a rectangle or a circle is, in itself a complicated piece of code. Anyone interested in the logic for triangles may like to look at the site here, which is what the Phaser code is base on. It's fascinating stuff!

var TriangleToTriangle = function (triangleA, triangleB)
{
    //  First the cheapest ones:

    if (
        triangleA.left > triangleB.right ||
        triangleA.right < triangleB.left ||
        triangleA.top > triangleB.bottom ||
        triangleA.bottom < triangleB.top)
    {
        return false;
    }

    var lineAA = triangleA.getLineA();
    var lineAB = triangleA.getLineB();
    var lineAC = triangleA.getLineC();

    var lineBA = triangleB.getLineA();
    var lineBB = triangleB.getLineB();
    var lineBC = triangleB.getLineC();

    //  Now check the lines against each line of TriangleB
    if (LineToLine(lineAA, lineBA) || LineToLine(lineAA, lineBB) || LineToLine(lineAA, lineBC))
    {
        return true;
    }
    if (LineToLine(lineAB, lineBA) || LineToLine(lineAB, lineBB) || LineToLine(lineAB, lineBC))
    {
        return true;
    }
    if (LineToLine(lineAC, lineBA) || LineToLine(lineAC, lineBB) || LineToLine(lineAC, lineBC))
    {
        return true;
    }
    //  Nope, so check to see if any of the points of triangleA are within triangleB

    var points = Decompose(triangleA);
    var within = ContainsArray(triangleB, points, true);

    if (within.length > 0)
    {
        return true;
    }

    //  Finally check to see if any of the points of triangleB are within triangleA

    points = Decompose(triangleB);
    within = ContainsArray(triangleA, points, true);

    if (within.length > 0)
    {
        return true;
    }

    return false;
};

<static> GetTriangleToTriangle(triangleA, triangleB [, out])

As with the rectangle equivalent, there is a GetTriangleToTriangle method which returns the intersection points.

Ironically, the code is actually simpler than the TriangleToTriangle method which simply returns a boolean indicating whether the triangles are intersecting or not

var GetTriangleToTriangle = function (triangleA, triangleB, out)
{
    if (out === undefined) { out = []; }

    if (TriangleToTriangle(triangleA, triangleB))
    {
        var lineA = triangleB.getLineA();
        var lineB = triangleB.getLineB();
        var lineC = triangleB.getLineC();

        GetTriangleToLine(triangleA, lineA, out);
        GetTriangleToLine(triangleA, lineB, out);
        GetTriangleToLine(triangleA, lineC, out);
    }

    return out;
};

Somewhat similar to the equivalent method for rectangles, the code checks for intersection of the 3 edges of triangle B against triangleA, by calling the GetTriangleToLine method.

GetTriangleToLine, if one looks at the underlying code, actually calls Geom.Intersects.LineToLine method of the 3 triangle edges against the line passed.

Hence, the code is actually checking every edge of one triangle against every edge of the other triangle.

Sample Code

Below is a simple example which uses the Geom.Intersects.TriangleToTriangle method to detect overlap.