线段 3D 线段相交

Question

假设我有一个由三个坐标 A、B 和 C 定义的三角形和一个由 3D 欧几里得空间中的两个坐标 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。 如果线段在 [0..1] 范围内，则线段与平面相交t

如果是，请检查u, v参数是否符合上述边缘条件