Jump to content
  • Advertisement
Sign in to follow this  
mathematical

SAT - Same Plane Triangle

This topic is 889 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've implemented a Seperating Axis test for two triangles. The test seems to work in all cases, except if the two triangles happen to be on the same plane. For the seprating axis, i'm testing the normals for both triangles, then the 9 axis i get from crossing the sides of the triangles.

 

My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that?

 

Any idea why it would fail only when the triangles are on the same plane? If it's any help, i've attached my code:

public static bool Intersects(Triangle triangle1, Triangle triangle2) {
    Vector3 t1_v0 = triangle1.p0.ToVector();
    Vector3 t1_v1 = triangle1.p1.ToVector();
    Vector3 t1_v2 = triangle1.p2.ToVector();

    Vector3 t1_f0 = t1_v1 - t1_v0; // B - A
    Vector3 t1_f1 = t1_v2 - t1_v1; // C - B
    Vector3 t1_f2 = t1_v0 - t1_v2; // A - C

    Vector3 t2_v0 = triangle2.p0.ToVector();
    Vector3 t2_v1 = triangle2.p1.ToVector();
    Vector3 t2_v2 = triangle2.p2.ToVector();

    Vector3 t2_f0 = t2_v1 - t2_v0; // B - A
    Vector3 t2_f1 = t2_v2 - t2_v1; // C - B
    Vector3 t2_f2 = t2_v0 - t2_v2; // A - C


    Vector3[] axisToTest = new[] {
        Vector3.Cross(t1_f0, t1_f1),
        Vector3.Cross(t2_f0, t1_f1),

        Vector3.Cross(t2_f0, t1_f0),
        Vector3.Cross(t2_f0, t1_f1),
        Vector3.Cross(t2_f0, t1_f2),

        Vector3.Cross(t2_f1, t1_f0),
        Vector3.Cross(t2_f1, t1_f1),
        Vector3.Cross(t2_f1, t1_f2),

        Vector3.Cross(t2_f2, t1_f0),
        Vector3.Cross(t2_f2, t1_f1),
        Vector3.Cross(t2_f2, t1_f2),
    };

    foreach(Vector3 axis in axisToTest) {
        if (!TriangleTriangleSAT(triangle1, triangle2, axis)) {
            return false;
        }
    }

    return true;
}

protected static bool TriangleTriangleSAT(Triangle triangle1, Triangle triangle2, Vector3 raw_axis) {
    Vector3 axis = Vector3.Normalize(raw_axis);

    Vector2 range1 = GetTriangleInterval(triangle1, axis);
    Vector2 range2 = GetTriangleInterval(triangle2, axis);

    float min1 = range1.X;
    float max1 = range1.Y;
    float min2 = range2.X;
    float max2 = range2.Y;

    if (max1 < min2 || max2 < min1) {
        return false;
    }

    /*if (range1.Y < range2.X || range2.Y < range1.X) {
        return false;
    }*/

    return true;
}

protected static Vector2 GetTriangleInterval(Triangle triangle, Vector3 axis) {
    Vector3[] vertices = new Vector3[] {
        triangle.p0.ToVector(),
        triangle.p1.ToVector(),
        triangle.p2.ToVector()
    };
    float min = Vector3.Dot(axis, vertices[0]);
    float max = min;

    for (int i = 0; i < vertices.Length ; ++i) {
        float value = Vector3.Dot(axis, vertices[i]);
        min = Min(min, value);
        max = Max(max, value);
    }

    return new Vector2(min, max);
}
Edited by mathematical

Share this post


Link to post
Share on other sites
Advertisement

That was it, problem solved. The robustness of the SAT is discussed in the book "Real Time Collision Detection", Chapter 5. Starts on page 156.

 

I attempted to implement the authors solution (Using much uglier code), but the results work as expected!

 

If anyone is interested, the final code is 


protected class AxisPrototype {
    Vector3 A;
    Vector3 B;
    Vector3 C;
    Vector3 D;

    public AxisPrototype(Vector3 a, Vector3 b, Vector3 c, Vector3 d) {
        A = a;
        B = b;
        C = c;
        D = d;
    }

    public Vector3 AB {
        get {
            return A - B;
        }
    }

    public Vector3 CD {
        get {
            return C - D;
        }
    }

    public Vector3 CA {
        get {
            return C - A;
        }
    }

    public bool GetAxis(out Vector3 result) {
        result = Vector3.Cross(AB, CD);

        if (result.LengthSquared() < 0.0001f) {
            Vector3 n = Vector3.Cross(AB, CA);
            result = Vector3.Cross(AB, n);
            if (result.LengthSquared() < 0.0001f) {
                return false;
            }
        }

        return true;
    }
}

public static bool Intersects(Triangle triangle1, Triangle triangle2) {
    Vector3 t1_v0 = triangle1.p0.ToVector();
    Vector3 t1_v1 = triangle1.p1.ToVector();
    Vector3 t1_v2 = triangle1.p2.ToVector();

    Vector3 t2_v0 = triangle2.p0.ToVector();
    Vector3 t2_v1 = triangle2.p1.ToVector();
    Vector3 t2_v2 = triangle2.p2.ToVector();

    AxisPrototype[] axisToTest = new AxisPrototype[] {
        new AxisPrototype(t1_v1, t1_v0, t1_v2, t1_v1),
        new AxisPrototype(t2_v1, t2_v0, t2_v2, t2_v1),

        new AxisPrototype(t2_v1, t2_v0, t1_v1, t1_v0),
        new AxisPrototype(t2_v1, t2_v0, t1_v2, t1_v1),
        new AxisPrototype(t2_v1, t2_v0, t1_v0, t1_v2),

        new AxisPrototype(t2_v2, t2_v1, t1_v1, t1_v0),
        new AxisPrototype(t2_v2, t2_v1, t1_v2, t1_v1),
        new AxisPrototype(t2_v2, t2_v1, t1_v0, t1_v2),

        new AxisPrototype(t2_v0, t2_v2, t1_v1, t1_v0),
        new AxisPrototype(t2_v0, t2_v2, t1_v2, t1_v1),
        new AxisPrototype(t2_v0, t2_v2, t1_v0, t1_v2),
    };

    foreach(AxisPrototype axis in axisToTest) {
        if (!TriangleTriangleSAT(triangle1, triangle2, axis)) {
            return false;
        }
    }

    return true;
}

protected static bool TriangleTriangleSAT(Triangle triangle1, Triangle triangle2, AxisPrototype axisProto) {
    Vector3 axis = new Vector3();
    if (!axisProto.GetAxis(out axis)) {
        return false; // Not a seperating axis
    }

    Vector2 range1 = GetTriangleInterval(triangle1, axis);
    Vector2 range2 = GetTriangleInterval(triangle2, axis);

    float min1 = range1.X;
    float max1 = range1.Y;
    float min2 = range2.X;
    float max2 = range2.Y;

    if (max1 < min2 || max2 < min1) {
        return false;
    }

    // Not a seperating axis
    /*if (range1.Y < range2.X || range2.Y < range1.X) {
        return false;
    }*/

    // Is a seperating axis
    return true;
}

protected static Vector2 GetTriangleInterval(Triangle triangle, Vector3 axis) {
    Vector3[] vertices = new Vector3[] {
        triangle.p0.ToVector(),
        triangle.p1.ToVector(),
        triangle.p2.ToVector()
    };
    float min = Vector3.Dot(axis, vertices[0]);
    float max = min;

    for (int i = 0; i < vertices.Length ; ++i) {
        float value = Vector3.Dot(axis, vertices[i]);
        min = Min(min, value);
        max = Max(max, value);
    }

    return new Vector2(min, max);
}

Share this post


Link to post
Share on other sites
in an implementation of mine years ago, I extracted additional planes besides the 9 cross products. I pre computed 3 additional planes per triangle taking the cross product of the triangle normal and each of its edge (ordered such that the generated plane normal pointed away from the center mass of the triangle, the points on the edge obviously being the point for that plane projection).

Share this post


Link to post
Share on other sites

My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that?

 

Why are you crossing the normals? As you mention yourself the possible separating axes are the two triangle normals and the 9 pairwise cross products of the edges. 

 

I also noticed that you are using an absolute tolerance. Christer wrote a good summary of relative and absolute tolerances here:

http://realtimecollisiondetection.net/pubs/Tolerances/

 

Another thing to watch out for are sliver triangles which can result in ill-defined face normals. A simple trick to build a robust face normal is to use the two shortest edges in the cross product.

Edited by Dirk Gregorius

Share this post


Link to post
Share on other sites

My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that?

 
Why are you crossing the normals? As you mention yourself the possible separating axes are the two triangle normals and the 9 pairwise cross products of the edges. 
 
I also noticed that you are using an absolute tolerance. Christer wrote a good summary of relative and absolute tolerances here:
http://realtimecollisiondetection.net/pubs/Tolerances/
 
Another thing to watch out for are sliver triangles which can result in ill-defined face normals. A simple trick to build a robust face normal is to use the two shortest edges in the cross product.

His question demonstrates why there are additional planes/axes to test for beyond the 3*3 edge cross products (and 2 plane normals). For each triangle, besides the main plane, there are also 3 additional planes/axes, totaling 17 (3 * 3 + 3 + 3 + 2). The 3 extra per triangle are the axes constructed with the cross between each edge and the plane normal (for right handed/clockwise triangles). The same reason is there are 15 for OBBs and not merely 9.

Share this post


Link to post
Share on other sites

 

My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that?

 

Why are you crossing the normals?

 

To see if more cross products are necessary.

Share this post


Link to post
Share on other sites

 

 

His question demonstrates why there are additional planes/axes to test for beyond the 3*3 edge cross products (and 2 plane normals). For each triangle, besides the main plane, there are also 3 additional planes/axes, totaling 17 (3 * 3 + 3 + 3 + 2). The 3 extra per triangle are the axes constructed with the cross between each edge and the plane normal (for right handed/clockwise triangles). The same reason is there are 15 for OBBs and not merely 9. 

 

Sorry, what you are writing is simply wrong! You only need to test axes that build a face on the Minkowski sum of the two triangles and there are *exactly* 11 possible separating axes you need test for two triangles. I recommend reading Christer's and Gino's books which are great resources on this topic.

 

I also gave a presentation on the topic which explains how to identify the possible separating axes (in particular for the edge/edge cases) and how this is related to the Minkowski space. You can download it e.g. here: http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip

Share this post


Link to post
Share on other sites


His question demonstrates why there are additional planes/axes to test for beyond the 3*3 edge cross products (and 2 plane normals). For each triangle, besides the main plane, there are also 3 additional planes/axes, totaling 17 (3 * 3 + 3 + 3 + 2). The 3 extra per triangle are the axes constructed with the cross between each edge and the plane normal (for right handed/clockwise triangles). The same reason is there are 15 for OBBs and not merely 9.


Sorry, what you are writing is simply wrong! You only need to test axes that build a face on the Minkowski sum of the two triangles and there are *exactly* 11 possible separating axes you need test for two triangles. I recommend reading Christer's and Gino's books which are great resources on this topic.

I also gave a presentation on the topic which explains how to identify the possible separating axes (in particular for the edge/edge cases) and how this is related to the Minkowski space. You can download it e.g. here: http://media.steampowered.com/apps/valve/2013/DGregorius_GDC2013.zip
Thank you, I stand corrected. I will research the math further.

Edit: I should add however, I don't see the axes (plane normals) in the event the triangles are coplanar, and the cross products as well as the two surface normals all point in the same direction? To me this problem is then reduced to a 2d problem, and my naive approach of extending the 2d solution into 3D space seemed to have circumvented that?

Share this post


Link to post
Share on other sites

Your observation is totally correct! None of the triangle/triangle tests (SAT, Moeller, ...) handle the co-planar case by default iirc, but all rely on handling it as a special case. Sorry, I should have pointed that out. I only read over the SAT part and the possible separating axes.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!