c++ - GJK算法三角面测试

Question

我正在重建我的 GJK 算法，但我在四面体的三角面测试方面遇到问题。不过，我的点和边测试已经完成。

我想测试原点是否在四面体之外并且最接近特定的三角形面。

到目前为止，我的方法是计算三角形面的法线并进行一系列点积测试以确定原点是否在该面的外部并且最接近该面。我的方法有一个主要问题:我不能保证我的法线朝外。请参阅我制作的这张图以获得更好的描述:

如您所见，同一个三角形，根据顶点的排序，需要不同的叉积“排序”来产生朝外的法线。我有什么办法可以确保它们朝外吗？如果没有，是否有更好的方法来测试这些面孔？这是我的流程示例:

if (dot(ABC, AO) > 0) {
        if (dot(ACD, AO) <= 0) {
            if (dot(ADB, AO) <= 0) {
                if (dot(DCB, DO) <= 0) {
                    // closest to face of ABC

                }
            }
        }
    }
}

引用:

ABC, ACD, ADB, DCB = triangular face normals (as you can see I'm assuming the 'left' triangle from the picture)

AO = vector from A to origin

DO = vector from A to origin

Answer 1

让我们来处理人脸 ABC。使用 N = cross(B-A, C-A) 形成法线。如果dot(N, D-A) > 0，则N为内指，需要反转。最后，如果需要，规范化 N 以获得一个正常的单位。