Let's suppose I have a triangle defined by three coordinates A, B and C and a line segment defined by two coordinates D and E in 3D euclidean space. Let's further suppose that the segment is intersecting the triangle. Now, I need to find out wether the line segment intersects the triangle at its "border". So my idea was to take each edge of the triangle (AB, BC and CA) and test wether one of them intersects with the segment DE. The problem is that I haven't found a solution for segment/segment intersection. I have found this one but it doesn't work. Help very appreciated.
Edit Based on MBo's answer, I have implemented a C# method:
// return: 0 -> segment parallel to plane
// return: 1 -> segment intersects an edge of the face
// return: -1 -> segments intersects the interior or the triangle or not at all
public static int SegmentTriangleIntersection(Vector3D a, Vector3D b, Vector3D c, Vector3D d, Vector3D e)
{
var ed = e - d;
var ba = b - a;
var ca = c - a;
var ad = a - d;
var det = (ed.X*-ba.Y*-ca.Z) + (-ba.X*-ca.Y*ed.Z) + (-ca.X*ed.Y*-ba.Z) - (ed.Z*-ba.Y*-ca.X) - (-ba.Z*-ca.Y*ed.X) -
(-ca.Z*ed.Y*-ba.X);
if (Vector3D.IsNearlyEqual(det, 0)) // segment parallel to triangle
return 0;
var det_t = (ad.X * -ba.Y * -ca.Z) + (-ba.X * -ca.Y * ad.Z) + (-ca.X * ad.Y * -ba.Z) - (ad.Z * -ba.Y * -ca.X) - (-ba.Z * -ca.Y * ad.X) -
(-ca.Z * ad.Y * -ba.X);
var t = det_t/det;
if (t >= 0 & t <= 1) // segment intersects plane of triangle
{
var det_u = (ed.X*ad.Y*-ca.Z) + (ad.X*-ca.Y*ed.Z) + (-ca.X*ed.Y*ad.Z) - (ed.Z*ad.Y*-ca.X) - (ad.Z*-ca.Y*ed.X) -
(-ca.Z*ed.Y*ad.X);
var u = det_u/det;
var det_v = (ed.X*-ba.Y*ad.Z) + (-ba.X*ad.Y*ed.Z) + (ad.X*ed.Y*-ba.Z) - (ed.Z*-ba.Y*ad.X) -
(-ba.Z*ad.Y*ed.X)-(ad.Z*ed.Y*-ba.X);
var v = det_v/det;
if (Vector3D.IsNearlyEqual(u, 0) && v >= 0 && v <= 1)
return 1;
if (Vector3D.IsNearlyEqual(v, 0) && u >= 0 && u <= 1)
return 1;
if (Vector3D.IsNearlyEqual(v + u, 1) && u >= 0 && v >= 0)
return 1;
}
return -1;
}