检查3D点是否在凸多面体(方形金字塔)内部的算法 [英] Algorithm for checking if 3D point inside convex polyhedron (square pyramid)

问题描述

我正在寻找可靠的碰撞检测算法，并找到了克里斯特·埃里克森(Christer Ericson)的一本很棒的书，名为《 实时碰撞检测".我正在尝试使用一种特殊的算法，该算法检查给定点是否在凸多面体内部(在3D空间中，这些是四角锥，立方体和四面体(又名金字塔，所有边都是三角形)).就我而言，我有一个方形金字塔.通过使用给定数量的半空间的相交体积并确定该点是在由多面体的边跨过的所有平面的前面还是后面，来完成对点的验证.我很难理解参数n的用法(见下文)，该参数代表给定多面体的半角空格数:

I am looking robust collision detection algorithms and found an awesome book called Realtime Collision Detection by Christer Ericson. I am trying to use a particular algorithm which checks whether a given point is inside convex polyhedron (in 3D space these are the square pyramid, cube and tetrahedron (aka pyramid with all sides being a triangle)). In my case I have a square pyramid. The validation of the point is done by using the intersection volume for a given number of halfspaces and determining whether the point is in front or behind all of the planes that are spanned by the polyhedron's sides. I have difficulties understanding the usage of the argument n (see below) which represents the number of halfspaces for the given polyhedron:

// 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(...)计算给定点与平面之间的距离

with DistPointPlane(...) calculating the distance between a given point and a plane

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

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

and Plane being a structure that represents a plane in 3D space

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;
}

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

What the algorithm does is basically the following:

1. 对于给定点，计算其到凸多面体每个平面的距离
2. 检查距离是负数还是正数

1. For a given point calculate its distance to each plane of the convex polyhedron
2. Check if distance is negative or positive

1. 如果距离为负，则点位于平面法线的相对侧，因此位于其后方.
2. 其他点与飞机的法线位于同一侧，因此在其前方

如果指向给定多面体的所有平面之后，则位于内部，否则位于外部

If point behind all planes of the given polyhedron it lies inside else it lies outside

就我所知，现在就方形金字塔而言，有10个半空间，因为我们有4个侧面和一个底面，每个侧面代表一个单独的平面(所以总共有5个平面)将3D空间划分为两个半空间(5 planes * 2 = 10 halfspaces).我没有得到的是上面算法的代码中n的用法.它用作循环访问Plane实例数组的循环的终止条件.但是，如上所述，有10个半空间.

Now in terms of a square pyramid as far as I can tell there are 10 halfspaces since we have 4 sides and a base each representing a separate plane (so in total there are 5 planes) that divides the 3D space in two halfspaces (5 planes * 2 = 10 halfspaces). What I don't get is the usage of n in the code for the algorithm above. It is used as a termination condition for the loop which iterates through an array of Plane instances. However as mentioned there are 10 halfspaces.

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

One thing I have thought about after some digging is the fact that the intersection between two planes is a line (edge of the pyramid). Further quoting 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个)，但是书中的文字(包括函数实现上方的注释)含糊不清，阅读其中的内容可能会得出错误的主意(至少那是我的情况).

Each of the pyramid's vertices fulfill this requirement since for any given two sides (including the base) we get a line which is between two of the pyramid's vertices. So in terms of intersection we do have 5 (4 for the base and 1 for the apex) however the text in the book (including the comment above the function's implementation) is vague and reading it one might get the wrong idea (at least that's my case).

我的思路是否接近真理，或者我在数学知识方面缺少很多?

Is my line of thought close to the truth or am I missing some big chunk in terms of math knowledge?

我已将代码移植到Python 3，并更改了算法以仅遍历我的飞机列表，而无需接受其他参数(如果我的想法是正确的，则与原始参数基本相同)，并使用matplotlib.它工作得很好，但是我仍然想知道我是否正确理解了它:

I have ported the code to Python 3 and altered the algorithm to loop through just my list of planes without taking an additional argument (which, if my thoughts are correct, is basically the same as the original one) and plotted it with matplotlib. It works perfectly fine but I still want to know whether I have understood it correctly or not:

推荐答案

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

Basically your shape is a polyhedron but that is simply defined as a shape with many faces normally 6. You need to actually be looking for the name tetrahedron which is the classic pyramid shape you have defined in the visual representation above. But the basic answer is taking the normal of your 5 planes (the 4 triangles and one square), and check if they are facing in the same direction of the point in space. If they all return false then your point is inside of the shape. If any one of them returns true then you are outside the shape. This type of test works for most convex shapes because there is no case where the planes are overlapping there normals.

这篇关于检查3D点是否在凸多面体(方形金字塔)内部的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！