algorithm - 如何确定一个点是否位于 3D 三角形上

Question

我需要一个快速算法的示例，该算法允许计算一个点是否位于 3D 三角形上。我的意思是如果这个点在包含给定三角形的平面上的投影在这个三角形的内部。

我需要计算一个点和一个三角形之间的距离(如果它的投影位于三角形内部，则为点与三角形面之间的距离；如果投影位于三角形外部，则为点与三角形边之间的距离)。

希望我说得足够清楚了。我找到了一些使用重心坐标的 2D 示例，但找不到任何 3D 示例。有没有比计算点的投影、将这个投影点和给定的三角形投影到 2D 并解决标准的“三角形中的点”问题更快的方法？

Answer 1

如果三角形的顶点是 A、B、C，点是 P，那么首先要找到三角形的法线 N。为此只需计算 N = (B-A) X (C-A)，其中 X 是矢量叉积。

目前，假设 P 与其法线位于 ABC 的同一侧。

考虑具有面 ABC、ABP、BCP、CAP 的 3d 金字塔。当且仅当 ABC 与其他 3 个三角形中的每一个之间的二面角都小于 90 度时，P 在 ABC 上的投影在其中。反过来，这些角度等于 N 与相应的外向三角形法线之间的角度!所以我们的算法是这样的:

Let N = (B-A) X (C-A), N1 = (B-A) X (P-A), N2 = (C-B) X (P-B), N3 = (A-C) X (P-C)
return N1 * N >= 0 and N2 * N >= 0 and N3 * N >= 0;

星星是点积。

我们仍然需要考虑 P 位于 ABC 对面的情况。有趣的是，在这种情况下，向量 N1、N2、N3 现在指向金字塔内，而在上述情况下，它们指向外部。这取消了相反的法线，上面的算法仍然提供了正确的答案。 (当发生这种情况时你不喜欢它吗？)

3d 中的叉积各需要 6 次乘法和 3 次减法。点积是 3 次乘法和 2 次加法。平均而言(考虑到如果 N1 * N < 0，则无需计算 N2 和 N3)，该算法需要 2.5 个叉积和 1.5 个点积。所以这应该很快。

如果三角形的构成可能很差，那么您可能想要使用 Newell 算法来代替任意选择的叉积。

请注意，这里不处理任何三角形退化(一条线或一个点)的边缘情况。您必须使用特殊情况代码来执行此操作，这并不是那么糟糕，因为零法线说明了 ABC 和 P 的几何形状。

这是 C 代码，它使用简单的恒等式比上面的数学更好地重用操作数:

#include <stdio.h>

void diff(double *r, double *a, double *b) {
  r[0] = a[0] - b[0];
  r[1] = a[1] - b[1];
  r[2] = a[2] - b[2];
}

void cross(double *r, double *a, double *b) {
  r[0] = a[1] * b[2] - a[2] * b[1];
  r[1] = a[2] * b[0] - a[0] * b[2];
  r[2] = a[0] * b[1] - a[1] * b[0];
}

double dot(double *a, double *b) {
  return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
}

int point_over_triangle(double *a, double *b, double *c, double *p) {
  double ba[3], cb[3], ac[3], px[3], n[3], nx[3];

  diff(ba, b, a);
  diff(cb, c, b);
  diff(ac, a, c);

  cross(n, ac, ba);  // Same as n = ba X ca

  diff(px, p, a);
  cross(nx, ba, px);
  if (dot(nx, n) < 0) return 0;

  diff(px, p, b);
  cross(nx, cb, px);
  if (dot(nx, n) < 0) return 0;

  diff(px, p, c);
  cross(nx, ac, px);
  if (dot(nx, n) < 0) return 0;

  return 1;
}

int main(void) {
  double a[] = { 1, 1, 0 };
  double b[] = { 0, 1, 1 };
  double c[] = { 1, 0, 1 };
  double p[] = { 0, 0, 0 };

  printf("%s\n", point_over_triangle(a, b, c, p) ? "over" : "not over");

  return 0;
}

我对其进行了轻微测试，它似乎工作正常。