0

我正在寻找强大的碰撞检测算法，并找到了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;
}

该算法的作用基本上如下：

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

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

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

要唯一指定线，还需要在其上找到一个特定点。这可以通过找到同时在两个平面上的点来确定

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

我的思路是否接近事实，还是我在数学知识方面遗漏了一些重要内容？

我已将代码移植到 Python 3 并更改了算法以仅循环遍历我的平面列表，而无需使用其他参数（如果我的想法正确，则与原始参数基本相同）并将其绘制为matplotlib. 它工作得很好，但我仍然想知道我是否理解正确：

在此处输入图像描述

4

2 回答 2

1

这是一个类似的问题

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

于 2018-04-09T08:16:47.377 回答
0

我会说你最了解它。我不确定您对“距离”的确切含义。通常点积提供两个向量之间的角度。在您的情况下，有一个位置向量（点）和一个法线向量。由于余弦定律，如果点积大于 0，则两个向量之间的夹角小于 90 度。另一方面，如果乘积为负，则角度大于 90 度。如果为 0，则向量是正交的。所以基本上它与距离无关，而是与角度有关。

于 2018-04-07T15:14:39.780 回答