[游戏开发]Unity/C# 求三维空间中两个三角形相交的算法

原理在这里：https://web.stanford.edu/class/cs277/resources/papers/Moller1997b.pdf
这里有一个老哥写的中文笔记：
https://blog.csdn.net/shenyi0_0/article/details/107831862
这篇论文也有对这个算法的一定解释：
三维网格模型实体布尔运算方法的研究与实现 杨兰

代码如下：

const float Epsilon = 1.0E-10F;
readonly int[][] CrossLines = new int[][]
{
    new int[]{ 0, 2 }, 
    new int[]{ 0, 1 },
    new int[]{ 1, 2 }
};
readonly int[][] LineEndpointPairs = new int[][]
{
    new int[]{ 0, 1 },
    new int[]{ 1, 2 },
    new int[]{ 2, 0 },
};

// Tomas Moller 快速三角形求交算法
var T1 = targetMesh.triangles[i];
var T2 = patternMesh.triangles[j];

var v10 = targetMesh.vertices[T1.p0].pw; //世界坐标
var v11 = targetMesh.vertices[T1.p1].pw;
var v12 = targetMesh.vertices[T1.p2].pw;

var v20 = patternMesh.vertices[T2.p0].pw;
var v21 = patternMesh.vertices[T2.p1].pw;
var v22 = patternMesh.vertices[T2.p2].pw;

var n1 = Vector3.Cross(v11 - v10, v12 - v10);
var n2 = Vector3.Cross(v21 - v20, v22 - v20);

var d = Vector3.Cross(n1, n2);

// 两三角形平行
if (d.magnitude < Epsilon)
{
    continue;
}

var d1 = Vector3.Dot(n1, v10);
var d2 = Vector3.Dot(n2, v20);

var d10 = Vector3.Dot(n2, v10) - d2;
var d11 = Vector3.Dot(n2, v11) - d2;
var d12 = Vector3.Dot(n2, v12) - d2;

var d20 = Vector3.Dot(n1, v20) - d1;
var d21 = Vector3.Dot(n1, v21) - d1;
var d22 = Vector3.Dot(n1, v22) - d1;

var dis1 = new float[]{ d10, d11, d12 };
var dis2 = new float[]{ d20, d21, d22 };

int[] distancesSign1 = new int[3];
int[] distancesSign2 = new int[3];
for (int k = 0; k < 3; k++)
{
    distancesSign1[MathF.Sign(dis1[k]) + 1]++;
    distancesSign2[MathF.Sign(dis2[k]) + 1]++;
}


// 两三角形所在平面不相交
if (distancesSign1.Contains(3) || distancesSign2.Contains(3))
{
    continue;
}

// 单顶点相交，其他部分在同一侧
if (distancesSign1[1] == 1 && distancesSign1.Contains(2))
{
    continue;
}
if (distancesSign2[1] == 1 && distancesSign2.Contains(2))
{
    continue;
}

// 两边都是单顶点相交
if (distancesSign1[1] == 1 && distancesSign2[1] == 1)
{
    continue;
}

//0: p0-p1, 1: p1-p2, 2: p2-p0
int[] l1, l2;
if (distancesSign1[0] == 1) // 一个顶点在平面之下
{
    l1 = CrossLines[Array.FindIndex(dis1, a => a < 0)];
}
else
{
    l1 = CrossLines[Array.FindIndex(dis1, a => a > 0)];
}
if (distancesSign2[0] == 1) // 一个顶点在平面之下
{
    l2 = CrossLines[Array.FindIndex(dis2, a => a < 0)];
}
else
{
    l2 = CrossLines[Array.FindIndex(dis2, a => a > 0)];
}


float[] p1, p2;

if (Mathf.Abs(d.x) >= Mathf.Abs(d.y) && Mathf.Abs(d.x) >= Mathf.Abs(d.z))
{
    p1 = new float[] { v10.x, v11.x, v12.x };
    p2 = new float[] { v20.x, v21.x, v22.x };
}
else if (Mathf.Abs(d.y) >= Mathf.Abs(d.x) && Mathf.Abs(d.y) >= Mathf.Abs(d.z))
{
    p1 = new float[] { v10.y, v11.y, v12.y };
    p2 = new float[] { v20.y, v21.y, v22.y };
}
else
{
    p1 = new float[] { v10.z, v11.z, v12.z };
    p2 = new float[] { v20.z, v21.z, v22.z };
}

var t1 = new float[2];
var t2 = new float[2];

for (int k = 0; k < 2; k++)
{
    var endPoints = LineEndpointPairs[l1[k]];
    t1[k] = p1[endPoints[0]] + (p1[endPoints[1]] - p1[endPoints[0]]) 
        * dis1[endPoints[0]] / (dis1[endPoints[0]] - dis1[endPoints[1]]);
}

for (int k = 0; k < 2; k++)
{
    var endPoints = LineEndpointPairs[l2[k]];
    t2[k] = p2[endPoints[0]] + (p2[endPoints[1]] - p2[endPoints[0]]) 
        * dis2[endPoints[0]] / (dis2[endPoints[0]] - dis2[endPoints[1]]);
}


if ((t1.Max() >= t2.Max() && t1.Min() <= t2.Max()) ||
    (t2.Max() >= t1.Max() && t2.Min() <= t1.Max()))
{
    // 有相交，根据l数组的信息继续求平面交点即可
}