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

问题描述

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

//测试多面体内的点 p 是否为 n 个半空间的交集体积int TestPointPolyhedron(点p，平面*h，int n){for (int i = 0; i < n; i++) {if(DistPointPlane(p, h[i]) > 0.0f) return 0;}返回 1；}

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

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

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

struct Plane {向量 n;//平面法线.平面上的点 X 满足 Dot(n, X) = d浮动 d;//d = dot(n, p) 对于平面上的给定点}平面计算平面(点a，点b，点c){平面 p;p.n = Normalize(Cross(b - a, c - a));p.d = 点(p.n，a)；返回 p;}

算法的基本作用如下:

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

3. 如果点在给定多面体的所有平面后面，它位于里面，否则它位于外面

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

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

解决方案

这里有一个类似的问题

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

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

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

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. For a given point calculate its distance to each plane of the convex polyhedron
2. Check if distance is negative or positive
   1. If distance is negative point lies on the opposite side of the plane's normal so it's behind it.
   2. Else point lies on the same side as the plane's normal so it's in front of it

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

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.

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

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?

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:

解决方案

here's a similar question

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屋！