mathvectorlanguage-agnostic2dcross-product

How to compute triple product in 2D


I am following this article on how to code the GJK algorithm for collision detection, but instead of doing it in 3D, I do it in 2D.

However, at one point there is this piece of code :

bool Line(
    Simplex& points,
    vector3& direction)
{
    vector3 a = points[0];
    vector3 b = points[1];

    vector3 ab = b - a;
    vector3 ao =   - a;
 
    if (SameDirection(ab, ao)) {
        direction = ab.cross(ao).cross(ab);
    }

    else {
        points = { a };
        direction = ao;
    }

    return false;
}

As you can see he chains two cross product to find the next direction, but how could I do that in 2D ?

Here is a picture to make these vectors more clear :

Graphic of the AB and AO vectors


Solution

  • The vector cross triple product in 3D is

    p = a×(b×c)

    The full expansion can be computed with the following matrix/vector product

    |px|   | -ay*by-az*bz     ay*bx        az*bx      | | cx |
    |py| = |    ax*by      -ax*bx-az*bz    az*by      | | cy |
    |pz|   |    ax*bx         ay*bz      -ax*bx-ay*by | | cz |
    

    There are multiple 2D projections of the above depending if none, one or two of the vectors a, b or c are out of plane (with a z component non-zero).

    In your case all three vectors are in plane (az=0, bz=0 and cz=0) which yields the following result

    |px|   | -ay*by   ay*bx               0 | | cx |   | ay*(bx*cy-by*cx) |
    |py| = |  ax*by  -ax*bx               0 | | cy | = | ax*(by*cx-bx*cy) |
    | 0|   |      0       0    -ax*bx-ay*by | |  0 |   |                0 |
    

    So there you have it. The right-hand side of the above is the result of a×(b×c) in 2D.