检查3D点是否在凸多面体(四角金字塔)内的算法

Question

我正在寻找稳健的碰撞检测算法，并找到了一本很棒的书，名为 Realtime Collision Detection，作者是 Christer Ericson。我正在尝试使用一种特定的算法来检查给定点是否在凸多面体内部(在 3D 空间中，这些是方形金字塔、立方体和四面体(又名金字塔，所有边都是三角形))。在我的例子中，我有一个方形金字塔。通过使用给定数量的半空间的相交体积并确定该点是在多面体边所跨越的所有平面的前面还是后面来完成点的验证。我很难理解参数 n(见下文)的用法，它表示给定多面体的半空间数:

// Test if point p inside polyhedron given as the intersection volume of n halfspaces
int TestPointPolyhedron(Point p, Plane *h, int n) {
    for (int i = 0; i < n; i++) {
        if(DistPointPlane(p, h[i]) > 0.0f) return 0;
    }
    return 1;
}

用 DistPointPlane(...) 计算给定点和平面之间的距离

float DistPointPlane(Point q, Plane p) {
    return Dot(q, p.n) - p.d;
}

和Plane是表示3D空间中平面的结构

struct Plane {
    Vector n; // Plane normal. Point X on the plane satisfies Dot(n, X) = d
    float d;  // d = dot(n, p) for a given point on the plane
}

Plane ComputePlane(Point a, Point b, Point c) {
    Plane p;
    p.n = Normalize(Cross(b - a, c - a));
    p.d = Dot(p.n, a);
    return p;
}

算法主要做的事情如下:

1. 对于给定的点，计算它到凸多面体每个平面的距离
2. 检查距离是负数还是正数
   1. 如果距离为负值，则点位于平面法线的另一侧，因此它在法线后面。
   2. Else 点位于平面法线的同一侧，因此它在它的前面
3. 如果点在给定多面体所有平面的后面，它位于内部，否则它位于外部

据我所知，现在正方形金字塔有 10 个半空间，因为我们有 4 个边和一个底面，每个边代表一个单独的平面(因此总共有 5 个平面)，将 3D 空间分成两个半空间(5 个平面 * 2 = 10 个半空间)。我没有得到的是 n 在上述算法的代码中的用法。它用作遍历 Plane 实例数组的循环的终止条件。然而，如前所述，有 10 个半空间。

经过一番挖掘，我想到的一件事是两个平面之间的交点是一条线(金字塔的边缘)。进一步引用Wolfram Mathworld

To uniquely specify the line, it is necessary to also find a particular point on it. This can be determined by finding a point that is simultaneously on both planes

金字塔的每个顶点都满足此要求，因为对于任何给定的两侧(包括底部)，我们得到一条位于金字塔两个顶点之间的线。因此，就交集而言，我们确实有 5 个(底部 4 个，顶部 1 个)但是书中的文字(包括函数实现上方的注释)含糊不清，阅读它可能会产生错误的想法(至少那是我的情况)。

我的思路是否接近事实，或者我是否遗漏了大量数学知识？

我已将代码移植到 Python 3 并更改算法以循环遍历我的平面列表而不使用额外的参数(如果我的想法是正确的，它与原始参数基本相同)并用matplotlib。它工作得很好，但我仍然想知道我是否理解正确:

Answer 1

here's a similar question

基本上你的形状是一个多面体，但它被简单地定义为一个有许多面的形状，通常是 6。你实际上需要寻找名称四面体，它是你在上面的可视化表示中定义的经典金字塔形状。但基本的答案是获取 5 个平面(4 个三角形和一个正方形)的法线，并检查它们是否面向空间中的点的相同方向。如果它们都返回 false，那么您的点就在形状内部。如果其中任何一个返回真，那么你就在形状之外。这种类型的测试适用于大多数凸形，因为没有平面在法线处重叠的情况。