algorithm - 四面体边缘测试

Question

当测试一个点对应于一个四面体时，有 4 种情况。它位于四面体内部，最接近顶点、最接近边或最接近面。这是它的二维图，http://i.imgur.com/AmYNO.png .例如，当 P - A 和 B - A、C - A 和 D - A 的点积均为负时，点 P 最接近顶点 A。如果您要沿法线方向拉伸(stretch)三角形面以创建棱镜，则如果该点包含在该空间内，则该点将最接近该面。如果这两种情况都不是，它将最接近边缘。

我希望能够在不依赖顶点或面测试结果的情况下专门测试它是否最接近边缘。有没有相对有效的方法来做到这一点？四面体不是规则的。

Answer 1

您的意思是，最接近特定边缘，还是通常最接近边缘(而不是顶点或平面)？

如果是前者，那么如果一个点位于四个半空间的交点上，则该点最接近(特定的)边，这两个半空间由垂直于相邻面并穿过边的两个平面定义，并且两个平面垂直于边并通过相邻的顶点。因此，针对所有四个平面测试您的点，如果它位于适合所有平面的半空间内，则它最接近该边缘。

具体来说，假设我们要测试点 P 是否最接近边 AB，边 AB 位于面 ABC 和BAD(顺时针给出的顶点)。那么四个测试分别是:

• (P - A) · (A - B) < 0
• (P - B) · (B - A) < 0
• (P - A) · ((B - C) × (A - C) × (A - B)) < 0
• (P - B) · ((A - D) × (B − D) × (B − A)) < 0

(我想知道是否有更便宜的方法来进行第三次和第四次测试？如果您知道，请告诉我!)