光线-盒相交理论

Question

我希望确定射线与盒子之间的交点。该盒子由其最小三维坐标和最大三维坐标定义，射线由其起点和指向方向定义。

目前，我正在为盒子的每个面形成一个平面，并将射线与该平面相交。如果射线与平面相交，则检查交点是否实际上在盒子表面上。如果是，则检查它是否是该射线的最近交点，并返回最近的交点。

我检查平面交点是否在盒子表面本身上的方式是通过一个函数。

bool PointOnBoxFace(R3Point point, R3Point corner1, R3Point corner2)
{
  double min_x = min(corner1.X(), corner2.X());
  double max_x = max(corner1.X(), corner2.X());
  double min_y = min(corner1.Y(), corner2.Y());
  double max_y = max(corner1.Y(), corner2.Y());
  double min_z = min(corner1.Z(), corner2.Z());
  double max_z = max(corner1.Z(), corner2.Z());
  if(point.X() >= min_x && point.X() <= max_x && 
     point.Y() >= min_y && point.Y() <= max_y &&
     point.Z() >= min_z && point.Z() <= max_z)
     return true;

  return false;
}

其中corner1是该盒子面矩形的一个角，corner2是对面的角。我的实现大多数时候都能正常工作，但有时会给我错误的交点。请参见以下图像：

这张图片展示了从相机的眼睛出发并击中盒子表面的射线。其他射线是盒子表面的法线。可以看到特定的一条射线（实际上是法线）从盒子的“后面”出现，而法线应该从盒子的顶部向上出现。这似乎很奇怪，因为还有其他多个射线正确地击中了盒子的顶部。

我想知道我检查交点是否在盒子上的方式是否正确，或者是否应该使用其他算法。

谢谢。

- Myx

---

很棒的示意图，它真的帮助了解释问题。 - Adrian McCarthy

Answer 1

将间隔增加epsilon并不是一个好的方法，因为现在在你的盒子边缘处有大小为epsilon的边框，光线可以通过。所以你会摆脱这个（相对普遍的）奇怪错误集，并得到另一个（更罕见的）奇怪错误集。

我假设你已经想象好了光线沿着其向量以某种速度行进，并找到与每个平面相交的时间。例如，如果你在与x = x0的平面相交，并且你的光线从（0,0,0）沿着方向（rx，ry，rz）前进，则相交时间为t = x0 / rx。如果t为负数，请忽略它-你正在朝另一个方向前进。如果t为零，您必须决定如何处理该特殊情况-如果您已经在平面上，则是否反弹？是否穿过它？您可能还要将rx == 0作为一种特殊情况处理（以便您可以击中盒子的边缘）。

无论如何，现在您恰好知道了撞击该平面的坐标：它们是（t * rx，t * ry，t * rz）。 现在，您只需读取t * ry和t * rz是否在其所需的矩形内（即，在沿着那些轴的立方体的最小值和最大值之间）。您不测试x坐标，因为您已经知道您击中了它。同样，您必须决定是否/如何将击中角落作为一个特殊情况处理。此外，现在您可以按时间对各个表面的碰撞进行排序，并选择第一个作为碰撞点。

这使得您能够计算出光线是否以及在哪里与立方体相交，而无需诉诸任意的epsilon因子，达到浮点运算的准确度。

所以你只需要像你已经拥有的那个一样，三个函数：一个用于测试是否在假定你击中x的情况下，在yz内击中，以及分别假定你击中y和z的xz和xy的相应函数。

---

编辑：添加代码（详细说明如何针对每个轴进行不同的测试）：

#define X_FACE 0
#define Y_FACE 1
#define Z_FACE 2
#define MAX_FACE 4

// true if we hit a box face, false otherwise
bool hit_face(double uhit,double vhit,
                 double umin,double umax,double vmin,double vmax)
{
  return (umin <= uhit && uhit <= umax && vmin <= vhit && vhit <= vmax);
}

// 0.0 if we missed, the time of impact otherwise
double hit_box(double rx,double ry, double rz,
                double min_x,double min_y,double min_z,
                double max_x,double max_y,double max_z)
{
  double times[6];
  bool hits[6];
  int faces[6];
  double t;
  if (rx==0) { times[0] = times[1] = 0.0; }
  else {
    t = min_x/rx;
    times[0] = t; faces[0] = X_FACE; 
    hits[0] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
    t = max_x/rx;
    times[1] = t; faces[1] = X_FACE + MAX_FACE;
    hits[1] = hit_box(t*ry , t*rz , min_y , max_y , min_z , max_z);
  }
  if (ry==0) { times[2] = times[3] = 0.0; }
  else {
    t = min_y/ry;
    times[2] = t; faces[2] = Y_FACE;
    hits[2] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
    t = max_y/ry;
    times[3] = t; faces[3] = Y_FACE + MAX_FACE;
    hits[3] = hit_box(t*rx , t*rz , min_x , max_x , min_z , max_z);
  }
  if (rz==0) { times[4] = times[5] = 0.0; }
  else {
    t = min_z/rz;
    times[4] = t; faces[4] = Z_FACE;
    hits[4] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
    t = max_z/rz;
    times[5] = t; faces[5] = Z_FACE + MAX_FACE;
    hits[5] = hit_box(t*rx , t*ry , min_x , max_x , min_y , max_y);
  }
  int first = 6;
  t = 0.0;
  for (int i=0 ; i<6 ; i++) {
    if (times[i] > 0.0 && (times[i]<t || t==0.0)) {
      first = i;
      t = times[i];
    }
  }
  if (first>5) return 0.0;  // Found nothing
  else return times[first];  // Probably want hits[first] and faces[first] also....
}

我刚刚打了这个代码，没有编译它，所以要小心错误。

总之，重点是将三个方向分开处理，并测试是否在(u,v)坐标系中的正确框内发生了碰撞，其中(u,v)取决于你击中的平面是哪个：(x,y)、(x,z)或(y,z)。

- Rex Kerr

---

谢谢您详细的回复。我也更喜欢使用不依赖于epsilon递增的方法。然而，使用您的方法，我必须知道面平面不包括哪个轴，对吗？如果是这样，我该如何检查我撞到了哪个轴（即，您能解释一下您在最后一句话中的措辞吗？） - Myx

我已经添加了代码，希望能够使其清晰明了。需要注意的关键点是，根据你正在测试的面不同，你需要进行不同的hit_box测试。(例如，第一个被测试的是min_x，我们会看到撞击点是否在yz矩形内。) - Rex Kerr

谢谢你提供的代码，它让我更清楚了解了事情。在你的代码中，你进行了如下检查：if(rx==0)...if(ry==0)...if(rz==0)。这对于“轴对齐的盒子”是正确的吗？我只是担心盒子可能以这样或那样的方式定向，使得它的平面不一定沿着x、y或z轴。 - Myx

这是处理光线与面之一平行的情况--否则我会除以零。在这种情况下，我使用上述逻辑说它总是错过了那个面。如果您的盒子沿轴线不对齐，请旋转向量（和原点）的坐标使其对齐，然后进行比较--这样您就可以像这里所示使用精确测试。 - Rex Kerr

感谢您的帮助和解释。非常感激！=) - Myx

Answer 2

PointOnBoxFace 应该是二维检查，而不是三维的。例如，如果您正在测试 z = z_min 平面，则只需要将 x 和 y 与它们各自的边界进行比较。您已经确定了 z 坐标是正确的。浮点精度可能会让您在“重新检查”第三个坐标时出错。

例如，如果 z_min 是 1.0，则首先对该平面进行测试。您找到一个交点 (x, y, 0.999999999)。现在，即使 x 和 y 在范围内，z 也不完全正确。

- Adrian McCarthy

Answer 3

编辑：忽略这个答案（请参见下面的评论，我被有力地证明了我的错误）。

您正在测试点是否在体积内部，但该点位于该体积的周围，因此您可能会发现它与体积的“无穷小”距离在外。尝试通过一些小的epsilon扩大框，例如：

double epsilon = 1e-10; // Depends the scale of things in your code.
double min_x = min(corner1.X(), corner2.X()) - epsilon;
double max_x = max(corner1.X(), corner2.X()) + epsilon;
double min_y = min(corner1.Y(), corner2.Y()) - epsilon;
...

从技术上讲，比较几乎相等的数字的正确方法是将它们的位表示转换为整数，并对一些小偏移量进行比较，例如在C语言中：

#define EPSILON 10 /* some small int; tune to suit */
int almostequal(double a, double b) {
    return llabs(*(long long*)&a - *(long long*)&b) < EPSILON;
}

当然，在C#中这并不容易，但也许不安全语义可以实现相同的效果。（感谢@Novox的评论，他引导我到一个很好的页面详细解释了这个技术。）

- Marcelo Cantos

---

请注意不要选择太小的epsilon；否则，您的浮点数单元会干扰denorms（即非规格化浮点数），这可能会严重影响性能。 - Frank

这是一些问题的好答案，但不适用于Myx的问题。现在你碰到了那些几乎错过的东西，而且你是不必要地这样做的。 - Rex Kerr

@Myx：浮点数使用二进制尾数mmmm和指数eee表示，它们一起表示数字1.mmmm2^eee。当数字接近零时，eee达到其负极限，此时数字被表示为0.01mm2^eee。这是一种非规格化的浮点数。这些数字的问题在于失去了精度，并且需要更多的FPU工作。 - Marcelo Cantos

这是一种简单地推迟问题的黑客方法。 - Adrian McCarthy

@Marcelo：epsilon比较对于某些问题非常好，但_不适用于这个问题_。它_是_一个矩形立方体，而且，这是一个_体积碰撞测试_，当你碰到平面表面时，你永远不需要进行epsilon化（除非你的体积小于epsilon厚度）。这是多面体表面反射的一个好方法。 - Rex Kerr

Answer 4

代码看起来没问题。尝试找到这个特定的光线并进行调试。

- Andrey

---

有没有其他方法可以检查一个特定点是否在盒子表面上？也许可以使用光线和3D点来代替显式地检查x、y和z坐标吗？ - Myx

你可以并且应该将光线视为向量，并通过方程找到交点的x、y、z值。 - Andrey

我已经通过方程找到了交点的x、y、z坐标。现在的目标是找出这个x、y、z是否在盒子的某个面上，我想知道是否有一个方程可以解决这个问题。 - Myx

代码看起来不太好。它测试了Myx已经假定的某个面被击中的情况。再次测试是多余的。 - Rex Kerr

Answer 5

它可能会恰好穿过盒子的边缘吗？浮点舍入误差可能导致它被右侧和后面的面都错过。

- Thomas

---

从视觉反馈来看，似乎并不是这种情况。但这也是我应该处理的问题（我本来打算以后再担心它）。我该如何解决这个问题？（即如果光线正好击中边缘或角落） - Myx