我正在寻找强大的碰撞检测算法,并发现了一本很棒的书,称为实时碰撞检测克里斯特埃里克森。我正在尝试使用一种特殊的算法来检查给定点是否在凸多面体(在三维空间中,这些是正方形棱锥体、立方体和四面体(即所有边都是三角形的棱锥体))在我的情况下,我有一个方形金字塔通过使用给定数量的半空间的交集体积并确定该点是在由多面体侧面跨越的所有平面的前面还是后面来验证该点。我很难理解参数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;
}
计算给定点与平面之间的距离
float DistPointPlane(Point q, Plane p) {
return Dot(q, p.n) - p.d;
}
是一个在三维空间中代表一个平面的结构
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个平面),将三维空间分成两个半空间(
DistPointPlane(...)
)。我没有得到的是在上面算法的代码中使用Plane
。它被用作循环的终止条件,循环遍历一个5 planes * 2 = 10 halfspaces
实例数组。然而,如前所述,有10个半空间。经过一番挖掘,我想到的一件事是两个平面的交点是一条直线(金字塔的边缘)。进一步引用Wolfram Mathworld
要唯一地指定行,还需要找到
关于它的特别点。这可以通过找到一个
同时在两个平面上
每个金字塔的顶点都满足这一要求,因为对于任何给定的两边(包括底部),我们都会得到一条位于金字塔两个顶点之间的线所以在交集方面,我们确实有5个(4个表示基部,1个表示顶点),但是书中的文本(包括函数实现上面的注释)是模糊的,阅读它可能会得到错误的想法(至少这是我的情况)。
我的思路是接近事实,还是我在数学知识方面遗漏了一大块?
我已经将代码移植到了Python 3中,并修改了算法,只循环遍历我的平面列表,而不需要额外的参数(如果我的想法正确的话,基本上与原始参数相同),并用
n
绘制了它它工作得很好,但我仍然想知道我是否正确理解了它:最佳答案
here's a similar question
基本上,你的形状是一个多面体,但这只是简单地定义为一个有许多面的形状,通常是6实际上,您需要查找名称四面体,这是您在上面的可视化表示中定义的经典金字塔形状。但基本的答案是取5个平面(4个三角形和1个正方形)的法线,并检查它们是否朝向空间中的点的同一方向。如果它们都返回false,那么你的点就在形状的内部。如果其中任何一个返回true,则表示您在形状之外。这种类型的测试适用于大多数凸面形状,因为不存在平面与法线重叠的情况。