Сегмент Пересечение сегмента

Question

Предположим, у меня есть треугольник, определенный тремя координатами A, B и C, и отрезок, определенный двумя координатами D и E в трехмерном евклидовом пространстве. Далее предположим, что отрезок пересекает треугольник. Теперь мне нужно выяснить, пересекает ли отрезок линии треугольник на его "границе". Поэтому моя идея заключалась в том, чтобы взять каждый край треугольника (AB, BC и CA) и проверить, пересекается ли один из них с сегментом DE. Проблема в том, что я не нашел решения для пересечения сегмента / сегмента. Я нашел это, но это не работает. Помощь очень ценится.

Редактировать Основываясь на ответе MBo, я реализовал метод C#:

// 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;
}

Answer 1

Давайте использовать параметрические уравнения для координат (векторы выделены жирным шрифтом):

Сегмент DE:
sDE(t) = D + t * (E - D) = D + t * ED
//ED = E - D

Сегмент AB:
sAB(u) = A + u * (B - A) = A + u * BA

Сегмент AC:
sAC(v) = A + v * (C - A) = A + u * CA

Плоскость треугольника ABC описывается двухпараметрическим уравнением:
pABC(u, v) = A + u * BA + v * CA

Точка на плоскости с координатами (u, v) лежит внутри треугольника, если

u in range [0..1]
and 
v in range [0..1]
and
u+v is in range [0..1]

Точка с координатами (u, v) лежит на краю треугольника, если [условие края]

u = 0 and v in range [0..1]    //at AC edge
or
v = 0 and u in range [0..1]    //at AC edge
or
v + u = 1 and u in range (0..1) and v in range (0..1)      //at BC edge

Теперь напишем уравнение для пересечения сегмента DE и плоскости ABC

sDE(t) = pABC(u, v)
D + t * ED = A + u * BA + v * CA

Мы можем решить последнее уравнение (система из 3 линейных уравнений для каждой координаты) и найти параметры t,u,v

D.X + t * ED.X = A.X + u * BA.X + v * CA.X
D.Y + t * ED.Y = A.Y + u * BA.Y + v * CA.Y
D.Z + t * ED.Z = A.Z + u * BA.Z + v * CA.Z

t * ED.X - u * BA.X - v * CA.X = A.X - D.X
t * ED.Y - u * BA.Y - v * CA.Y = A.Y - D.Y
t * ED.Z - u * BA.Z - v * CA.Z = A.Z - D.Z

Сначала найдите определитель этой системы - если она равна нулю, сегмент параллелен плоскости.

Если нет, проверьте параметр t. Сегмент пересекает плоскость, если t находится в диапазоне [0..1]

Если да, проверьте, u, v параметры соответствуют краевым условиям выше