如何找到两个三角形相交的面积

Question

如何找到两个三角形相交的面积

c#algorithmunity-game-enginegeometry

3

已知三角形的顶点坐标和法向量，如何计算两个三角形之间接触的面积（可能为0）？由于这些三角形也存在于三维空间中，如果它们没有正确对齐，只是互相挤在一起，那么接触面积应该为0。(使用C#语言)

- user13955585

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mario Welzig · Accepted Answer

这不是一个简单的问题，因此让我们分解成几个步骤。

检查这两个三角形是否共面，如果不是，则它们的交集面积为0。
将三角形投影到二维平面上。
计算它们的交集多边形。
计算多边形的面积。

1. 检查共面性

为了使两个三角形共面，其中一个三角形的所有顶点必须位于另一个三角形确定的平面上。

使用此处描述的算法，我们可以检查每个顶点是否满足条件，但由于浮点数不是完全精确的，您需要定义一些误差阈值来确定仍然算作共面的情况。

假设va和vb分别是三角形A和B的向量，则代码可能如下所示。
（注意：我从记忆中编写所有代码，从未使用过Unity，因此如果不完全正确，请谅解）。

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. 将三角形投影到二维空间

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

这个答案很好地解释了数学原理。
首先，我们需要找到一个由三个向量组成的正交基（它们必须互相正交且长度为1）。

其中一个向量就是平面的法向量，因此我们需要另外两个向量，它们既正交于第一个向量，又正交于彼此。
根据定义，由我们的三角形定义的平面上的所有向量都与法向量正交，因此我们可以选择一个向量（例如从va [0]到va [1]的向量）并将其归一化。
第三个向量必须同时正交于前两个向量，我们可以通过取前两个向量的叉积来找到这样的向量。

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

有了所有这些参数，并使用链接答案中的公式，我们可以确定我们新的投影（x，y）坐标（来自其他答案的t_1和t_2）。请注意，由于我们所有的点都位于定义该法向量的平面上，因此第三个坐标（在其他答案中称为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中计算交叉区域

这个答案提到了完成最后一步所需的算法。
Sutherland-Hodgman算法逐个将一个三角形与另一个三角形的每条边进行裁剪。其结果可以是三角形、四边形或空多边形。

最后，鞋带公式可用于计算所得到的裁剪多边形的面积。

将所有内容结合起来

假设您已经实现了两个函数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);
}