如何确定点是否位于3D中的三角形上方

Question

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

我需要计算一个点和一个三角形之间的距离（如果其投影位于三角形内部，则该点与该三角形的面之间；如果其投影位于三角形外部，则该点与该三角形的边缘之间）。

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

Answer 1

如果三角形的顶点是A，B，C，且点是P，则从找到三角形的法线N开始。为此，只需计算N =（BA）X（CA），其中X是矢量叉积。

目前，假设P与ABC位于正常ABC的同一侧。

考虑面为ABC，ABP，BCP，CAP的3d金字塔。当且仅当ABC与其他三个三角形中的每一个之间的二面角均小于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;
}

我已经对其进行了轻松的测试，并且似乎工作正常。