我正在寻找强大的碰撞检测算法，并找到了Christer Ericson的一本名为Realtime Collision Detection的很棒的书。我正在尝试使用一种特定的算法来检查给定点是否在凸多面体内部（在 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;
}
该算法的作用基本上如下：
- 对于给定的点，计算它到凸多面体每个平面的距离
- 检查距离是负数还是正数
- 如果距离为负，则点位于平面法线的另一侧，因此它在其后面。
- 其他点与平面法线位于同一侧，因此它在它的前面
- 如果点在给定多面体的所有平面后面，则它位于内部，否则位于外部
现在就我所知的方形金字塔而言，有 10 个半空间，因为我们有 4 个边和一个底，每个边代表一个单独的平面（因此总共有 5 个平面），将 3D 空间分成两个半空间（5 planes * 2 = 10 halfspaces）。我没有得到的是n上面算法的代码中的用法。它用作循环遍历Plane实例数组的终止条件。然而，如前所述，有 10 个半空格。
经过一番挖掘，我想到的一件事是两个平面之间的交点是一条线（金字塔的边缘）。进一步引用Wolfram Mathworld
要唯一指定线，还需要在其上找到一个特定点。这可以通过找到同时在两个平面上的点来确定
金字塔的每个顶点都满足这个要求，因为对于任何给定的两侧（包括底部），我们得到一条位于金字塔两个顶点之间的线。因此，就交集而言，我们确实有 5 个（基数为 4，顶点为 1）但是书中的文本（包括函数实现上方的注释）是模糊的，阅读它可能会得到错误的想法（至少那是我的情况）。
我的思路是否接近事实，还是我在数学知识方面遗漏了一些重要内容？
我已将代码移植到 Python 3 并更改了算法以仅循环遍历我的平面列表，而无需使用其他参数（如果我的想法正确，则与原始参数基本相同）并将其绘制为matplotlib. 它工作得很好，但我仍然想知道我是否理解正确：
