c# - 怎么求两个三角形相交的面积

Question

给定顶点的位置和表面法线。如何计算两个三角形接触的面积(可能为 0)？这些三角形也在 3D 空间中，所以如果它们没有正确排列，只是相互挤压，接触面积应该为 0。(在 C# 中)

Answer 1

这不是一个微不足道的问题，所以让我们把它分解成几个步骤。

1. 检查两个三角形是否为coplanar ，否则面积为0。
2. 将三角形投影到二维表面上
3. 计算相交多边形
4. 计算面积

---

1。检查共面性

要使两个三角形共面，一个三角形的所有顶点必须位于另一个三角形确定的平面内。

使用描述的算法 here我们可以检查每个顶点是否是这种情况，但由于 float 不是完全精确的事实，您将需要定义一些错误阈值以确定仍然算作共面的东西。

假设 va 和 vb 分别是三角形 A 和 B 的向量，代码可能如下所示。
(注意:我从未使用过 Unity，所有代码都是靠内存编写的，所以如果不是 100% 正确，请原谅)。

public static bool AreTrianglesCoplanar(Vector3[] va, Vector3[] vb) {
    // make sure these are actually triangles
    Debug.Assert(va.Length == 3);
    Debug.Assert(vb.Length == 3);

    // calculate the (scaled) normal of triangle A
    var normal = Vector3.Cross(va[1] - va[0], va[2] - va[0]);

    // iterate all vertices of triangle B
    for(var vertex in vb) {
        // calculate the dot product between the normal and the vector va[0] --> vertex
        // the dot product will be 0 (or very small) if the angle between these vectors
        // is a right angle (90°)
        float dot = Vector3.Dot(normal, vertex - va[0]).

        // the error threshold
        const float epsilon = 0.001f;
        
        // if the dot product is above the threshold, the vertex lies outside the plane
        // in that case the two triangles are not coplanar
        if(Math.Abs(dot) > epsilon)
            return false;
    }

    return true;
}

2。将三角形投影到二维空间

我们现在知道所有六个顶点都在同一个嵌入到 3D 空间的 2D 平面中，但是我们所有的顶点坐标仍然是三维的。所以下一步是将我们的点投影到 2D 坐标系中，这样它们的相对位置就会被保留。

This answer很好地解释了数学。
首先，我们需要找到一组构成正交基的三个向量(它们必须彼此正交且长度为 1)。

1. 其中一个只是平面的法向量，因此我们还需要两个与第一个向量正交且彼此正交的向量。
2. 根据定义，三角形定义的平面中的所有向量都与法向量正交，因此我们可以只选择一个(例如从 va[0] 到 va 的向量[1]) 并将其归一化。
3. 第三个向量必须与其他两个向量正交，我们可以通过对前两个向量求叉积来找到这样一个向量。

我们还需要在平面上选择一个点作为我们的原点，例如 va[0]。

有了所有这些参数，并使用链接 amswer 中的公式，我们可以从其他答案)。请注意——因为我们所有的点都位于定义该法向量的平面内——第三个坐标(在另一个答案中称为 s)将始终(接近)零。

public static void ProjectTo2DPlane(
        Vector3[] va, Vector3[] vb
        out Vector2[] vaProjected, out Vector2[] vbProjecte
    ) {
    // calculate the three coordinate system axes
    var normal = Vector3.Cross(va[1] - va[0], va[2] - va[0]).normalized;
    var e1 = Vector3.Normalize(va[1] - va[0]);
    var e2 = Vector3.Cross(normal, e1);

    // select an origin point
    var origin = va[0];

    // projection function we will apply to every vertex
    Vector2 ProjectVertex(Vector3 vertex) {
        float s = Dot(normal, vertex - origin);
        float t1 = Dot(e1, vertex - origin);
        float t2 = Dot(e2, vertex - origin);
        // sanity check: this should be close to zero
        // (otherwise the point is outside the plane)
        Debug.Assert(Math.Abs(s) < 0.001);
        return new Vector2(t1, t2);
    }

    // project the vertices using Linq
    vaProjected = va.Select(ProjectVertex).ToArray();
    vbProjected = vb.Select(ProjectVertex).ToArray();
}

健全性检查:

• 顶点 va[0] 应该投影到 (0, 0)。
• 顶点 va[1] 应该被投影到 (*, 0)，所以在新的 x 轴上的某个地方。

3。/4.计算2D的交集面积

This answer这个答案提到了最后一步所需的算法。
Sutherland-Hodgman algorithm连续剪辑一个三角形与另一边的每一边。结果将是三角形、四边形或空多边形。

最后，shoelace formula可用于计算生成的裁剪多边形的面积。

将所有内容整合在一起

假设您实现了 CalculateIntersecionPolygon 和 CalculatePolygonArea 这两个函数，最终的交集面积可以这样计算:

public static float CalculateIntersectionArea(Mesh triangleA, Mesh triangleB) {
    var verticesA = triangleA.GetVertices();
    var verticesB = triangleB.GetVertices();

    if(!AreTrianglesCoplanar(verticesA, verticesB))
        return 0f; // the triangles are not coplanar

    ProjectTo2DPlane(verticesA, verticesB, out Vector2[] projectedA, out Vector2[] projectedB);

    CalculateIntersecionPolygon(projectedA, projectedB, out List<Vector2> intersection);

    if(intersection.Count == 0)
        return 0f; // the triangles didn't overlap

    return CalculatePolygonArea(intersection);
}