How to choose one of two correct intersection between plane and triangle edges in 3D?

Question

I have a line(A, B) and a triangle(P0, P1, P2) somewhere in 3D space. In other words, I have 3 points ([x,y,z] each) for the triangle, and two points (also [x,y,z]) for the line. One point of line lie inside triangle(A or B). The main goal is find intersection on triangle edge that forms part of line (A, B) on the screen.

What I do:

1. Calculate plane Normal from line start (A), line end (B) and Camera position:

    Vector3 Normal = Vector3.Cross(A - cameraPos, B - cameraPos);

2. Find two intersections by checking each edge of triangle:

    bool IsPlaneIntersectLine(Vector3 Normal, Vector3 A, Vector3 B, Vector3 EdgePoint1, Vector3 EdgePoint2, out Vector3 Intersection)
    {
        float dotProduct = Vector3.Dot(Normal, (EdgePoint1 - EdgePoint2));
        if (dotProduct == 0f)
            return false;
        float dot1 = Vector3.Dot(Normal, (A - EdgePoint2));
        float distance = dot1 / dotProduct;
        if (distance > 1f || distance < 0f)
            return false;
        Intersection = EdgePoint2 + distance * (EdgePoint1 - EdgePoint2);
        return true;
    }

    Vector3 intersection1, intersection2, intersection3;
    bool isEdge1Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P0, triangle.P1, out intersection1);
    bool isEdge2Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P1, triangle.P2, out intersection2);
    bool isEdge3Intersected = IsPlaneIntersectLine(Normal, A, B, triangle.P2, triangle.P0, out intersection3);

As a result I have two intersections, but only one is correct - the intersection, that is a part of line (A, B) on screen. Also I have limitations - I can't convert this points to screen space for checking - which of two intersection points is between A and B.

Also I tried check dot product between line vector and intersection vector:

    float dot = Vector3.Dot((Intersection - A), (B - A));
    if (dot < 0f)
    {
        return false;
    }

But there is some triangles/edges that doesn't suitable for this condition.

How to find one intersection on triangle edge that forms part of line (A, B) on the screen?

Answer 1

As I already described one approach in my previous answer, pertaining to a more general algorithm, one direct way to check for this particular situation is to form the two cross-product vectors

V1 = Vector3.Cross((A - cameraPos), (Intersection - cameraPos))

V2 = Vector3.Cross((Intersection - cameraPos), (B - cameraPos))

These two vectors are perpendicular to the plane (cameraPos, A, B) and therefore lie on a common line. If both of them point in the same direction, then when rotating your gaze around cameraPos starting from point A towards point B, you will see first point A, then point Intersection and then point B. If, however, the vectors V1 and V2 point in opposite directions, then you are not going to see point Intersection between the points A and B. So, in order to resolve your issue, I excpect the following algorithm to do the job:

V1 =  Vector3.Cross((A - cameraPos), (Intersection - cameraPos));
V2 =  Vector3.Cross((Intersection - cameraPos), (B - cameraPos));
dot = Vector3.Dot(V1, V2);

if dot < 0f
{
   return false
} 

One remark, all these algorithms apply mostly to visible triangles, so for triangles that are not visible, one needs to be careful. Also, if A and B are in the same triangle, these algorithms encounter an exception. And if A is already on one a triangle's edge, then this fix is unnecessary and I think that you can directly go to step 3 from the general algorithm.

Answer 2

What's coming up here is a game developer's answer, not a geometry major's, so it would make most math people cringe, but it should generally work.

Since triangles are planar, and you've already calculated the planar normal, you can create a transform matrix that will Rotate the triangle so it's normal is straight up and Translate it's center to [0,0,0]. (I can't explain the math to create this matrix off the top of my head, but there are many open-source libraries with this logic built in, basically an inverse "look at" matrix). This is effectively a world-to-local-space matrix.

Once you have that matrix, you can apply it to the two points on the line to move that into local space, and then you have the very simple task of determining where the line intersects the XZ axes plane (i.e. solve for where Y equals zero). While you have everything in temporary 2D here, you can use barycentric coordinates to check if the intersection point is in the triangle, on a border, or outside entirely pretty easily too.

Once you have your answer point in local space, transform it by the inverse of your matrix to move it back to world space, and you should be done.

Answer 3

If you want a 2D intersection, of line and at most two edges, as seen on the screen, then you need first to calculate projected coordinates.
For details, search for any good tutorial where you learn about transformations (by using 4x4 matrices). Be sure to understand three transformations: Model, View, and Projection. Once you have 2D data (dismiss "depth" coordinate after projection) your problem reduces to test three 2D line-line intersections.

If you whish a 3D intersection (raw data, no transformations) then search for line-plane intersection (plane of the triangle). Once you get the intersection point, if any, calculate distances from this point to each edge.